ターボコード

情報理論 において、ターボ符号は、1990～91年頃に開発され、1993年に初めて発表された高性能前方誤り訂正（FEC）符号の一種です。これらは、特定のノイズレベルが与えられた場合に信頼性の高い通信が可能な符号化率の理論上の最大値である最大チャネル容量またはシャノン限界に非常に近い最初の実用的な符号でした。ターボ符号は、 3G / 4G移動体通信（UMTSやLTEなど）や（深宇宙）衛星通信、および設計者がデータ破損ノイズが存在する状況下で帯域幅または遅延が制限された通信リンクを介して信頼性の高い情報伝送を実現しようとするその他のアプリケーションで使用されています。ターボ符号は、同様の性能を提供する低密度パリティ検査（LDPC）符号と競合します。ターボ符号の特許が失効するまで^{[ 1 ]} 、 LDPC符号の特許フリーの状態は、LDPCの継続的な関連性の重要な要因でした。^{[ 2 ]}

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

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

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

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

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

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

ターボ符号が登場する以前は、最良の構成は、外側のリード・ソロモン誤り訂正符号と内側のビタビ復号された短制約長畳み込み符号を組み合わせた直列連結符号であり、RSV符号としても知られていた。

後の論文で、ベルーは「80年代後半に確率的処理の関心を強調したG. バテイル、 J. ハーゲナウアー、P. ヘーハーの直感」を称賛した。さらに、「 R. ギャラガーとM. タナーは、その一般原理が密接に関連した符号化および復号化技術をすでに構想していた」と付け加えたが、当時は必要な計算が非現実的だった。^{[ 6 ]}

ターボ符号には、異なるコンポーネントエンコーダ、入出力比、インターリーバ、およびパンクチャリングパターンを使用する、さまざまな種類があります。このエンコーダ実装例では、古典的なターボエンコーダについて説明し、並列ターボ符号の一般的な設計を示します。

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

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

図において、Mはメモリレジスタである。遅延線とインターリーバにより、入力ビットd _kは異なるシーケンスで現れる。最初の反復では、エンコーダの系統的な性質により、入力シーケンスd _kはエンコーダの2つの出力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 つのデコーダの間に設置されたインターリーバを使用して、エラーバーストを分散します。${\displaystyle \textstyle DEC_{1}}$出力。DIブロックはデマルチプレクサおよび挿入モジュールです。スイッチとして機能し、入力ビットをリダイレクトします。${\displaystyle \textstyle DEC_{1}}$ある瞬間には${\displaystyle \textstyle DEC_{2}}$別の場所で。OFF 状態では両方に電力を供給します。${\displaystyle \textstyle y_{1k}}$そして${\displaystyle \textstyle y_{2k}}$パディングビット（ゼロ）を含む入力。

メモリレスAWGNチャネルを考え、k回目の反復において、デコーダが2つのランダム変数を受信すると仮定します。

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

どこ${\displaystyle \textstyle a_{k}}$そして${\displaystyle \textstyle b_{k}}$同じ分散を持つ独立したノイズ成分である${\displaystyle \textstyle \sigma ^{2}}$。${\displaystyle \textstyle Y_{k}}$は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)}}}$

そしてそれを届けます${\displaystyle \textstyle DEC_{2}}$。${\displaystyle \textstyle \Lambda (d_{k})}$これは尤度比の対数（LLR）と呼ばれます。${\displaystyle \textstyle p(d_{k}=i),\,i\in \{0,1\}}$事後確率(APP)は、${\displaystyle \textstyle d_{k}}$受信したデータを解釈する確率を示すデータビット${\displaystyle \textstyle d_{k}}$ビットとして${\displaystyle \textstyle i}$LLRを考慮すると、${\displaystyle \textstyle DEC_{2}}$明確な決定、つまり復号されたビットが得られます。

ビタビアルゴリズムはAPPを計算できないことが知られているため、${\displaystyle \textstyle DEC_{1}}$その代わりに、修正されたBCJRアルゴリズムが使用されます。${\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ビットのデータブロックを復号するために、デコーダのフロントエンドは、データストリームの各ビットに対応する尤度尺度のブロックを作成します。n / 2ビットのパリティサブブロックそれぞれに 1 つずつ、2 つの並列デコーダがあります。どちらのデコーダも、ペイロードデータにm個の尤度のサブブロックを使用します。2番目のパリティサブブロックを処理するデコーダは、コーダがこのサブブロックに使用した順列を知っています。

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

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

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

電気通信：

• ターボコードは、 HSPA、EV-DO、LTEなどの3Gおよび4Gモバイル通信規格で広く使用されています。
• MediaFLOは、クアルコム社製の地上波モバイルテレビシステムです。
• DVB-RCS ^{[ 7 ]}やDVB-RCS2などの衛星通信システムの相互作用チャネル。
• 最近のNASAのミッション、例えば火星偵察オービターなどは、リード・ソロモン誤り訂正・ビタビ復号符号の代替としてターボ符号を使用している。
• IEEE 802.16（WiMAX）は、無線都市型ネットワーク規格であり、ブロックターボ符号化と畳み込みターボ符号化を使用している。

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

• BCJRアルゴリズム
• 畳み込み符号
• 前方誤り訂正
• インターリーバー
• 低密度パリティチェックコード
• 直列連結畳み込み符号
• ソフトデシジョン復号
• ターボイコライザー
• ビタビアルゴリズム

• Guizzo, Erico (2004年3月) 「完璧なコードに近づく」 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でターボコードをシミュレーションするためのオープンソースライブラリです。
• 「ターボ等化：原理と新しい結果」は、 2009年2月27日にWayback Machineにアーカイブされた、畳み込み符号とチャネル等化を併用することに関するIEEE Transactions on Communicationsの記事です。
• IT++ ホームページ IT ++は強力な C++ ライブラリであり、特にターボコードをサポートしています。
• デビッド・マッケイによるターボコード出版物
• AFF3CTホームページ（高速前方誤り訂正ツールボックス）：ソフトウェアによる高速ターボコードシミュレーション用
• ケルエダン、シルヴィ。ベロ、クロード(2010)。「ターボコード」。スカラーペディア。５（４）。 sawpedia.org: 6496. Bibcode : 2010SchpJ...5.6496K。土井：10.4249/scholarpedia.6496。
• 3GPP LTE Turbo リファレンスデザイン。
• AWGNにおけるターボ符号BER性能の推定（ 2019年2月1日にWayback Machineにアーカイブ済み）（MatLab）。
• 並列連結畳み込み符号化：ターボ符号（MatLab Simulink）