畳み込み符号のソースを表示

{{出典の明記|date=2022-03}}
'''畳み込み符号'''（たたみこみふごう、{{lang-en-short|Convolutional code}}）は、[[電気通信]]における[[前方誤り訂正|誤り訂正符号]]の一種である。

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

== 符号化の基本動作 ==
[[画像:Convol_encoder_nrj.png|thumb|right|300px|図1. 符号化率 1/3、拘束長 3 の非再帰・非組織的畳み込み符号器]]
図1は最も簡易な畳み込み符号器の一例を示す。これは入力1ビットを3ビットに変換出力するもので、直近で入力された3ビットを記憶する機構を含む。

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

*'''[[符号レート|符号化率]]''' <math>r</math>: 入力ビット長と出力ビット長の比。''m''ビットから''n''ビットへの変換<math>(n \ge m)</math>では <math>r=m/n</math>となる。
*'''拘束長''' <math>k</math>: 演算に用いる直近の入力ビットの長さ (constraint length)。
*'''自由距離''' <math>d</math>: 符号の訂正能力を表す (free distance)。 詳細は[[#自由距離とエラー分布|後述]]。

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

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

まず、入力ビット <math>m_1</math>は左端のレジスタに格納される。そして、各メモリレジスタの値から生成多項式を適用して ''n'' ビットを出力する。この例では、生成多項式は <math>G_1 = (1,1,1), G_2 = (0,1,1), G_3 = (1,0,1)</math> であり、出力ビットは次のように計算される（2 を法とする）。

*''n''<sub>1</sub> = ''m''<sub>1</sub> + ''m''<sub>0</sub> + ''m<sub>-1</sub>''
*''n''<sub>2</sub> = ''m''<sub>0</sub> + ''m''<sub>-1</sub>
*''n''<sub>3</sub> = ''m''<sub>1</sub> + ''m''<sub>-1</sub>

次に、全レジスタ値を右方向に[[ビット演算|ビットシフト]]し（<math>m_1</math> を <math>m_0</math> に移し、<math>m_0</math> を <math>m_{-1}</math> に移す）、次の入力ビットを待つ。
これを反復し、新たな入力ビットがない場合、全てのレジスタがゼロ状態になるまで出力を続ける。

=== 再帰的な実装 ===
[[画像:Convol_encoder_rj.png|thumb|right|300px|図2. 符号化率 1/2、拘束長 4 の再帰・組織的畳み込み符号器]]
図1で示したものは非再帰的な符号器である。一方で、図2に示すように再帰的なものもある。

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

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

{{clear}}
== 数学的表現 ==
この方式の名称の由来は、入力と符号器の[[インパルス応答]]との[[畳み込み]]を行うことによる。符号器の応答は次の式で表される。

<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> 番目の出力のインパルス応答である。

畳み込み符号器は、離散[[LTIシステム理論|線型時不変系]]である。符号出力は固有の[[伝達関数法|伝達関数]]で表され、それは生成多項式と密接に関連している。インパルス応答は[[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> を次のように定義する。<!-- polydegは生成多項式の次数 -->
*<math> m = \max_i \operatorname{polydeg}(H_i(1/z))</math>

ここで、任意の有理関数 <math>f(z)  = P(z)/Q(z)</math> について、次が成り立つ。
* <math> \operatorname{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 である。

== 復号 ==
=== 方式 ===
{{main|ビタビアルゴリズム}}

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

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

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

=== トレリス図 ===
[[画像:Convolutional_code_trellis_diagram.svg|right|thumb|400px|図3. 図1の符号器についてのトレリス図。実線は0入力、破線は1入力、赤線は遷移の一例]]
畳み込み符号化および復号は[[有限オートマトン|有限な状態遷移]]で表現することができる。''k''ビットのメモリを持つ符号器は <math>2^k</math> の状態が存在する。

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

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

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

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

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

*<math>t=\left \lfloor \frac{d-1}{2} \right \rfloor</math>

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

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

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

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

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

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

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

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

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

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

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

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

== 関連項目 ==
*[[低密度パリティ検査符号]]

== 外部リンク ==
* [http://complextoreal.com/chapters/convo.pdf Tutorial on Convolutional Coding and Decoding]
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms], by David J.C. MacKay, Chapter 47 にて LDPC 符号を論じている。
* [http://www.eccpage.com/ The Error Correcting Codes (ECC) Page]
* [http://www.eembc.org/benchmark/telecom.asp?APPL=TLC EEMBC benchmark scores] マイクロプロセッサでの畳み込み符号化の性能を評価した結果
* [http://caspar.hazymoon.jp/convolution/index.html 無線通信における畳み込み符号化について]

{{DEFAULTSORT:たたみこみふこう}}
[[Category:誤り検出訂正]]
[[Category:数学に関する記事]]