ターボ符号（ターボふごう、）は、1993年に開発された高性能な誤り訂正符号であり、宇宙探査機での通信など、ノイズのある限られた帯域幅で情報転送量を可能な限り最大化したい場合に使われている。既知の誤り訂正符号の中では、ターボ符号と低密度パリティ検査符号 (LDPC) がシャノン限界（ノイズのある伝送路における最大情報転送量の理論的限界値）に最も近い。ターボ符号は送信機の出力を上げずにデータレートを上げることができ、逆に言えばあるデータレートでの消費電力を低減できる。主な欠点は、復号処理が複雑でレイテンシが比較的大きい点であり、このため低レイテンシが重視される用途には向かない。宇宙探査機ではレイテンシは大きな問題ではない（距離が非常に大きいため、電波が光速で伝播する際のレイテンシ自体が大きいから）ターボ符号以前には、LDPCの実用的実装も開発されていなかったため、シャノン限界に最も近い技法としては、リード・ソロモン誤り訂正ブロック符号とビタビ復号の短拘束長畳み込み符号を組み合わせた RSV 符号があった。これらのアルゴリズムは複雑であり、ソフトウェア特許で守られているため、システムに採用するのを避ける場合がある。1993年、Claude Berrou、Alain Glavieux、Punya Thitimajshima（ENSTブルターニュ）が論文 "Near Shannon Limit error-correcting coding and decoding: Turbo-codes" を Proceedings of IEEE International Communications Conference で発表した。Berrou は「80年代末に確率過程の面白さを教えてくれた G. Battail、J. Hagenauer、P. Hoeher に負うところがある」としている。また、「R. Gallager と M. Tanner はこれと非常に近い原理の符号化・復号技法を既に構想していた」とも書いているが、当時は必要な計算ができていなかった。符号器はビット列を3つのサブブロックとして送信する。第一のサブブロックは "m"-ビットのペイロードデータである。第二のサブブロックはそのペイロードデータの "n/2" パリティビット列であり、再帰系統的畳み込み符号（RSC符号）を使って計算する。第三のサブブロックはペイロードデータの既知の並べ替えの "n/2" パリティビット列であり、こちらもRSC畳み込み符号を使って計算する。従って、ペイロードと共に2つの冗長だが異なるパリティビット列が送信される。ブロック長は "m+n" ビットであり、符号レートは "m/(m+n)" である。ペイロードデータの並べ替えは、インターリーバ（interleaver）というデバイスを使う。ハードウェアによるターボ符号器は2つのRSC符号器 C と C から構成され、これらの出力を並列連結と呼ばれる手法で連結する。入力ビット列 d は C にはそのまま入力され、C にはインターリーバを通して並べ替えた上で入力される。出力は、入力 d をそのまま出力する系統出力 x と C の出力 y、C の出力 y がある。復号器も符号器と似たような形で構築され、2つの復号器を相互接続するが、こちらは直列接続であって並列接続ではない。一段目の復号器 "DEC" が符号器 "C" に対応し、二段目の復号器 "DEC" が符号器 "C" に対応している。"DEC" は軟判定を行い、それによって "L" の遅延が生じる。同じ遅延は符号器のインタリーバ部分にあるレジスタでも生じる。"DEC" では "L" の遅延を生じる。2つの復号器の中間にインターリーバが置かれ、"DEC" の出力におけるバースト誤りを分散させる。受信信号のうち x はそのまま "DEC" に入力されるが、y または y に相当する部分はデマルチプレクサによって "DEC" か "DEC" に振り分けられる。伝送路が履歴の影響がないガウスノイズのある加算的伝送路（AWGN）とし、反復が "k" 番目の場合、復号器は以下のような確率変数の対を受け取る。ここで "a" と "b" は独立ノイズ成分であり、共に分散は σ である。"Y" は "y" 符号器出力の "k" 番目のビットである。冗長情報はデマルチプレックスされた後、（"y"="y" のとき）"DEC" に送られるか（"y"="y" のとき）"DEC" に送られる。"DEC" は軟判定を行う。すなわち、であり、その結果を "DEC" に渡す。Λ("d") は "logarithm of likelihood ratio" (LLR) と呼ばれる。"p"(d="i"), =0,1 は "d" データビットの事後確率(APP)であり、受信した "d" を "i" と解釈する確率を示している。"LLR" を考慮することで、"DEC" は硬判定、すなわち復号を行う。ビタビアルゴリズムではAPPを計算できないことが知られている。そのため "DEC" には使えない。その代わりに修正を加えたBCJRアルゴリズムを使う。"DEC" にはビタビアルゴリズムがよく使われる。なお、ここで示した流れは最適ではない。"DEC" は利用可能な冗長情報の一部しか使っていない。一般に "DEC" の出力を "DEC" にフィードバックすることで最適化する。復号器の前半部はデータストリームの各ビットについて、ある整数値を生成する。この整数はそのビットが 0 または 1 である確からしさを示すものである。例えば、その整数が [-127, 127] の範囲とした場合、などと解釈できる。これはフロントエンドからのデータストリームに確率的な面を導入するが、単にビットが0か1かというよりも多くの情報を伝えられる。例えば、従来型の無線受信機のフロントエンドなら、各ビットは信号の電圧が所定のしきい電圧の上か下かで判別されていた。ターボ符号の復号器の場合、フロントエンドは電圧がしきい値からどれだけ離れているかを数値的に表すことになる。"m+n" ビットのデータブロックを復号するため、復号器のフロントエンドは個々のビットの可能性測度をまとめた可能性測度のブロックを生成する。2つの並列の復号器が、それぞれ "n/2" ビットのパリティサブブロックを扱う。これら復号器はペイロードデータのために "m" 個の可能性測度のサブブロックを使う。2番目のパリティのサブブロックを扱う復号器は、符号器が行った並べ替えを知っている。ターボ符号の鍵となる発明は、可能性データをどのように使って2つの復号器の違いを調和させるかという点である。2つの畳み込み復号器はそれぞれ "m" ビットのパターンの仮説（と可能性）を生成する。仮説ビットパターンを比較し、差異があれば、復号器は仮説内の各ビットに対応した可能性測度を交換する。それぞれの復号器はもう一方の復号器が生成した可能性測度列を持っていて、それを使って新たな仮説ビットパターンを生成する。その後、それらは新たな仮説を比較する。このような反復プロセスは2つの復号器が同じ仮説ビットパターンで合意するまで繰り返され、通常15から18回反復される。これは、言ってみればクロスワードパズルや数独を解くようなものである。部分的に解かれ一部改ざんされた可能性のあるクロスワードパズルを2人の人間（=復号器）が解くことを想定してみよう。1人は縦のヒント（パリティビット）だけを処理し、もう1人は横のヒントだけを処理する。2人はまず自分の持つヒントに基づいてパズルを解き、それぞれの文字についてどれだけ自信があるかを添える。そして、それぞれの結果を比較し、互いに解と自信度を交換し、どこがどう違うのかを知る。この新たな知識に基づいて、解と自信度を更新し、最終的に同じ解になるまでこれを繰り返すのである。人工知能の観点では、ターボ符号はベイジアンネットワークでのループのある確率伝播と見なすことができる。

出典:wikipedia