ターボコード

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

「ターボコード」という名前は、通常のターボコードのデコード中に使用されるフィードバックループから生まれたもので、エンジンのターボチャージに使用される排気フィードバックに例えられています。ハーゲナウアーは、エンコードプロセスにはフィードバックが関与していないため、ターボコードという用語は誤った名称であると主張しています。^[3]

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

ターボ符号に関する最初の公開論文は、「シャノン限界に近い誤り訂正符号化および復号化: ターボ符号」でした。^[4]この論文は、1993 年に IEEE 国際通信会議の議事録で発表されました。1993 年の論文は、スペースの制約により 3 つの別々の投稿が結合されて作成されました。この結合により、論文には 3 人の著者が記載されました: Berrou、Glavieux、およびThitimajshima (フランスの Télécom Bretagne、旧ENST Bretagne )。ただし、元の特許出願から、Berrou がターボ符号の唯一の発明者であり、論文の他の著者はコア概念以外の資料を提供したことが明らかです。^{[不適切な統合]}

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

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

ターボ コードに加えて、Berrou は再帰的体系的畳み込み (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 _2の反復で使用される場合、それらのレートはそれぞれ次のようになります。

${\displaystyle {\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 つの基本デコーダが相互に接続されていますが、並列ではなく直列です。デコーダは低速 (つまり) で動作するため、エンコーダ用であり、同様に用です。はソフト決定を生成し、遅延を引き起こします。同じ遅延がエンコーダの遅延線によっても発生します。の動作により遅延が発生します。 ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle R_{1}}$${\displaystyle \textstyle C_{1}}$${\displaystyle \textstyle DEC_{2}}$${\displaystyle \textstyle C_{2}}$${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle L_{1}}$${\displaystyle \textstyle DEC_{2}}$${\displaystyle \textstyle L_{2}}$

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

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

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

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

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

${\displaystyle \textstyle DEC_{1}}$ソフトな決定をもたらします。つまり、

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

そしてそれを に配信します。は尤度比の対数( LLR )と呼ばれます。はデータ ビットの事後確率(APP)であり、受信したビットを と解釈する確率を示します。LLRを考慮すると、ハード決定、つまりデコードされたビットが生成されます。 ${\displaystyle \textstyle DEC_{2}}$${\displaystyle \textstyle \Lambda (d_{k})}$${\displaystyle \textstyle p(d_{k}=i),\,i\in \{0,1\}}$${\displaystyle \textstyle d_{k}}$${\displaystyle \textstyle d_{k}}$${\displaystyle \textstyle i}$${\displaystyle \textstyle DEC_{2}}$

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

ただし、図に示されている構造は、利用可能な冗長情報の適切な部分のみを使用しているため、最適なものではありません。構造を改善するために、フィードバック ループが使用されます (図の点線を参照)。 ${\displaystyle \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モバイル電話規格で広く使用されています。
• Qualcommの地上モバイルテレビ システム、MediaFLO。
• DVB-RCS ^[7]やDVB-RCS2などの衛星通信システムの相互作用チャネル。
• 火星探査機などの最近のNASAミッションでは、リード・ソロモン誤り訂正-ビタビ復号器コードの代替としてターボコードが使用されています。
• 無線メトロポリタン ネットワーク標準であるIEEE 802.16 ( WiMAX ) では、ブロック ターボ コーディングと畳み込みターボ コーディングが使用されます。

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

• BCJRアルゴリズム
• 畳み込み符号
• 前方誤り訂正
• インターリーバー
• 低密度パリティ検査符号
• シリアル連結畳み込み符号
• ソフト判定復号
• ターボイコライザー
• ビタビアルゴリズム

• 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通信調査とチュートリアル。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 月)。「Closing In On The Perfect Code」。IEEE Spectrum 41 ( 3): 36–42。doi : 10.1109 /MSPEC.2004.1270546。S2CID 21237188。2009 年 10 月 11 日時点のオリジナルよりアーカイブ。
• 「UMTS ターボ コードとソフトウェア定義無線に適した効率的なデコーダ実装」Wayback Machineに 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++ライブラリです。
• David MacKay によるターボコード出版物
• ソフトウェアでの高速ターボコードシミュレーションのためのAFF3CTホームページ（高速フォワードエラー訂正ツールボックス）
• ケルエダン、シルヴィ。ベロ、クロード(2010)。 「ターボコード」。スカラーペディア。５（４）。学者ペディア.org: 6496。書誌コード:2010SchpJ...5.6496K。土井：10.4249/scholarpedia.6496。
• 3GPP LTE Turbo リファレンス デザイン。
• AWGN でのターボ コード BER パフォーマンスの推定。Wayback Machine (MatLab) に 2019 年 2 月 1 日にアーカイブされました。
• 並列連結畳み込み符号化: ターボ符号 (MatLab Simulink)