連結されたエラー訂正コード

符号理論 において、連結符号は、内部符号と外部符号を組み合わせることによって得られる誤り訂正符号の一種です。これらは、ブロック長の増加に伴って誤り確率が指数関数的に減少し、かつ復号の複雑さが多項式時間である符号を見つけるという問題の解決策として、 1966年にデイブ・フォーニーによって考案されました。^{[ 1 ]} 連結符号は、1970年代に宇宙通信で広く使用されるようになりました。

チャネル符号化の分野は、与えられた通信チャネル上で可能な限り高速なデータストリームを送信し、受信側で、与えられた技術で実装可能な符号化および復号化アルゴリズムを用いて、元のデータを確実に復号化することに関係している。

シャノンのチャネル符号化定理は、多くの一般的なチャネルにおいて、あらゆる速度でデータを確実に送信できるチャネル符号化方式が存在することを示している。${\displaystyle R}$一定のしきい値未満${\displaystyle C}$これは、与えられたチャネルのチャネル容量と呼ばれます。実際、ブロック長が長くなるにつれて、復号エラーの確率は指数関数的に減少します。${\displaystyle N}$符号化方式の は無限大に及ぶ。しかし、送信されたすべての可能な符号語の尤度を単純に計算する単純な最適復号方式の複雑さは、 とともに指数関数的に増加する。${\displaystyle N}$そのため、そのような最適なデコーダーはすぐに実現不可能になる。

デイブ・フォーニーは博士論文の中で、連結符号を用いることで、容量以下のあらゆるデータレートにおいて、指数関数的に減少する誤り確率を実現できること、そして復号の複雑さは符号ブロック長に対して多項式的にしか増加しないことを示した。

C を[ n , k , d ] コード、すなわち長さn、次元k、最小ハミング距離d、レートr = k / nのブロックコード_とし、アルファベットA上で定義する。

${\displaystyle C_{in}:A^{k}\rightarrow A^{n}}$

C _{out を}、 | B | = | A | ^k個の記号を持つアルファベットB上の[ N , K , D ] コードとする。

${\displaystyle C_{out}:B^{K}\rightarrow B^{N}}$

内部コードC _{in は}、| A | ^k = | B | 個の可能な入力のうちの 1 つを受け取り、A上のnタプルにエンコードし、送信し、| B | 個の可能な出力のうちの 1 つにデコードします。これを、アルファベットBから 1 つのシンボルを送信できる (スーパー) チャネルとみなします。このチャネルをN回使用して、 C _outのコードワード内のN個のシンボルをそれぞれ送信します。C _out (外部コード) とC _in (内部コード)の連結をC _{outと表記します。}${\displaystyle \circ }$C_は、アルファベットA上の長さNnのコードである。^{[ 1 ]}

${\displaystyle C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}}$

これは、各入力メッセージm = ( m ₁ , m ₂ , ..., m _K ) をコードワード ( C _in ( m ' ₁ ), C _in ( m ' ₂ ), ..., C _in ( m ' _N )) にマッピングします。ここで、( m ' ₁ , m ' ₂ , ..., m ' _N ) = C _out ( m ₁ , m ₂ , ..., m _K ) です。

このアプローチの重要な洞察は、C inが_最尤法を使用して復号され（したがって、長さの増加に伴って誤り確率が指数的に減少する）、C _{out が}長さN = 2 ^nrのコードで、 Nの多項式時間で復号できる場合、連結コードはその結合長n 2 ^nr = O ( N ⋅log( N ))の多項式時間で復号でき、 C _{in の}復号複雑度が指数関数的であっても、誤り確率が指数関数的に減少するということです。^{[ 1 ]}これについては、「連結コードの復号」のセクションでさらに詳しく説明します。

上記の連結の一般化では、N個の可能な内部コードC _in、iがあり、C _outのコードワードのi番目のシンボルは、 i番目の内部コードを使用して内部チャネルを介して送信されます。Justesenコードは、外部コードがReed–Solomon コードである一般化された連結コードの例です。

1.連結コードCの_出力の距離${\displaystyle \circ }$C_は少なくともdDであり、つまりD ' ≥ dDの [ nN , kK , D ' ] コードである。

証明： 2つの異なるメッセージm ¹ ≠ m ² ∈ B ^Kを考える。2つのコードワード間の距離を Δ で表す。すると

${\displaystyle \Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D.}$

したがって、符号語C _out ( m ¹ ) とC _out ( m ^{2 ) の}N個のシンボルのシーケンスが異なる位置は少なくともD個存在する。これらの位置( iと表記) については、次のようになる。

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})_{i}),C_{in}(C_{out}(m^{2})_{i}))\geq d.}$

したがって、アルファベットAから取得したn ⋅ N個のシンボルのシーケンスには、少なくともd ⋅ D 個の位置があり、その中で 2 つのコードワードが異なっている。

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})),C_{in}(C_{out}(m^{2})))\geq dD.}$

2. C _outとC _{in が}線形ブロックコードである場合、C _{out は}${\displaystyle \circ }$C _inもまた線形ブロックコードである。

この性質は、 C _outとC _inの生成行列を用いて連結されたコードの生成行列を定義するという考え方に基づいて容易に示すことができる。

連結符号の復号アルゴリズムの自然な概念は、まず内側の符号を復号し、次に外側の符号を復号することです。アルゴリズムが実用的であるためには、最終ブロック長に対して多項式時間である必要があります。外側の符号に対して多項式時間で一意の復号アルゴリズムが存在すると仮定します。次に、内側の符号に対して多項式時間で復号するアルゴリズムを見つける必要があります。ここで多項式実行時間とは、実行時間が最終ブロック長に対して多項式であることを意味します。主なアイデアは、内側ブロック長を外側の符号のサイズに対して対数に選択すると、内側の符号の復号アルゴリズムは内側ブロック長に対して指数時間で実行され、指数時間ではあるが最適な最尤復号器（MLD）を内側の符号に使用できるということです。

具体的には、デコーダへの入力をベクトルy = ( y ₁ , ..., y _N ) ∈ ( A ⁿ ) ^Nとします。すると、復号アルゴリズムは2段階のプロセスになります。

1. 内部コードC _inの MLD を使用して、内部コードワードのセットy ' = ( y ' ₁ , ..., y ' _N ) を再構築します。ここで、y ' _i = MLD _{C in} ( y _i )、1 ≤ i ≤ N です。
2. C_{出力に対して、} y 'に対して独自の復号アルゴリズムを実行します。

さて、最初のステップの時間計算量はO ( N ⋅exp( n )) であり、ここでn = O (log( N )) は内側のブロック長です。言い換えれば、外側のブロック長Nに関してN ^{O (1)} (つまり多項式時間) となります。ステップ 2 の外側の復号アルゴリズムは多項式時間で実行されると仮定されているため、全体の復号アルゴリズムの計算量も多項式時間となります。

1971年のマリナー火星探査機ミッションでは既に単純な連結方式が実​​装されていたが、^{[ 5 ]}連結符号は1977年に2機の宇宙探査機を打ち上げたボイジャー計画で深宇宙通信に定期的に使用されるようになった。^{[ 6 ]}それ以来、連結符号は効率的な誤り訂正符号化の主力となり、少なくともターボ符号やLDPC符号が発明されるまではそうであった。^{[ 5 ] [ 6 ]}

通常、内側のコードはブロックコードではなく、制約長が短いソフト決定畳み込みビタビ復号コードです。 ^{[ 7 ]} 外側のコードには、より長いハード決定ブロックコード、多くの場合、8ビットシンボルのリード・ソロモンコードが使用されます。 ^{[ 1 ] [ 5 ]} シンボルサイズが大きいと、外側のコードはチャネルの劣化によって発生する可能性のあるエラーバーストに対してより堅牢になり、また、畳み込みコード自体の誤った出力がバースト的であるためです。^{[ 1 ] [ 5 ]}通常、2つのコードの間にインターリーブ層が追加され、エラーバーストがより広い範囲に分散されます。^{[ 5 ]}

内側のビタビ畳み込み符号と外側のリード・ソロモン符号の組み合わせ（RSV符号として知られる）は、ボイジャー2号で初めて使用され、^{[ 5 ] [ 8 ]}宇宙分野内外で広く普及した構成となった。今日でも、DVB-Sデジタルテレビ放送規格などの衛星通信で特に使用されている。^{[ 9 ]}

より広い意味では、2つ以上のコードの任意の（直列）組み合わせは連結コードと呼ばれることがあります。たとえば、DVB-S2規格では、高効率LDPCコードが代数的外側コードと組み合わされて、LDPCコード固有のエラーフロアによって内側コードから残った耐性エラーを除去します。^{[ 10 ]}

コンパクトディスク（CD）でも単純な連結方式が用いられており、異なるサイズの2つのリード・ソロモン符号の間にインターリーブ層を設けることで、エラーを様々なブロックに分散させている。

上記の説明は、現在では直列連結符号と呼ばれるものについて述べたものです。 1993年に初めて説明されたターボ符号は、2つの畳み込み符号を並列に連結し、2つの符号の間にインターリーバを挟み、符号間で情報をやり取りする反復デコーダを備えています。^{[ 6 ]}この設計は、これまで考案されたどの連結符号よりも優れた性能を持っています。

しかし、ターボ符号の重要な側面は、反復復号方式です。反復復号は、より高い符号化利得を達成するために、直列連結畳み込み符号（SCCC）など、直列連結にも適用されています。反復復号の初期形態は、ガリレオ探査機の「ガリレオ符号」で2～5回の反復で実装されました。^{[ 5 ]}

• ギルバートとヴァルシャモフが結ばれる
• ジャステセンコード
• シングルトンバウンド
• ジャブロフ行き

• Shu Lin、Daniel J. Costello Jr. (1983).エラー制御符号化：基礎と応用. Prentice Hall . pp. 278–280 . ISBN  978-0-13-283796-5。
• FJ MacWilliams ; NJA Sloane (1977).誤り訂正符号の理論. North-Holland. pp. 307–316 . ISBN  978-0-444-85193-2。

• Dave Forney (編). 「連結コード」 . Scholarpedia .
• バッファロー大学 コーディング理論講義ノート – アトリ・ルドラ博士