畳み込み符号

電気通信において、畳み込み符号は、ブール多項式関数をデータストリームにスライド適用することでパリティシンボルを生成する誤り訂正符号の一種です。このスライド適用は、エンコーダによるデータへの「畳み込み」を表しており、これが「畳み込み符号化」という用語の由来となっています。畳み込み符号のスライド特性により、時間不変トレリスを用いたトレリス復号が容易になります。時間不変トレリス復号を用いることで、畳み込み符号を妥当な計算量で最尤ソフトデシジョン復号することが可能になります。

畳み込み符号の大きな利点の1つは、経済的な最尤ソフトデシジョン復号を実行できることです。これは、一般的に時間変動トレリスで表現され、そのため通常はハードデシジョン復号される古典的なブロック符号とは対照的です。畳み込み符号は、基本符号化率とエンコーダの深さ（またはメモリ）によって特徴付けられることがよくあります。${\displaystyle [n,k,K]}$基本コードレートは通常次のように表されます。${\displaystyle k/n}$ここで、kは入力データの生データレート、nは出力チャネル符号化ストリームのデータレートです。 チャネル符号化によって入力ビットに冗長性が挿入されるため、 kはnより小さくなります。メモリはしばしば「制約長」Kと呼ばれ、出力は現在の入力と以前の入力の関数です。${\displaystyle K-1}$入力。^{[ 1 ]}深さは、多項式内のメモリ要素vの数、またはエンコーダの最大可能な状態数（通常：$2v$)

畳み込み符号は連続的であるとよく言われます。しかし、実際の畳み込み符号化のほとんどはデータブロックに対して行われるため、畳み込み符号は連続的というよりは、ブロック長が任意であると言うこともできます。畳み込み符号化されたブロック符号は、通常、終端符号を採用します。畳み込み符号のブロック長が任意であるという点は、一般的に代数的性質によって決定される固定ブロック長を持つ古典的なブロック符号とは対照的です。

畳み込み符号の符号化率は、シンボルパンクチャリングによって変更されるのが一般的です。例えば、「マザー」符号化率を持つ畳み込み符号は、${\displaystyle n/k=1/2}$例えば、より高い割合で穿孔される可能性がある。${\displaystyle 7/8}$コードシンボルの一部を送信しないだけで済みます。パンクド畳み込み符号の性能は、一般的に送信されるパリティの量に比例して向上します。畳み込み符号は、経済的なソフトデシジョン復号が可能であること、またブロック長や符号化率の柔軟性が高いことから、デジタル通信で非常に人気があります。

畳み込み符号は1955年にピーター・エリアスによって導入されました。畳み込み符号は、計算量と遅延を犠牲にすれば、任意の品質で復号できると考えられていました。1967年、アンドリュー・ビタビは、時間不変のトレリスベースの復号器（ビタビアルゴリズム）を用いることで、畳み込み符号を妥当な計算量で最尤復号できることを明らかにしました。その後、 BCJR復号アルゴリズムなど、他のトレリスベースの復号アルゴリズムが開発されました。

再帰的系統的畳み込み符号は、 1991年頃にクロード・ベルーによって発明されました。これらの符号は、ターボ符号などの連結符号の処理を含む反復処理に特に有用であることが証明されました。^{[ 2 ]}

「畳み込み」という用語を用いると、古典的な畳み込み符号は有限インパルス応答（FIR）フィルタとみなすことができ、再帰的な畳み込み符号は無限インパルス応答（IIR）フィルタとみなすことができる。

畳み込み符号は、デジタルビデオ、ラジオ、モバイル通信（GSM、GPRS、EDGE、3Gネットワ​​ーク（3GPPリリース7まで）^{[ 4 ] [ 5 ]}など） 、衛星通信^{[ 6 ]}など、数多くのアプリケーションで信頼性の高いデータ転送を実現するために広く使用されています。これらの符号は、特にリード・ソロモン符号などのハードデシジョン符号と連結して実装されることがよくあります。ターボ符号が登場する前は、このような構成が最も効率的で、シャノン限界に最も近いものでした。

畳み込み符号化でデータを処理するには、まずk 個のメモリ レジスタを用意し、それぞれに 1 ビットの入力値を保持します。特に指定がない限り、すべてのメモリ レジスタは 0 の値で開始します。エンコーダにはn 個のモジュロ 2加算器(モジュロ 2 加算器は、単一のブールXOR ゲートで実装でき、論理は0+0  =  0、0 + 1  =  1、1 + 0  =  1、1 + 1  =  0です) と、n個の生成多項式(各加算器に 1 つずつ) があります (下図を参照)。入力ビットm ₁は、最も左のレジスタに入力されます。生成多項式と残りのレジスタの既存の値を使用して、エンコーダはn個のシンボルを出力します。これらのシンボルは、目的のコード レートに応じて、送信またはパンクチャリングされます。次に、すべてのレジスタの値を右にビット シフトし( m _{1 は}m ₀に移動し、m _{0 は}m ₋₁に移動します)、次の入力ビットを待ちます。入力ビットが残っていない場合、エンコーダはすべてのレジスタがゼロ状態に戻るまで（フラッシュビット終了まで）シフトを続けます。

下の図は、制約長 (k) が 3 のレート 1/3 (m/n) エンコーダです。_{生成多項式は G1 = (1,1,1)、G2} = ( 0,1,1 )、G3 = ( 1,0,1 ) です。_{したがって}、出力ビットは次の_ように (mod 2) 計算されます。

n ₁ = m ₁ + m ₀ + m ₋₁

n ₂ = m ₀ + m ₋₁

n ₃ = m ₁ + m ₋₁。

畳み込み符号には、体系的なものと非体系的なものがある。

• 体系的に、エンコード前にメッセージの構造を繰り返す
• 非体系的な変化が初期構造に影響を与える

非系統的畳み込み符号は、ノイズ耐性が優れているため、より普及しています。これは畳み込み符号の自由距離に関係しています。^{[ 7 ]}

• 
  非系統的畳み込み符号の簡単な例。
• 
  体系的な畳み込み符号の簡単な例。

上の図のエンコーダは非再帰型エンコーダです。以下は再帰型エンコーダの例で、フィードバック構造を備えています。

この例のエンコーダは、入力データが出力シンボル（出力2）にも使用されているため、体系的です。出力シンボルに入力データが含まれていないコードは、 非体系的と呼ばれます。

再帰コードは一般的に体系的であり、逆に非再帰コードは一般的に非体系的である。これは厳密な要件ではないが、一般的な慣習である。

図2のエンコーダの例は8状態エンコーダです。これは、3つのレジスタによって8つのエンコーダ状態（2³）が生成されるためです^。対応するデコーダトレリスも通常は8つの状態を使用します。

再帰的系統畳み込み符号（RSC符号）は、ターボ符号での利用により普及が進んでいる。再帰的系統符号は、擬似系統符号とも呼ばれる。

その他のRSCコードと適用例は以下のとおりです。

LDPC符号の実装や、直列連結畳み込み符号（SCCC）の内部構成符号として有用です。

SCCCや多次元ターボコードに役立ちます。

衛星通信などの用途における低誤り率ターボ符号の構成符号として有用です。また、SCCC外部符号としても適しています。

畳み込みエンコーダは、入力ストリームとエンコーダのインパルス応答との畳み込み演算を実行するため、このように呼ばれています。

${\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{ik}=(x*h^{j})[i],}$

ここで、 xは入力シーケンス、y ^jは出力jからのシーケンス、h ^jは出力jのインパルス応答であり、${\displaystyle {*}}$畳み込みを表します。

畳み込みエンコーダは、離散線形時不変システムです。エンコーダの各出力は、生成多項式と密接に関連する独自の伝達関数によって記述できます。インパルス応答は、Z変換を介して伝達関数と結び付けられます。

最初の（非再帰型）エンコーダの伝達関数は次のとおりです。

• ${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{3}(z)=1+z^{-2}.\,}$

第2（再帰型）エンコーダの伝達関数は以下のとおりです。

• ${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\,}$
• ${\displaystyle H_{2}(z)=1.\,}$

mを次のように定義する。

${\displaystyle m=\max _{i}\operatorname {polydeg} (H_{i}(1/z))\,}$

ここで、任意の有理関数に対して${\displaystyle f(z)=P(z)/Q(z)\,}$、

${\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}$。

すると、mは多項式の次数の最大値である。

${\displaystyle H_{i}(1/z)\,}$制約長は次のように定義される。${\displaystyle K=m+1\,}$例えば、最初の例では制約の長さは3で、2番目の例では制約の長さは4です。

畳み込みエンコーダは有限状態機械です。n個のバイナリセルを持つエンコーダは^2ⁿ個の状態を持ちます。

エンコーダ（上の図1に示す）の左側のメモリセル（m ₀）に「1」、右側のメモリセル（m ₋₁）に「0」が入っているとします。（m ₁は現在の値を表すため、実際にはメモリセルではありません）。このような状態を「10」とします。入力ビットに応じて、エンコーダは次のターンで「01」状態または「11」状態のいずれかに変換できます。すべての遷移が可能であるわけではないことがわかります（たとえば、デコーダは「10」状態から「00」に変換したり、「10」状態にとどまったりすることはできません）。

考えられるすべての遷移は、以下のように示すことができます。

実際のエンコードされたシーケンスは、このグラフ上のパスとして表現できます。有効なパスの一例を赤色で示します。

この図は復号化の考え方を示しています。受信したシーケンスがこのグラフに適合しない場合、それはエラーを含むシーケンスであり、グラフに適合する最も近い正しいシーケンスを選択する必要があります。実際の復号化アルゴリズムはこの考え方を利用しています。

自由距離^{[ 8 ]} ( d )は、異なる符号化シーケンス間の最小ハミング距離です。畳み込み符号の訂正能力( t )は、その符号によって訂正できるエラーの数です。これは次のように計算できます。

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}$

畳み込み符号はブロックを使用せず、連続したビットストリームを処理するため、 tの値は互いに比較的近い位置にあるエラーの数に適用されます。つまり、t個のエラーのグループが複数存在しても、それらが比較的離れていれば通常は修正可能です。

自由距離は、畳み込み復号器の出力における誤った「バースト」の最小長として解釈できます。エラーが「バースト」として現れるという事実は、内部に畳み込み符号を持つ連結符号を設計する際に考慮する必要があります。この問題に対する一般的な解決策は、畳み込み符号化の前にデータをインターリーブすることです。これにより、外側のブロック（通常はリード・ソロモン符号）がほとんどのエラーを訂正できるようになります。

畳み込み符号を復号するためのアルゴリズムはいくつか存在する。kの値が比較的小さい場合、ビタビアルゴリズムは最尤推定性能を提供し、並列処理性に優れているため、広く用いられている。そのため、ビタビ復号器はVLSIハードウェアやSIMD命令セットを備えたCPU上のソフトウェアで容易に実装できる。

制約長が長い符号は、いくつかの逐次復号アルゴリズムのいずれかを用いてより実用的に復号できます。その中でもファノアルゴリズムが最もよく知られています。ビタビ復号とは異なり、逐次復号は最尤復号ではありませんが、制約長が長くなっても複雑さはわずかにしか増加しないため、強力な長制約長符号を使用できます。このような符号は、 1970年代初頭の木星・土星探査計画であるパイオニア計画で使用されましたが、その後、より短いビタビ復号符号に取って代わられました。これらの符号は通常、ビット誤り率曲線を急勾配にし、極めて低い残留未検出誤り率を実現する大きなリード・ソロモン誤り訂正符号と連結されます。

ビタビ復号アルゴリズムと逐次復号アルゴリズムはどちらも、最も可能性の高い符号語を構成するビットというハード判定を返します。ソフト出力ビタビアルゴリズムを使用すると、各ビットに近似的な信頼度尺度を追加できます。BCJRアルゴリズムを使用すると、各ビットの最大事後確率（MAP）ソフト判定を取得できます。

実際、科学研究で得られた定義済みの畳み込み符号構造は、産業界でも利用されています。これは、致命的な畳み込み符号（より多くのエラーを引き起こす符号）を選択できる可能性に関係しています。

特に人気のあるビタビ復号畳み込み符号は、少なくともボイジャー計画以来使用されており、制約長Kが7、レートrが1/2である。^{[ 13 ]}

マーズ・パスファインダー、マーズ・エクスプロレーション・ローバー、土星探査機カッシーニは、 K =15、レート1/6を使用しています。このコードは、 より単純なコードよりも約2dB優れています。${\displaystyle K=7}$（ボイジャー探査機のミッションコードと比較して）復号化の複雑さが256倍かかるコード。

GSMでは、エラー訂正技術として、制約長2、レート1/2の畳み込み符号が使用されている。 ^{[ 14 ]}

任意の符号化率を持つ畳み込み符号は、多項式選択に基づいて設計できますが^{[ 16 ]}、実際には、必要な符号化率を達成するためにパンクチャリング手順がよく使用されます。パンクチャリングは、「基本」低レート（例えば1/ n ）符号からm / nレート符号を作成するために使用される技術です。これは、エンコーダ出力の一部のビットを削除することによって実現されます。ビットはパンクチャリング行列に従って削除されます。以下のパンクチャリング行列が最もよく使用されます。

例えば、上記の表から適切な行列を用いてレート2/3のコードを作成する場合、基本エンコーダの出力を取得し、最初の分岐の最初のビットと2番目の分岐のすべてのビットを送信する必要があります。具体的な送信順序は、それぞれの通信規格によって定義されます。

パンクチャード畳み込み符号は、例えばインテルサットシステムやデジタルビデオ放送など、衛星通信で広く使用されています。

穴あき畳み込み符号は「穿孔型」とも呼ばれる。

単純なビタビ復号畳み込み符号は、ターボ符号に取って代わられつつあります。ターボ符号は、反復型の短い畳み込み符号の新しいクラスであり、同じ性能を得るために必要な長い畳み込み符号に対するビタビアルゴリズムよりもはるかに少ない復号複雑度で、シャノンの定理によって課される理論的な限界に非常に近い値を実現します。外側の代数符号（例えば、リード・ソロモン符号）との連結により、ターボ符号設計に内在するエラーフロアの問題に対処できます。

• 量子畳み込み符号

•  この記事は、連邦規格1037C（一般調達局）からのパブリックドメイン資料を組み込んでいます。 2022年1月22日にオリジナルからアーカイブされました。

• デイビッド・JC・マッケイ著のオンライン教科書『情報理論、推論、学習アルゴリズム』では、第48章で畳み込み符号について解説している。
• エラー訂正コード（ECC）のページ
• Matlabの説明
• より良いデジタル通信のための畳み込みデコーダの基礎
• 畳み込み符号（MIT）
• 情報理論と符号化（イルメナウ工科大学）Wayback Machineに2017年8月30日にアーカイブされた文書では、48ページで畳み込み符号について論じている。