符号理論
例えば、テーブル上の円に何枚の硬貨を敷き詰められるか、あるいは3次元では球体の中にどれだけビー玉を詰められるかという問題と同じである。別の考慮として、符号の選択がある。例えば、正六角形を四角形の枠に敷き詰めようとしても、角に隙間ができてしまう。次元を大きくすると、隙間となる空間の割合は小さくなる。しかし、ある次元で符号が隙間無く敷き詰められるようになり、それを完全符号と呼ぶ。そのような符号の例は非常にまれである(ハミング [ n , k , 3 ] {\displaystyle [n,k,3]} 、ゴレイ [ 24 , 12 , 8 ] , [ 23 , 12 , 7 ] , [ 12 , 6 , 6 ] {\displaystyle [24,12,8],[23,12,7],[12,6,6]} )。
もうひとつ、よく見逃される点として、1つの符号語が持つ近傍の数がある。再び硬貨を例にすると、最初に硬貨を方形の格子に詰める。この場合、各硬貨には4つの近傍がある。正六角形では、各硬貨は6つの近傍を持つ。次元を大きくすると、近傍の数は急速に増加する。結果として、ノイズによってある符号語を近傍の別の符号語と間違う可能性も大きくなる。これはブロック符号の基本的制限であり、実際すべての符号に言えることである。ある近傍に間違う可能性は低くても、近傍が増えれば全体としての誤り率は問題となる。
畳み込み符号は電話回線用モデム(ITU-T V.32、V.17、V.34)や GSM 携帯電話、さらには衛星通信や軍事通信機器にも使われている。
ここでのアイデアは、入力となるメッセージ群のシンボル列の重み付き総和として各符号語のシンボルを作成するということである。これは線形時不変系において入力とインパルス応答が判っているときに出力を求める畳み込みに似ている。
従って、畳み込みエンコーダの出力は一般に、畳み込みエンコーダとレジスタの状態に対する入力ビットの畳み込みである。
基本的に畳み込み符号は同等なブロック符号以上のノイズ耐性を保証しないが、多くの場合、同程度のブロック符号よりも実装が大幅に単純化される。エンコーダは大抵の場合、状態メモリとフィードバック論理(通常 XORゲート)を持つ単純な回路である。デコーダはファームウェアやソフトウェアで実装される。
畳み込み符号のデコードに最適なアルゴリズムとしてビタービ・アルゴリズムがある。その計算負荷を減らす単純化手法もあり、最も可能性の高い経路だけを探索する。これは最適ではないが、低ノイズの環境ではよい結果となることがわかっている。最近のマイクロプロセッサでは、この縮小された探索アルゴリズムで平均毎秒4,000符号語以上のデコードが可能である。