ターボ符号

ターボ符号（ターボふごう、英: Turbo code）は、1993年に発表された高性能な誤り訂正符号である^[1]。第三世代携帯電話、第四世代携帯電話などの移動通信システムや、宇宙探査機での通信など、ノイズのある限られた帯域幅であっても、信頼性の高い高速通信を行う場合に使われている。

利点と欠点

既知の誤り訂正符号の中では、ターボ符号と低密度パリティ検査符号 (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₂ の遅延を生じる。

2つの復号器の中間にインターリーバが置かれ、DEC₁ の出力におけるバースト誤りを分散させる。受信信号のうち x_k はそのまま DEC₁ に入力されるが、y_1k または y_2k に相当する部分はデマルチプレクサによって DEC₁ か DEC₂ に振り分けられる。

伝送路が履歴の影響がないガウスノイズのある加算的伝送路（AWGN）とし、反復が k 番目の場合、復号器は以下のような確率変数の対を受け取る。

~x_{k}=(2d_{k}-1)+a_{k}

,

~y_{k}=2(Y_{k}-1)+b_{k}

ここで a_k と b_k は独立ノイズ成分であり、共に分散は σ² である。Y_k は y_k 符号器出力の k 番目のビットである。

冗長情報はデマルチプレックスされた後、（y_k=y_1k のとき）DEC₁ に送られるか（y_k=y_2k のとき）DEC₂ に送られる。

DEC₁ は軟判定を行う。すなわち、

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

であり、その結果を DEC₂ に渡す。Λ(d_k) は logarithm of likelihood ratio (LLR) と呼ばれる。p(d_k=i), _i=0,1 は d_k データビットの事後確率(APP)であり、受信した d_k を i と解釈する確率を示している。LLR を考慮することで、DEC₂ は硬判定、すなわち復号を行う。

ビタビアルゴリズムではAPPを計算できないことが知られている。そのため DEC₁ には使えない。その代わりに修正を加えたBCJRアルゴリズムを使う。DEC₂ にはビタビアルゴリズムがよく使われる。

なお、ここで示した流れは最適ではない。DEC₁ は利用可能な冗長情報の一部しか使っていない。一般に DEC₂ の出力を DEC₁ にフィードバックすることで最適化する。

軟判定手法

復号器の前半部はデータストリームの各ビットについて、ある整数値を生成する。この整数はそのビットが 0 または 1 である確からしさを示すものである。例えば、その整数が [-127, 127] の範囲とした場合、

-127 なら「確実に 0 である」
-100 なら「ほぼ確実に 0 である」
0 なら「0 または 1 のどちらかである」
100 なら「ほぼ確実に 1 である」
127 なら「確実に 1 である」

などと解釈できる。

これはフロントエンドからのデータストリームに確率的な面を導入するが、単にビットが0か1かというよりも多くの情報を伝えられる。

例えば、従来型の無線受信機のフロントエンドなら、各ビットは信号の電圧が所定のしきい電圧の上か下かで判別されていた。ターボ符号の復号器の場合、フロントエンドは電圧がしきい値からどれだけ離れているかを数値的に表すことになる。

m+n ビットのデータブロックを復号するため、復号器のフロントエンドは個々のビットの可能性測度をまとめた可能性測度のブロックを生成する。2つの並列の復号器が、それぞれ n/2 ビットのパリティサブブロックを扱う。これら復号器はペイロードデータのために m 個の可能性測度のサブブロックを使う。2番目のパリティのサブブロックを扱う復号器は、符号器が行った並べ替えを知っている。

2つのビットパターン仮説

ターボ符号の鍵となる発明は、可能性データをどのように使って2つの復号器の違いを調和させるかという点である。2つの畳み込み復号器はそれぞれ m ビットのパターンの仮説（と可能性）を生成する。仮説ビットパターンを比較し、差異があれば、復号器は仮説内の各ビットに対応した可能性測度を交換する。それぞれの復号器はもう一方の復号器が生成した可能性測度列を持っていて、それを使って新たな仮説ビットパターンを生成する。その後、それらは新たな仮説を比較する。このような反復プロセスは2つの復号器が同じ仮説ビットパターンで合意するまで繰り返され、通常15から18回反復される。

これは、言ってみればクロスワードパズルや数独を解くようなものである。部分的に解かれ一部改ざんされた可能性のあるクロスワードパズルを2人の人間（=復号器）が解くことを想定してみよう。1人は縦のヒント（パリティビット）だけを処理し、もう1人は横のヒントだけを処理する。2人はまず自分の持つヒントに基づいてパズルを解き、それぞれの文字についてどれだけ信頼があるかを添える。そして、それぞれの結果を比較し、互いに解と信頼度を交換し、どこがどう違うのかを知る。この新たな知識に基づいて、解と信頼度を更新し、最終的に同じ解になるまでこれを繰り返すのである。