ターボ符号ターボ符号の概要

利点と欠点

既知の誤り訂正符号の中では、ターボ符号と低密度パリティ検査符号 (LDPC) がシャノン限界（ノイズのある伝送路における最大情報転送量の理論的限界値）に最も近い。

ターボ符号は送信機の出力を上げずにデータレートを上げることができ、逆に言えばあるデータレートでの消費電力を低減できる。主な欠点は、復号処理が複雑で復号処理遅延が比較的大きい点であり、このため低レイテンシが重視される用途には向かない。但し、復号処理は近年のプロセッサの高速化でレイテンシ全体で見ると支配要因とはならない場合がある。また、宇宙探査機において、復号処理遅延の大きいターボ符号であっても問題とされない。復号処理遅延より伝搬遅延の方がレイテンシの支配要因となるためである。

ターボ符号以前には、LDPCの実用的実装も開発されていなかったため、シャノン限界に最も近い技法としては、リード・ソロモン誤り訂正ブロック符号とビタビ復号の短拘束長畳み込み符号を組み合わせた RSV 符号があった。

これらのアルゴリズムは複雑であり、ソフトウェア特許で守られているため、システムに採用するのを避ける場合がある。

歴史

1993年、Claude Berrou、Alain Glavieux、Punya Thitimajshima（ブルターニュ電気通信国立大学）が論文 "Near Shannon Limit error-correcting coding and decoding: Turbo-codes. 1" (Berrou etal.(1993)) を Proceedings of IEEE International Communications Conferenceで発表した。Berrou は「80年代末に確率過程の面白さを教えてくれた G. Battail、J. Hagenauer、P. Hoeher に負うところがある」としている。また、「R. Gallager と M. Tanner はこれと非常に近い原理の符号化・復号技法を既に構想していた」とも書いているが、当時は必要な計算ができていなかった^[1]。Joachim Hagenauerは、「ターボエンジンの類推から、復号でおいてのみフィードバック情報が使われるため、ターボ符号という名称は不適切である。」と述べている^[2]。

符号化

符号器はビット列を3つのサブブロックとして送信する。第一のサブブロックは m-ビットのペイロードデータである。第二のサブブロックはそのペイロードデータの n/2 パリティビット列であり、再帰系統的畳み込み符号（RSC符号）を使って計算する。第三のサブブロックはペイロードデータの既知の並べ替えの n/2 パリティビット列であり、こちらもRSC畳み込み符号を使って計算する。従って、ペイロードと共に2つの冗長だが異なるパリティビット列が送信される。ブロック長は m+n ビットであり、符号レートは m/(m+n) である。ペイロードデータの並べ替えは、インターリーバ（interleaver）という手法を使う。

ハードウェアによるターボ符号器は2つのRSC符号器 C₁ と C₂ から構成され、これらの出力を並列連結と呼ばれる手法で連結する。

入力ビット列 d_k は C₁ にはそのまま入力され、C₂ にはインターリーバを通して並べ替えた上で入力される。出力は、入力 d_k をそのまま出力する系統出力 x_k と C₁ の出力 y_1k、C₂ の出力 y_2k がある。

復号

復号器も符号器と似たような形で構築され、2つの復号器を相互接続するが、こちらは直列接続であって並列接続ではない。それ故、遅延は符号器よりも構造的に大きくなる。一段目の復号器 DEC₁ が符号器 C₁ に対応し、二段目の復号器 DEC₂ が符号器 C₂ に対応している。DEC₁ は軟判定を行い、それによって L₁ の遅延が生じる。同じ遅延は符号器のインタリーバ部分にあるレジスタでも生じる。DEC₂ では L₂ の遅延を生じる。