ターボ符号のソースを表示

'''ターボ符号'''（ターボふごう、{{lang-en-short|Turbo code}}）は、1993年に発表された高性能な[[前方誤り訂正|誤り訂正符号]]である<ref name="TC1993">{{Cite book2 |url=https://ieeexplore.ieee.org/abstract/document/397441 |title=Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1 |author=Berrou, Claude; Glavieux, Alain; Thitimajshima, Punya |year=1993 |series=Proceedings of ICC'93-IEEE International Conference on Communications |volume=2 |pages=1064-1070 |archiveurl=https://web.archive.org/web/20090227062213/http://www-elec.enst-bretagne.fr/equipe/berrou/Near%20Shannon%20Limit%20Error.pdf |archivedate=2009-02-27 |accessdate=2024-01-12|publisher=Télécom Bretagne |ref={{harvid|Berrou etal.(1993)}}}} {{要購読}}</ref>。[[第3世代移動通信システム|第三世代携帯電話]]、[[第4世代移動通信システム|第四世代携帯電話]]などの移動通信システムや、[[宇宙探査機]]での通信など、ノイズのある限られた帯域幅であっても、信頼性の高い高速通信を行う場合に使われている。

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

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

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

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

== 歴史 ==
[[1993年]]、Claude Berrou、Alain Glavieux、Punya Thitimajshima（[[:fr:Télécom Bretagne|ブルターニュ電気通信国立大学]]）が論文 "''Near Shannon Limit error-correcting coding and decoding: Turbo-codes. 1''" {{harv|Berrou etal.(1993)}} を Proceedings of IEEE International Communications Conferenceで発表した。Berrou は「80年代末に確率過程の面白さを教えてくれた G. Battail、J. Hagenauer、P. Hoeher に負うところがある」としている。また、「R. Gallager と M. Tanner はこれと非常に近い原理の符号化・復号技法を既に構想していた」とも書いているが、当時は必要な計算ができていなかった<ref name="TC1993" />。[[:en:Joachim Hagenauer|Joachim Hagenauer]]は、「[[ターボチャージャー|ターボエンジン]]の類推から、復号でおいてのみフィードバック情報が使われるため、ターボ'''符号'''という名称は不適切である。」と述べている<ref>{{Cite web|和書|url=http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf|title=Wayback MachineによるWebアーカイブ|accessdate=2018-09-23|deadurl=yes|archiveurl=https://web.archive.org/web/20150924033733/http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf|archivedate=11September 24, 2015}}</ref>。

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

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

[[ファイル:Turbo encoder.svg]]

入力ビット列 d<sub>k</sub> は C<sub>1</sub> にはそのまま入力され、C<sub>2</sub> にはインターリーバを通して並べ替えた上で入力される。出力は、入力 d<sub>k</sub> をそのまま出力する系統出力 x<sub>k</sub> と C<sub>1</sub> の出力 y<sub>1k</sub>、C<sub>2</sub> の出力 y<sub>2k</sub> がある。

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

[[ファイル:Turbo decoder.svg]]

2つの復号器の中間にインターリーバが置かれ、''DEC''<sub>1</sub> の出力におけるバースト誤りを分散させる。受信信号のうち x<sub>k</sub> はそのまま ''DEC''<sub>1</sub> に入力されるが、y<sub>1k</sub> または y<sub>2k</sub> に相当する部分は[[マルチプレクサ|デマルチプレクサ]]によって ''DEC''<sub>1</sub> か ''DEC''<sub>2</sub> に振り分けられる。

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

:<math>~x_k=(2d_k-1)+a_k</math>,
:<math>~y_k=2(Y_k-1)+b_k</math>

ここで ''a''<sub>k</sub> と ''b''<sub>k</sub> は独立ノイズ成分であり、共に分散は σ<sup>2</sup> である。''Y''<sub>k</sub> は ''y''<sub>k</sub> 符号器出力の ''k'' 番目のビットである。

冗長情報はデマルチプレックスされた後、（''y''<sub>k</sub>=''y''<sub>1k</sub> のとき）''DEC''<sub>1</sub> に送られるか（''y''<sub>k</sub>=''y''<sub>2k</sub> のとき）''DEC''<sub>2</sub> に送られる。

''DEC''<sub>1</sub> は軟判定を行う。すなわち、

:<math>\Lambda(d_k)=\log\frac{p(d_k=1)}{p(d_k=0)}</math>

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

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

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

== 軟判定手法 ==
復号器の前半部はデータストリームの各ビットについて、ある整数値を生成する。この整数はそのビットが 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人はまず自分の持つヒントに基づいてパズルを解き、それぞれの文字についてどれだけ信頼があるかを添える。そして、それぞれの結果を比較し、互いに解と信頼度を交換し、どこがどう違うのかを知る。この新たな知識に基づいて、解と信頼度を更新し、最終的に同じ解になるまでこれを繰り返すのである。

== ターボ符号の具体的応用 ==
* ターボ符号は第三世代携帯電話<ref>[https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=468 Specification #: 25.212 Multiplexing and channel coding (FDD)] 3GPP</ref>や第四世代携帯電話<ref>[https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=2426 Specification #: 36.212 Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel coding] 3GPP</ref>の規格で広く使われている。
* [[MediaFLO]]: [[クアルコム]]の携帯端末向けマルチメディア放送規格。
* [[アメリカ航空宇宙局]]（NASA）の最近のミッション（[[マーズ・リコネッサンス・オービター]]など）は、RS-ビタビ符号の代わりにターボ符号を使うようになっている。
* ブロックターボ符号と畳み込みターボ符号は無線ネットワーク規格 [[WiMAX|IEEE 802.16]] で使われている。

== ベイズ的定式化 ==
[[人工知能]]の観点では、ターボ符号は[[ベイジアンネットワーク]]でのループのある[[確率伝播]]と見なすことができる<ref>{{cite journal|和書|author=林和則 |date=2008-10 |url=https://hdl.handle.net/2433/140156 |title=確率伝搬法とその応用 (生命現象と関連した非線形問題の数理) |journal=数理解析研究所講究録 |ISSN=1880-2818 |publisher=京都大学数理解析研究所 |volume=1616 |pages=16-40 |hdl=2433/140156 |CRID=1050282677090484992 |ref=harv}}</ref>。

== 脚注 ==
{{Reflist}}

== 関連項目 ==
* [[畳み込み符号]]
* [[ビタビアルゴリズム]]
* [[前方誤り訂正]]

== 外部リンク ==
* [http://www.csee.wvu.edu/~mvalenti/documents/valenti01.pdf "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios"] (''International Journal of Wireless Information Networks'')
* {{cite journal | author=Dana Mackenzie | title=Take it to the limit | journal=New Scientist | volume=187 | issue=2507 | year=2005 | pages=38&ndash;41 | id={{ISSN|0262-4079}} }} ([http://www.newscientist.com/article.ns?id=mg18725071.400 preview], [http://geilenkotten.homeunix.org/TC_NS_09072005.pdf copy])
* [http://www.iterativesolutions.com/Matlab.htm Coded Modulation Library], [[MATLAB]]でターボ符号をシミュレートするオープンライブラリ
* [http://www.ifp.uiuc.edu/~singer/journalpapers/tuchler_2002a.pdf "Turbo Equalization: Principles and New Results"], an ''IEEE Transactions on Communications''
* {{cite journal|和書|author=池田思朗 |year=2005 |url=http://www.smapip.is.tohoku.ac.jp/~smapip/2002/Tutorial/Textbook/shiro-ikeda.pdf |format=PDF |title=ターボ復号法の情報幾何的理解と改善の可能性 |journal=数理科学 500 |pages=63-69 |CRID=1010000781889788551}} {{404|date=2024-01}}
** [https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-16700227 情報幾何学に基づくクラスタ変分法の解析] 池田 思朗 統計数理研究所 2004 - 2006 (科研費)

{{Normdaten}}
{{DEFAULTSORT:たあほふこう}}
[[Category:誤り検出訂正]]