畳み込み符号
畳み込み符号化および復号は有限な状態遷移で表現することができる。kビットのメモリを持つ符号器は 2 k {\displaystyle 2^{k}} の状態が存在する。
例として図1の符号器を用いる。左のメモリ m 0 {\displaystyle m_{0}} に 1, 右端のメモリ m − 1 {\displaystyle m_{-1}} に 0 が格納されているとする。このときの状態を 10 で表す。なお m 1 {\displaystyle m_{1}} は現在の入力ビットそのものであり、状態には含めない。入力ビットの値によって、次の状態は 01 か 11 になる。ここで10 状態から 10 状態への遷移はあり得ない。
図3にこの符号器における全パターンの状態遷移を示す。符号器の状態遷移を分岐で表現したものをトレリス図と呼び、実際の符号化列はこの図上での経路で表現できる。一例を赤線で示した。
上記および図に示す通り、各状態の間には必ずしも遷移が存在するわけではない。これは復号に際して重要となる。受信ビットがこの図に適合しない場合は誤りがあることがわかり、最も近い「正しい」ビット列を選ばなくてはならない。実際の復号アルゴリズムもこの考え方を定式化したものである。