畳み込み符号

畳み込み符号︵たたみこみふごう、英: Convolutional code︶は、電気通信における誤り訂正符号の一種である。

1955年にマサチューセッツ工科大学のピーター・イライアスが提案したもので、一定長さ(拘束長)のビット列から順次新たなビット列を生成することで符号化する。対照的な方法にブロック符号がある。

符号化の基本動作

図1. 符号化率 1/3、拘束長 3 の非再帰・非組織的畳み込み符号器

図1は最も簡易な畳み込み符号器の一例を示す。これは入力1ビットを3ビットに変換出力するもので、直近で入力された3ビットを記憶する機構を含む。

一般に、畳み込み符号では以下の用語・記号で性能を表現する。

●符号化率 $r$ : 入力ビット長と出力ビット長の比。mビットからnビットへの変換$(n\geq m)$ では $r=m/n$ となる。

●拘束長 $k$ : 演算に用いる直近の入力ビットの長さ (constraint length)。

●自由距離 $d$ : 符号の訂正能力を表す (free distance)。 詳細は後述。

ここでは、符号化率 $r=1/3$ 、拘束長 $k=3$ となる。

符号器には、1ビットを入力保持できる k個のメモリレジスタを用意する。各メモリレジスタの初期値は 0 とする。また、n対の加算器と生成多項式があり、それぞれ2を法として演算する。

まず、入力ビット $m_{1}$ は左端のレジスタに格納される。そして、各メモリレジスタの値から生成多項式を適用して nビットを出力する。この例では、生成多項式は $G_{1}=(1,1,1),G_{2}=(0,1,1),G_{3}=(1,0,1)$  であり、出力ビットは次のように計算される︵2を法とする︶。

●n₁ = m₁+ m₀ + m_-1

●n₂ = m₀ + m_-1

●n₃ = m₁+ m_-1

次に、全レジスタ値を右方向にビットシフトし︵$m_{1}$  を $m_{0}$  に移し、$m_{0}$  を $m_{-1}$  に移す︶、次の入力ビットを待つ。 これを反復し、新たな入力ビットがない場合、全てのレジスタがゼロ状態になるまで出力を続ける。

再帰的な実装

図2. 符号化率 1/2、拘束長 4 の再帰・組織的畳み込み符号器

図1で示したものは非再帰的な符号器である。一方で、図2に示すように再帰的なものもある。

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

一般に、再帰的符号は組織的であり、逆に非再帰的符号は非組織的である。そうでない実装も可能であるが、そのようになっていることが多い。

数学的表現

この方式の名称の由来は、入力と符号器のインパルス応答との畳み込みを行うことによる。符号器の応答は次の式で表される。

$y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}$ 

ここで、$x$  は入力列、$y^{j}$  は $j$  番目の出力列、$h^{j}$  は $j$  番目の出力のインパルス応答である。

畳み込み符号器は、離散線型時不変系である。符号出力は固有の伝達関数で表され、それは生成多項式と密接に関連している。インパルス応答はZ変換により伝達関数として表現できる。

図1の非再帰的符号器の伝達関数は次の通りである。

●${\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$  を次のように定義する。

●$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$  は $H_{i}(1/z)$  の最大多項式次数であり、拘束長は $k=m+1$  と定義される。実際、図1の例では拘束長は3、図2の例では拘束長は4である。

復号

方式

詳細は「ビタビアルゴリズム」を参照

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

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

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

トレリス図

図3. 図1の符号器についてのトレリス図。実線は0入力、破線は1入力、赤線は遷移の一例

畳み込み符号化および復号は有限な状態遷移で表現することができる。kビットのメモリを持つ符号器は $2^{k}$  の状態が存在する。

例として図1の符号器を用いる。左のメモリ $m_{0}$  に 1, 右端のメモリ $m_{-1}$  に 0 が格納されているとする。このときの状態を 10で表す。なお $m_{1}$  は現在の入力ビットそのものであり、状態には含めない。入力ビットの値によって、次の状態は 01か 11になる。ここで10 状態から 10状態への遷移はあり得ない。

図3にこの符号器における全パターンの状態遷移を示す。符号器の状態遷移を分岐で表現したものをトレリス図と呼び、実際の符号化列はこの図上での経路で表現できる。一例を赤線で示した。

上記および図に示す通り、各状態の間には必ずしも遷移が存在するわけではない。これは復号に際して重要となる。受信ビットがこの図に適合しない場合は誤りがあることがわかり、最も近い﹁正しい﹂ビット列を選ばなくてはならない。実際の復号アルゴリズムもこの考え方を定式化したものである。

自由距離とエラー分布

任意の異なる符号化列のビット差分の個数(最小ハミング距離)を﹁自由距離﹂と呼ぶ。これは復号器の出力が連続的に誤りとなったときに許容できる最小の長さと解釈することもでき、符号設計においてはこの値が重要な指標となる。

畳み込み符号の訂正能力︵correcting capability︶として、訂正可能な誤りの数 tは自由距離 dを用いて次のように求められる。

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

この値は比較的互いに近い位置にある誤りについての限界を示すものである。逆に、ビット列がある程度離れた位置に t個を超える誤りを含んでいても、問題なく訂正できる。

畳み込み符号ではビット列を逐次演算しているため、ブロック符号と比較すると誤りが連続して発生すること(バーストエラー)への耐性が弱く、対策を考慮する必要がある。解決策として前述のパイオニア計画の例のように、畳み込み符号化する前にデータをインターリーブしておき、外側のブロック符号︵リード・ソロモン符号など︶がその種の誤り訂正をできるようにするなどの方法が採られている。

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

ビタビ復号を用いる畳み込み符号では符号化率1/2の符号が広く使われているが、これをもとに任意の符号化率のものを作ることができる。この操作をパンクチャリング (puncturing; 穴あけ)または perforated (穴あけ)と呼ぶ。

パンクチャリングでは、符号器の出力ビットを一部削除して符号を生成する。削除されるビットはパンクチャリング行列(puncturing matrix)によって決定される。主なパンクチャリング行列を以下に示す。

符号化率 r	パンクチャリング行列	自由距離 d (k = 7 の場合)
1/2 (穴あけなし)	${\begin{bmatrix}1\\1\end{bmatrix}}$	10
2/3	${\begin{bmatrix}1&0\\1&1\end{bmatrix}}$	6
3/4	${\begin{bmatrix}1&0&1\\1&1&0\end{bmatrix}}$	5
5/6	${\begin{bmatrix}1&0&1&0&1\\1&1&0&1&0\end{bmatrix}}$	4
7/8	${\begin{bmatrix}1&0&0&0&1&0&1\\1&1&1&1&0&1&0\end{bmatrix}}$	3

例えば符号化率 2/3 の符号を作る場合、上表の行列を使って、第1出力の2つ目の出力ビットと第2出力の全ビットを出力とする。ビットの転送の順序は通信規格による。

この方式は通信衛星でよく使われており、インテルサットやデジタルビデオブロードキャスティングなどで使われている。

実用例

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

拘束長が長ければそれだけ符号としても強力になるが、ビタビ法の計算量は拘束長に対して指数関数的に増大するため、宇宙探査では復号器の計算量と符号の性能のトレードオフで符号が設計されている。

●ビタビ復号を用いたものでは、拘束長 $k=7$ 、符号化率 $r=1/2$  の符号がある。NASAのボイジャー計画で使われて以来、広く普及している。

●マーズ・パスファインダー、マーズ・エクスプロレーション・ローバー、カッシーニでは、拘束長 $k=15$ 、符号化率 $r=1/16$  の符号が使われている。これは従来の $k=7$  の符号に比較して性能は 2 dB 向上しているが、復号の計算量は 256 倍となっている。

単純なビタビ復号を用いた畳み込み符号に代わり、現在ではターボ符号が広く利用されている。ターボ符号はシャノン限界に迫るほどの高性能を発揮しており、これと同等の誤り訂正性能を畳み込み符号だけで実現しようとすると復号計算量が非常に大きくなる。

関連項目

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

外部リンク

• 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 マイクロプロセッサでの畳み込み符号化の性能を評価した結果
• 無線通信における畳み込み符号化について