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

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

チャネル符号化の分野は、特定の通信チャネルを介して可能な限り最高の速度でデータ ストリームを送信し、特定のテクノロジで実装可能な符号化および復号化アルゴリズムを使用して、受信側で元のデータを確実に復号化することに関係しています。

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

デイブ・フォーニーは博士論文で、連結コードを使用することで、容量未満のすべてのデータ レートで指数関数的に減少するエラー確率を達成でき、復号化の複雑さはコード ブロックの長さに応じて多項式的にのみ増加することを示しました。

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

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

C _{out を}アルファベットB上の[ N , K , D ] コードとし、| B | = | A | ^k個のシンボルを使用します。

${\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 ∘ C _{in と}表記され、アルファベット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 コードは、外部コードがリード・ソロモン コードである一般化された連結コードの例です。

1.連結コードC _out ∘ C _inの距離は少なくとも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個のシンボルのシーケンスには、2つのコードワードが異なるd⋅D個の位置が少なくとも存在し、したがって

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

2. C _outとC _{in が}線形ブロック符号である場合、C _out ∘ 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 _outの固有のデコード アルゴリズムをy 'で実行します。

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

上記の復号化アルゴリズムは、最大dD /4 個までのエラーをすべて訂正するために使用できます。最小距離復号化を使用すると、外部デコーダーは、エラーがD /2 個未満のシンボルy ' _iのすべての入力y ' を訂正できます。同様に、内部コードは、 d /2 個未満の内部シンボルにエラーがある場合に、入力 y i を確実に訂正できます。_{したがって}、内部復号化後に外部シンボルy ' _iが不正確になるためには、少なくともd /2 個の内部シンボルにエラーがあった必要があり、外部コードが失敗するには、少なくともD /2 個の外部シンボルでこれが発生していなければなりません。したがって、連結コードが失敗するには、誤って受信される必要がある内部シンボルの総数は、少なくともd /2⋅ D /2 = dD /4 である必要があります。

このアルゴリズムは、内部コードが異なる場合（例えば、ジャステセンコード）にも機能します。フォーニーによって開発された一般化最小距離アルゴリズムは、最大dD /2のエラーを訂正するために使用できます。^[2] これは、内部コードの消失情報を使用して外部コードのパフォーマンスを向上させるもので、ソフト決定復号法を使用するアルゴリズムの最初の例でした。^{[3] [4]}

単純な連結方式は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コード固有のエラーフロアのために内部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)。誤り訂正符号の理論。ノースホランド。pp. 307–316。ISBN 978-0-444-85193-2。

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