ターボ符号とは？わかりやすく解説

ターボ符号（ターボふごう、英: 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}

要購読契約)

^ “Wayback MachineによるWebアーカイブ”. 11September 24, 2015時点のオリジナルよりアーカイブ。2018年9月23日閲覧。

^ Specification #: 25.212 Multiplexing and channel coding (FDD) 3GPP

^ Specification #: 36.212 Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel coding 3GPP

^ 林和則「確率伝搬法とその応用 (生命現象と関連した非線形問題の数理)」『数理解析研究所講究録』第1616巻、京都大学数理解析研究所、2008年10月、16-40頁、 CRID 1050282677090484992、 hdl:2433/140156、 ISSN 1880-2818。

外部リンク

"The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios" (International Journal of Wireless Information Networks)
Dana Mackenzie (2005). “Take it to the limit”. New Scientist 187 (2507): 38–41. ISSN 0262-4079. (preview, copy)
Coded Modulation Library, MATLABでターボ符号をシミュレートするオープンライブラリ
"Turbo Equalization: Principles and New Results", an IEEE Transactions on Communications
池田思朗「ターボ復号法の情報幾何的理解と改善の可能性」（PDF）『数理科学 500』2005年、63-69頁、 CRID 1010000781889788551。 ^{[リンク切れ]}
- 情報幾何学に基づくクラスタ変分法の解析池田思朗統計数理研究所 2004 - 2006 (科研費)

[1]

[2]

ターボ符号とは？わかりやすく解説