畳み込み符号

畳み込み符号（たたみこみふごう、英: Convolutional code）は、電気通信における誤り訂正符号の一種である。m-ビットの情報シンボル（すなわち m-ビット文字列）が符号化によって n-ビットシンボルに変換され、このとき m/n を符号レートと呼ぶ（n ≥ m）。また、その変換は最近の k 個の情報シンボルに関する関数となっており、k をその符号の拘束長（constraint length）と呼ぶ。

畳み込み符号が使われる場面

畳み込み符号は、デジタルラジオ、携帯電話、人工衛星リンク、Bluetooth などの実装について、性能を向上させるためによく使われる。

畳み込み符号化

ファイル:Convol encoder nrj.png

図1. レート 1/3、拘束長 3 の非再帰的非系統的畳み込みエンコーダ

データを畳み込み符号化するには、それぞれが 1 入力ビットを保持する k 個のメモリレジスタを用意する。特に指定されない限り、各メモリレジスタの初期値は 0 である。エンコーダには、n 個の 2 を法とする加算器と n 個の生成多項式があり、1つの生成多項式が1つの加算器に対応している。入力ビット m₁ は左端のレジスタに格納される。そして、各メモリレジスタの値に対して生成多項式を適用して n ビットの出力をする。次に、全レジスタ値を右方向にビットシフトし（m₁ を m₀ に移し、m₀ を m_-1 に移す）、次の入力ビットを待つ。新たな入力ビットがない場合、エンコーダは全てのレジスタがゼロ状態になるまで出力を続ける。

右図はレート 1/3 (m/n) で拘束長 (k) が 3 のエンコーダを示している。生成多項式は、G₁ = (1,1,1)、G₂ = (0,1,1)、G₃ = (1,0,1) である。従って、出力ビットは次のように計算される（2 を法とする）。

• n₁ = m₁ + m₀ + m_-1
• n₂ = m₀ + m_-1
• n₃ = m₁ + m_-1.

再帰的符号と非再帰的符号

ファイル:Convol encoder rj.png

図2. レート 1/2、拘束長 4 の再帰的系統的畳み込みエンコーダ

図1のエンコーダは「非再帰的」エンコーダである。図2に示したのは、再帰的な例である。

この図を見て判るとおり、「出力2」として符号化対象の入力がそのまま出力されている。このような符号は組織的(systematic)であるといい、そうでない符号を非組織的(non-systematic)であるという。

再帰的符号は常に系統的であり、逆に非再帰的符号は非系統的であることが多い。これは絶対条件ではないが、一般にそのようになっていることが多い。

インパルス応答、伝達関数、拘束長

畳み込みエンコーダが「畳み込み」と呼ばれるのは、入力ストリームに対してエンコーダの「インパルス応答」による「畳み込み」を行うからである。エンコーダのインパルス応答は次の式で表される。

• [math]y_i^j=\sum_{k=0}^{\infty} h^j_k x_{i-k},[/math]

ここで、[math]x\,[/math] は入力列、[math]y^j\,[/math] は [math]j\,[/math] 番目の出力列、[math]h^j\,[/math] は [math]j\,[/math] 番目の出力のインパルス応答である。

畳み込みエンコーダは、離散線型時不変系である。エンコーダの各出力は固有の伝達関数で表され、それは生成多項式と密接に関連している。インパルス応答は、Z変換を介して伝達関数と関連付けられる。

図1の非再帰的エンコーダの伝達関数は次の通りである。

• [math]H_1(z)=1+z^{-1}+z^{-2}\,[/math]
• [math]H_2(z)=z^{-1}+z^{-2}\,[/math]
• [math]H_3(z)=1+z^{-2}\,[/math]

図2の再帰的エンコーダの伝達関数は次の通りである。

• [math]H_1(z)=\frac{1+z^{-1}+z^{-3}}{1+z^{-2}+z^{-3}}\,[/math]
• [math]H_2(z)=1\,[/math]

[math] m \,[/math] を次のように定義する。

• [math] m = max_i polydeg (H_i(1/z)) \,[/math]

ここで、任意の有理関数 [math]f(z) = P(z)/Q(z) \,[/math] について、次が成り立つ。

• [math] polydeg(f) = max (deg(P), deg(Q)) \,[/math].

従って [math] m \,[/math] は [math] H_i(1/z) \,[/math] の最大多項式次数であり、拘束長は [math] K = m + 1 \,[/math] と定義される。実際、図1の例では拘束長は 3、図2の例では拘束長は 4 である。

トレリス図

畳み込みエンコーダは一種の有限オートマトンである。n 個のバイナリセルのあるエンコーダは、2ⁿ の状態を持つ。

図1のエンコーダを例として説明すると、このエンコーダの左のメモリセル(m₀)に '1'、右端のメモリセル(m_-1)に '0' が格納されているとする。m₁ は現在の値そのものであり、実際にはメモリセルではない。このときの状態を "10" で表す。入力ビットの値によって、次の状態は "01" か "11" になる。つまり、考えられるあらゆる状態を考慮したとき、それらの間に必ず遷移（エッジ）が存在するわけではない（例えば、 "10" 状態から "10" 状態への遷移はあり得ない）。

ファイル:Convolutional code trellis diagram.svg

図3. 図1のエンコーダについてのトレリス図

全ての可能な遷移は右図で示される。

実際に符号化された列は、この図での経路で示される。妥当な経路は右図では赤で示されている。

この図は「復号」に関する考え方を与えてくれる。受信したビット列がこの図に適合しない場合、誤りがあることがわかり、最も近い「正しい」ビット列を選ばなくてはならない。実際の復号アルゴリズムもこの考え方を定式化したものである。

自由距離と誤り分散

自由距離（free distance、d）は、異なる符号化列の間の最小ハミング距離である。畳み込み符号の訂正能力（correcting capability、t）とは、その符号によって訂正できる誤りの数である。訂正能力は次のように求められる。

• [math]t=\left \lfloor \frac{d-1}{2} \right \rfloor[/math]

畳み込み符号はブロックを使用せず、連続なビット列として処理するため、t の値は比較的互いに近い位置にある誤りに適用されるものである。すなわち、比較的遠い位置のビット列がそれぞれ t 個の誤りを含んでいても、問題なく訂正できる。

自由距離は、畳み込みデコーダの出力が連続的に誤りとなったときに許容できる最小の長さと解釈することもできる。畳み込み符号を使った連結符号を設計する際、誤りが連続して発生することを考慮する必要がある。この問題の一般的な解決策としては、インタリーバと呼ばれる機構で畳み込み符号化する前にデータをインターリーブしておき、外側のブロック符号（リード・ソロモン符号など）がほとんどの誤りを正しく訂正できるようにする。

畳み込み符号の復号

畳み込み符号の復号にはいくつかのアルゴリズムがある。k が比較的小さい場合、最尤法に基づいた高度に並列化可能なビタビアルゴリズムがよく使われる。ビタビデコーダはVLSIにも実装が容易であり、CPU上でソフトウェアとして実行する場合もSIMD命令を使うのに適している。

拘束長が長い場合、逐次型の復号アルゴリズムがいくつか存在しており、ファーノ・アルゴリズムなどがよく知られている。ビタビ復号とは異なり、逐次復号は最尤法は用いないが、計算量は拘束長に対して若干増大するだけで、強力な長い拘束長の符号を利用可能とする。そのような符号は1970年代のパイオニア計画（木星および土星の探査）で使われたが、短いビタビ符号を大きなリード・ソロモン符号で連結した形であり、全体としてビットエラー率の曲線は急勾配となり、極めて低い誤り見逃し率を実現していた。

ビタビ復号アルゴリズムも逐次復号アルゴリズムも、根本は最もそれらしい符号語を探すものである。近似的な信頼度を各ビットに付与する方法として、軟出力ビタビアルゴリズムがある。各ビットについての最大事後確率(MAP)の軟判定は、BCJRアルゴリズムを使って実現される。

主な畳み込み符号

ビタビ復号による畳み込み符号の例としては、ボイジャー計画以来使われている、拘束長 k が 7、レート r が 1/2 の符号がある。

• 拘束長が長ければ、それだけ符号としても強力になるが、ビタビアルゴリズムの計算量は拘束長に対して指数関数的に増大するため、宇宙探査ではデコーダの計算量と符号の性能のトレードオフで符号が設計されている。
• マーズ・パスファインダー、マーズ・エクスプロレーション・ローバー、カッシーニでは、k が 15、レートが 1/16 の符号が使われている。これは従来の k が 7 の符号に比較して、符号の性能は 2 dB 向上しているが、デコーダの計算量は 256 倍となっている。

パンクチャド畳み込み符号

パンクチャリング(puncturing)とは、基本となる 1/2 レートの符号から m/n のレートの符号を作る技法である。これは、エンコーダの出力の一部ビットを削除することでなされる。削除されるビットは「パンクチャリング行列; puncturing matrix」によって決定される。次に示すパンクチャリング行列は最もよく使われているものである。なお、自由距離は、NASA で使われている k=7 の畳み込み符号の場合である。

符号レート	パンクチャリング行列	自由距離
1/2 (No perf.)	1 1	10
2/3	1 0 1 1	6
3/4	1 0 1 1 1 0	5
5/6	1 0 1 0 1 1 1 0 1 0	4
7/8	1 0 0 0 1 0 1 1 1 1 1 0 1 0	3

例えば上の表にある行列を使って、レート 2/3 の符号を作る場合、第一出力の2つ目の出力ビットと第二出力の全ビットを出力とする。ビットの転送の順序は、それぞれの通信標準によって定義される。

パンクチャド畳み込み符号は通信衛星でよく使われており、例えば、インテルサットやデジタルビデオブロードキャスティングで使われている。

パンクチャド畳み込み符号は「perforated; 穴あき」とも呼ばれる。

ターボ符号

単純なビタビ復号による畳み込み符号は、シャノン限界に迫る性能を発揮するターボ符号の要素として使われている。ターボ符号と同等の誤り訂正性能を畳み込み符号だけで実現しようとすると、デコーダの計算量が非常に大きくなる。ターボ符号は今のところリード・ソロモン符号を利用してはいない。

関連項目

• 低密度パリティ検査符号

外部リンク

• Tutorial on Convolutional Coding and Decoding
• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, Chapter 47 にて LDPC 符号を論じている。
• The Error Correcting Codes (ECC) Page
• EEMBC benchmark scores マイクロプロセッサでの畳み込み符号化の性能を評価した結果
• 無線通信における畳み込み符号化について