ターボコード

情報理論において、ターボ符号は、1990年から1991年頃に開発され、1993年に初めて公開された高性能前方誤り訂正(FEC) 符号の一種である。これは、特定のノイズレベルを与えられた状態で信頼性の高い通信が依然として可能である符号レートの理論上の最大値である最大チャネル容量またはシャノン限界に極めて近づいた最初の実用的な符号であった。ターボ符号は、3G / 4Gモバイル通信 ( UMTSやLTEなど) や (深宇宙)衛星通信、およびデータ破損ノイズが存在する状況で帯域幅または遅延が制約された通信リンクを介して信頼性の高い情報転送を実現しようとする設計者が求めるその他のアプリケーションで使用されている。ターボ符号は、同様のパフォーマンスを提供する低密度パリティチェック(LDPC) 符号と競合する。ターボ符号の特許が失効するまで、^[1] LDPC符号の特許フリーの状態は、LDPCの継続的な重要性において重要な要素であった。^[2]

「ターボコード」という名称は、通常のターボコードのデコード時に用いられるフィードバックループに由来しており、これはエンジンのターボチャージャーに用いられる排気フィードバックに類似している。ハーゲナウアーは、エンコードプロセスにはフィードバックが関与していないため、「ターボコード」という用語は誤称であると主張している。^[3]

歴史

ターボ符号の基本特許出願は1991年4月23日に提出されました。この特許出願では、クロード・ベルーがターボ符号の唯一の発明者として記載されています。この特許出願により、2013年8月29日に失効した米国特許第5,446,747号を含む複数の特許が取得されました。

ターボ符号に関する最初の公開論文は、「シャノン限界近傍の誤り訂正符号化と復号：ターボ符号」であった。^[4]この論文は1993年にIEEE国際通信会議の議事録に掲載された。1993年の論文は、紙面の制約により3つの別々の投稿が統合されたものである。この統合により、論文の著者はベルー、グラヴィエ、そしてティティマジマ（フランスのテレコム・ブルターニュ（旧ENSTブルターニュ）所属）の3名となった。しかし、元の特許出願から、ベルーがターボ符号の唯一の発明者であり、他の著者は中核概念以外の資料を寄稿したことは明らかである。^{[不適切な統合]}

ターボ符号は導入当時、非常に革新的なものであったため、符号化分野の専門家の多くは報告された結果を信じませんでした。しかし、その性能が確認されると、符号化の世界に小さな革命が起こり、他の多くの反復信号処理の研究につながりました。^[5]

最初のクラスのターボ符号は、並列連接畳み込み符号（PCCC）でした。1993年に最初の並列ターボ符号が導入されて以来、直列連接畳み込み符号や繰り返し累積符号など、多くのクラスのターボ符号が発見されてきました。反復ターボ復号法は、リード・ソロモン訂正畳み込み符号などのより従来的なFECシステムにも適用されてきましたが、これらのシステムは反復復号器の実用的な実装には複雑すぎます。ターボ等化もターボ符号化の概念から生まれました。

ベロウはターボ符号に加えて、再帰的組織的畳み込み符号（RSC符号）も発明しました。この符号は、特許に記載されているターボ符号の実装例で使用されています。RSC符号を使用するターボ符号は、RSC符号を使用しないターボ符号よりも性能が優れているようです。

ターボコード以前は、外部リードソロモンエラー訂正コードと内部ビタビ復号化短い制約長畳み込みコード(RSV コードとも呼ばれる) を組み合わせたシリアル連結コードが最良の構成でした。

後の論文で、ベロウは「80年代後半に確率処理の興味を浮き彫りにしたG. バテイル、 J. ハーゲナウアー、P. ホーハー」の直感に功績を認めている。さらに、「 R. ギャラガーとM. タナーは既に、一般原理が密接に関連する符号化・復号化技術を構想していた」と付け加えているが、当時は必要な計算は非現実的であった。^[6]

エンコーダの例

ターボ符号には、コンポーネントエンコーダ、入出力比、インターリーバー、パンクチャリングパターンなど、様々なインスタンスが存在します。このエンコーダ実装例では、典型的なターボエンコーダについて説明し、並列ターボ符号の一般的な設計を示します。

このエンコーダ実装では、3つのビットのサブブロックが送信されます。最初のサブブロックは、ペイロードデータのmビットブロックです。2番目のサブブロックは、ペイロードデータのn/2パリティビットで、再帰組織畳み込み符号（RSC符号）を使用して計算されます。3番目のサブブロックは、ペイロードデータの既知の順列のn/2パリティビットで、これもRSC符号を使用して計算されます。したがって、2つの冗長で異なるパリティビットのサブブロックがペイロードとともに送信されます。完全なブロックには、符号化率がm /( m + n )のm + nビットのデータが含まれます。ペイロードデータの順列は、インターリーバーと呼ばれるデバイスによって実行されます。

ハードウェア的には、このターボコードエンコーダは、図に示すように、2 つの同一の RSC コーダC ₁とC _{2で構成され、}並列連結と呼ばれる連結方式を使用して相互に接続されています。

図中のMはメモリレジスタである。遅延線とインターリーバは、入力ビットd _kを異なるシーケンスで出現させる。最初の反復では、エンコーダのシステマティックな性質により、入力シーケンスd _{kはエンコーダの両方の出力}x _kとy _1kまたはy _2kに現れる。エンコーダC ₁とC _2がn ₁とn ₂の反復で使用される場合、それらのレートはそれぞれ次のようになる。

{\begin{aligned}~R_{1}&={\frac {n_{1}+n_{2}}{2n_{1}+n_{2}}}\\~R_{2}&={\frac {n_{1}+n_{2}}{n_{1}+2n_{2}}}\end{aligned}}

デコーダー

デコーダは上記のエンコーダと同様の方法で構築されています。2つの基本デコーダが相互接続されていますが、並列ではなく直列に接続されています。デコーダは低速（つまり）で動作するため、エンコーダを対象としており、はそれに応じてとなります。はソフト判定を生成し、遅延が発生します。エンコーダ内の遅延線によっても同じ遅延が発生します。の動作によって遅延が発生します。 $\textstyle DEC_{1}$ $\textstyle R_{1}$ $\textstyle C_{1}$ $\textstyle DEC_{2}$ $\textstyle C_{2}$ $\textstyle DEC_{1}$ $\textstyle L_{1}$ $\textstyle DEC_{2}$ $\textstyle L_{2}$

2つのデコーダ間に配置されたインターリーバは、出力から発生するエラーバーストを分散させるために使用されます。DIブロックは、多重分離および挿入モジュールです。スイッチとして機能し、入力ビットをある時点でに、別の時点でにリダイレクトします。OFF状態では、両方の入力にパディングビット（ゼロ）を供給します。 $\textstyle DEC_{1}$ $\textstyle DEC_{1}$ $\textstyle DEC_{2}$ $\textstyle y_{1k}$ $\textstyle y_{2k}$

メモリのないAWGNチャネルを考え、k回目の反復でデコーダーがランダム変数のペアを受信すると仮定します。

{\begin{aligned}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{k}\end{aligned}}

ここで、およびは同じ分散を持つ独立したノイズ成分です。はエンコーダ出力のk番目のビットです。 $\textstyle a_{k}$ $\textstyle b_{k}$ $\textstyle \sigma ^{2}$ $\textstyle Y_{k}$ $\textstyle y_{k}$

冗長情報は多重分離され、DIを介して( の場合) および( の場合)に送信されます。 $\textstyle DEC_{1}$ $\textstyle y_{k}=y_{1k}$ $\textstyle DEC_{2}$ $\textstyle y_{k}=y_{2k}$

$\textstyle DEC_{1}$ ソフトな決定が下されます。つまり、

\Lambda (d_{k})=\log {\frac {p(d_{k}=1)}{p(d_{k}=0)}}

それをに配信します。は尤度比（LLR）の対数と呼ばれます。はデータビットの事後確率（APP）であり、受信したビットをと解釈する確率を示します。LLRを考慮すると、はハードデシジョン、つまり復号されたビットとなります。 $\textstyle DEC_{2}$ $\textstyle \Lambda (d_{k})$ $\textstyle p(d_{k}=i),\,i\in \{0,1\}$ $\textstyle d_{k}$ $\textstyle d_{k}$ $\textstyle i$ $\textstyle DEC_{2}$

ビタビアルゴリズムはAPPを計算できないことが知られているため、では使用できません。代わりに、修正されたBCJRアルゴリズムが使用されます。の場合、ビタビアルゴリズムは適切なアルゴリズムです。 $\textstyle DEC_{1}$ $\textstyle DEC_{2}$

しかし、図示された構造は、利用可能な冗長情報の適切な一部しか使用していないため、最適な構造とは言えません。この構造を改善するために、フィードバックループが使用されます（図の点線を参照）。 $\textstyle DEC_{1}$

ソフトな意思決定アプローチ

デコーダのフロントエンドは、データストリームの各ビットに対して整数を生成します。この整数は、ビットが0または1である可能性の尺度であり、ソフトビットとも呼ばれます。この整数は[-127, 127]の範囲から抽出されます。ここで、

−127は「確実に0」を意味する
−100は「非常に可能性が高い0」を意味します
0は「0か1のどちらか」を意味します
100は「非常に可能性が高い1」を意味します
127は「確かに1」を意味します

これにより、フロントエンドからのデータストリームに確率的な側面が導入されますが、各ビットに関して 0 または 1 以上の情報が伝達されます。

例えば、従来の無線受信機のフロントエンドは、各ビットごとに内部アナログ電圧が所定の閾値電圧レベルを超えているか下回っているかを判断する必要があります。ターボ符号デコーダの場合、フロントエンドは内部電圧が所定の閾値からどれだけ離れているかを示す整数値を提供します。

m + nビットのデータブロックをデコードするために、デコーダのフロントエンドは、データストリームの各ビットに1つの尤度尺度を持つ尤度尺度のブロックを作成します。n ⁄ 2ビットのパリティサブブロックごとに1つずつ、2つの並列デコーダがあります。両方のデコーダは、ペイロードデータに対してm個の尤度のサブブロックを使用します。2番目のパリティサブブロックを処理するデコーダは、コーダがこのサブブロックに使用した順列を認識しています。

仮説を解いてビットを見つける

ターボ符号の重要な革新性は、尤度データを用いて2つのデコーダ間の差異を調整する方法にあります。2つの畳み込みデコーダはそれぞれ、ペイロードサブブロック内のmビットのパターンについて、仮説（導出尤度を含む）を生成します。仮説のビットパターンを比較し、異なる場合、デコーダは仮説内の各ビットについて導出尤度を交換します。各デコーダは、もう一方のデコーダから導出された尤度推定値を取り込み、ペイロード内のビットに対する新しい仮説を生成します。そして、これらの新しい仮説を比較します。この反復処理は、2つのデコーダがペイロードのmビットパターンに対して同じ仮説を生成するまで、通常15～18サイクルで継続されます。

このプロセスは、クロスワードパズルや数独のような相互参照パズルを解くプロセスと類似しています。例えば、部分的に完成し、文字化けしている可能性のあるクロスワードパズルを考えてみましょう。2人の解答者（デコーダー）がそれを解こうとしています。1人は「縦」の手がかり（パリティビット）のみを持ち、もう1人は「横」の手がかりのみを持っています。まず、両方の解答者はそれぞれの手がかりに対する答え（仮説）を推測し、各文字（ペイロードビット）に対する確信度を記録します。次に、解答と確信度を交換し、どこでどのように異なるかを確認しながら、両者の意見を比較します。この新しい知識に基づいて、両者は更新された解答と確信度を導き出し、同じ解に収束するまでこのプロセス全体を繰り返します。

パフォーマンス

ターボ符号は、チャネル上での符号のランダムな出現と物理的に実現可能な復号構造の魅力的な組み合わせにより、優れた性能を発揮します。ターボ符号はエラーフロアの影響を受けます。

ターボコードを用いた実用的応用

通信:

ターボコードは、 HSPA、EV-DO、LTEなどの 3Gおよび4Gモバイル電話規格で広く使用されています。
MediaFLO 、 Qualcommの地上モバイルテレビシステム。
DVB-RCS ^[7]やDVB-RCS2などの衛星通信システムの相互作用チャネル。
火星探査機などの最近のNASAミッションでは、リード・ソロモン誤り訂正-ビタビ復号器コードの代替としてターボコードが使用されています。
無線メトロポリタンネットワーク標準であるIEEE 802.16 ( WiMAX ) では、ブロックターボコーディングと畳み込みターボコーディングが使用されます。

ベイズ定式化

人工知能の観点から見ると、ターボ符号はベイジアンネットワークにおけるループ状の信念伝播の一例とみなすことができる。^[8]

参照

参考文献

^ US 5446747
^ Erico Guizzo (2004年3月1日). 「CLOSING IN ON THE PERFECT CODE」. IEEE Spectrum . 2023年4月23日時点のオリジナルよりアーカイブ。「もう一つの利点、おそらく最大の利点は、LDPCの特許の有効期限が切れているため、企業は知的財産権にお金を支払うことなくそれを使用できることです。」
^ Hagenauer, Joachim; Offer, Elke; Papke, Luiz (1996年3月). 「二進ブロック符号と畳み込み符号の反復復号法」(PDF) . IEEE Transactions on Information Theory . 42 (2): 429– 445. doi :10.1109/18.485714. 2013年6月11日時点のオリジナル(PDF)からアーカイブ。 2014年3月20日閲覧。
^ Berrou, Claude ; Glavieux, Alain ; Thitimajshima, Punya (1993)、「Near Shannon Limit Error – Correcting」、IEEE International Communications Conference Proceedings of IEEE International Communications Conference、第2巻、pp. 1064– 70、doi :10.1109/ICC.1993.397441、S2CID 17770377 、2010年2月11日閲覧。
^ Erico Guizzo (2004年3月1日). 「CLOSING IN ON THE PERFECT CODE」. IEEE Spectrum . 2023年4月23日時点のオリジナルよりアーカイブ。
^ ベルー、クロード、「10年前のターボコードがサービスを開始」、フランス、ブルターニュ、 2010年2月11日閲覧。
^ デジタルビデオ放送（DVB）; 衛星配信システムの相互作用チャネル、ETSI EN 301 790、V1.5.1、2009年5月。
^ McEliece, Robert J. ; MacKay, David JC ; Cheng, Jung-Fu (1998)、「Pearlの「ビリーフプロパゲーション」アルゴリズムの例としてのターボデコーディング」（PDF）、IEEE Journal on Selected Areas in Communications、16 (2): 140– 152、doi :10.1109/49.661103、ISSN 0733-8716。

さらに読む

出版物

Battail, Gérard (1998). 「ターボ符号を理解するための概念的枠組み」. IEEE Journal on Selected Areas in Communications . 916 (2): 245– 254. doi :10.1109/49.661112.
Brejza, MF; Li, L.; Maunder, RG; Al-Hashimi, BM; Berrou, C.; Hanzo, L. (2016). 「20年間のターボ符号化と、エネルギー制約のある無線アプリケーションのためのエネルギーを考慮した設計ガイドライン」(PDF) . IEEE Communications Surveys & Tutorials . 918 (1): 8– 28. doi :10.1109/COMST.2015.2448692. S2CID 12966388.
Garzón-Bohórquez, Ronald; Nour, Charbel Abdel; Douillard, Catherine (2016). パリティパンクチャ制約インターリーバを用いた5G向けターボ符号の改良(PDF) . 第9回ターボ符号および反復情報処理国際シンポジウム (ISTC). pp. 151– 5. doi :10.1109/ISTC.2016.7593095.

外部リンク

Guizzo, Erico (2004年3月). 「完璧なコードに近づく」. IEEE Spectrum 41 ( 3): 36– 42. doi :10.1109/MSPEC.2004.1270546. S2CID 21237188. 2009年10月11日時点のオリジナルよりアーカイブ。
「UMTSターボコードとソフトウェア無線に適した効率的なデコーダ実装」2016年10月20日アーカイブ（ International Journal of Wireless Information Networks）
マッケンジー、ダナ (2005). 「限界まで挑戦する」.ニュー・サイエンティスト. 187 (2507): 38–41 .
「限界に挑戦」、ターボ符号の発展と起源に関するサイエンスニュースの特集記事
ターボ符号に関する国際シンポジウム
Coded Modulation Library、MATLAB でターボ符号をシミュレートするためのオープンソースライブラリ
「ターボ等化: 原理と新たな結果」Wayback Machineに 2009 年 2 月 27 日にアーカイブされた、チャネル等化と畳み込みコードを併用することに関するIEEE Transactions on Communications の記事。
IT++ホームページIT++は、特にターボコードをサポートする強力なC++ライブラリです。
デビッド・マッケイによるターボコード出版物
ソフトウェアでの高速ターボコードシミュレーションのためのAFF3CTホームページ（高速フォワードエラー訂正ツールボックス）
ケルエダン、シルヴィ。ベロ、クロード(2010)。「ターボコード」。スカラーペディア。５（４）。学者ペディア.org: 6496。書誌コード:2010SchpJ...5.6496K。土井：10.4249/scholarpedia.6496。
3GPP LTE ターボリファレンスデザイン。
AWGN でのターボコード BER パフォーマンスの推定、Wayback Machine (MatLab) で 2019 年 2 月 1 日にアーカイブ。
並列連結畳み込み符号化：ターボ符号（MatLab Simulink）