Skip to content
検索結果に戻る

反復復号化によるターボ符号化

提唱者
Claude Berrou, Alain Glavieux, and Punya Thitimajshima
年
1993
種類
iterative error-correcting code
系統
Coding theory

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

1993年にBerrou、Glavieux、Thitimajshimaによって導入されたターボ符号は、誤り訂正符号化の歴史における画期的な成果である。シャノン限界(信頼性通信の理論的境界)に0.5 dB以内の性能を達成しており、これは実用的な複雑さで以前は不可能と考えられていた偉業である。ターボ符号は、インターリーバを備えた畳み込み符号を連結し、信念伝播による反復復号化を用いる。3G(UMTS)で採用され、LDPC符号と共に4G/5Gシステムでも依然として重要である。

手法の背後にある直感

標準的な誤り訂正符号は、データを保護するために冗長性を付加するが、通常は複雑な復号化(例:符号長に対して指数関数的に増大する最尤復号)を必要とする。ターボ符号はこの問題を逆転させる。単純な符号器(2つ以上の畳み込み符号)を並列に使用し、擬似乱数インターリーバで分離し、復号器間で情報を反復的に交換させる。インターリーバは、一方の符号にとって困難な誤りが、置換により他方の符号にとっては容易になることを保証するため、反復的な改善が真のメッセージに収束する。この「ターボ効果」(名称の由来)は、単一パス復号化よりも指数関数的に優れた性能を生み出し、理論的限界に迫る。

歴史学

ターボ符号は1993年のICCで発表され、シャノン限界に近い性能で符号理論コミュニティに衝撃を与えた。1990年代後半の3G(UMTS、cdma2000)採用の主要な推進力となった。ターボ符号の理解は、反復復号化のより広範な理論と、古典的符号(例:ハミング符号が反復構造を持つことが示された)の理解のルネサンスにつながった。2000年代には、LDPC符号(Gallager、1962年再発見)が同等の性能とより単純なアーキテクチャを持つ競合相手として登場した。極性符号(Arikan、2009年)は、限界において理論的な最適性を提供した。最新の規格(5G NR)はこれら3つのファミリーすべてをサポートしている。ターボ符号はレガシーであるが、広く実装されている。

使うべき場面

ターボ符号は、深層フェージングまたはノイズの多いチャネルで、強力な誤り訂正が必要な場合(例:衛星、深宇宙、水中)に優れている。ビット誤り率(BER)が10^-6未満とクリティカルであり、遅延が反復復号化(数ミリ秒)を許容できる場合にターボ符号化を使用する。ターボ符号は、レートクリティカルなアプリケーションや非常に短いパケット(インターリーバと復号器の状態がオーバーヘッドを支配する)にはあまり適さない。LDPC符号や極性符号(わずかに優れた性能、より単純)の台頭により、ターボ符号は多くの新しい規格ではレガシーとなっているが、互換性レイヤーでは依然として使用されている。

限界と注意点

  • 反復復号化は遅延を導入する(長いインターリーバで数十ミリ秒)
  • 性能はインターリーバ設計に敏感であり、選択を誤るとターボ効果が損なわれる
  • 非常に低いBERでは誤りがクラスターに伝播する傾向がある(エラーフロア)。緩和には符号の調整が必要
  • 復号化の複雑さは情報長に比例する(指数関数的ではないが、依然として高い)
  • 短いパケットはインターリーバのオーバーヘッドと収束に必要な反復深度の不足に悩まされる

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 実用的な複雑さでシャノン限界に0.5 dB以内の性能
  • 古典的な符号とは異なり、閾値現象なしに広範囲の信号対雑音比で良好に機能する
  • 反復復号化は反復ごとに性能を向上させ、反復回数によるレート制御を可能にする
  • 分離可能な設計:任意の畳み込み符号を使用でき、柔軟性を可能にする
  • インターリーバによる分散により、バースト誤りに対して堅牢

応用

  • 3G/4Gセルラー(UMTS、LTE):ターボ符号によるシャノン限界に近い性能を提供する上り下りトラフィックチャネル
  • 衛星通信:深宇宙ミッション(例:火星探査車)では、極端なノイズからの信頼性の高いデータ回復のためにターボ符号を使用
  • 軍事用秘匿通信:妨害を受けやすい環境での強力な誤り訂正による暗号化データ伝送
  • 無線センサーネットワーク:低電力ノードは、信頼性の高いマルチホップ転送のために短いターボ符号を使用
  • 医療テレメトリ:ノイズの多い無線リンクを介してクリティカルな患者データを送信する生体デバイス

使い方

使い方

1

情報ビットは、同一の畳み込み符号器(RSC:再帰的系統的畳み込み符号)を使用して2つの並列符号語に符号化される。

2

2つの符号器の間で、擬似乱数ビットインターリーバが情報系列を置換する。これにより、同じ情報に対して2つの符号語が異なる重み分布を持つことが保証される。

3

符号化されたビット(両方の符号器からの系統ビットとパリティビット)は、ノイズによって劣化されたチャネルを介して送信される。

4

受信側では、ソフト入力ソフト出力(SISO)復号器が反復処理を行う。復号器1は、受信信号と復号器2からの外部情報を使用して推定値を改善する。復号器2も同様に行う。逆インターリーバ/インターリーバが復号器間で情報を中継する。

5

固定回数の反復(例:8〜20回)の後、尤度比の閾値処理によって最終的なハード判定が行われる。収束は「ターボクリフ」で追跡できる。SNRが反復が収束を開始する閾値を超えると、性能は急激に低下する。

よくある落とし穴

  • 決定論的または短すぎるインターリーバの使用。擬似ランダム性は反復利得に不可欠
  • 固定反復回数が最適であると仮定すること。性能はSNRによって変化するため、適応反復回数の方が優れている
  • エラーフロアを無視すること。ターボ符号は閾値(ターボクリフ)を示す可能性があり、その下では性能が急速に低下する
  • 非常に短い情報ブロック(100ビット未満)にターボ符号を適用すること。相対的なオーバーヘッドが法外になる
  • 反復復号化におけるフィードバック遅延を考慮しないこと。復号器間のコヒーレントなタイミングが必要

よくある質問

ターボ符号の「ターボ」とは何ですか?

この名前は、各復号器が次の復号器の信号を「ブースト」することに似た、反復復号化プロセスに由来する。反復ごとの指数関数的な性能向上は、ターボ効果と呼ばれることもある。ターボチャージャーとは文字通り関係ない。

インターリーバはなぜそれほど重要なのですか?

インターリーバは、2番目の復号器がエラーパターンを見る前に、最初の復号器からのエラーパターンの相関を破壊する。それがないと、両方の復号器が繰り返し同じ間違いを犯すことになる。優れたインターリーバは、一方の復号器からのエラーがランダムに分散されることを保証し、2番目の復号器に新鮮な視点を与え、生産的な反復を可能にする。

ターボクリフとは何ですか?

ターボ符号は急激な閾値を示す。クリティカルなSNRを下回ると、反復復号化は収束に失敗し、BERは不良となる。閾値を超えると、BERは急激に低下する。これがターボクリフである。システム設計では、SNRはクリティカルポイントを安全に上回る必要がある。そのすぐ下で動作すると、SNRが良いように見えても壊滅的な失敗を引き起こす。

いくつの反復が必要ですか?

典型的なターボ復号器は8〜20回の反復を使用する。反復回数が増えると性能は向上するが、遅延も増加する。高SNRでは、数回の反復で十分である(収束は速い)。低SNRでは、より多くの反復が必要である。適応反復(収束を確認し、完了したら早期に停止する)は、遅延と性能のバランスをとる。

関連する手法

参考文献

  1. Berrou, C., Glavieux, A., & Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: Turbo-codes. In Proceedings of the IEEE International Conference on Communications (ICC), 1064-1070.

    DOI 文献を開く
    コピーしました。
  2. Richardson, T. J., & Urbanke, R. L. (2002). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    DOI 文献を開く
    コピーしました。