畳み込み符号(convolutional code)とは、情報のビット列をシフトレジスタに通し、各時刻に直前の数ビットの 1 次式を送り出す誤り訂正符号である。遅延の記号 $D$ を変数として、情報の列 $u(D)$ に多項式(一般には有理関数)の生成行列 $G(D)$ を掛けた $u(D)G(D)$ が符号語になる。符号語は有限個の状態をもつトレリスの上の道で表され、2 元対称通信路での最尤復号は、受信語に Hamming 距離で最も近い道を時刻ごとに求める Viterbi 復号で、長さに比例する手間で行える。率 $1/n$ の多項式符号化器は、生成多項式の最大公約元が $D$ の冪のときに限り破滅的でなく、そのとき自由距離は状態図の迂回路の重みの最小値に等しい。
畳み込み符号(convolutional code)は、情報のビット列を一定の長さのブロックに区切らず、流れてくるビットをシフトレジスタに通して、各時刻に過去の数ビットの 1 次式を送り出す誤り訂正符号である。送るビット列は、情報の列と短い固定の列(生成多項式の係数)との 畳み込み になるので、この名がある(Mac03 p. 184)。
ブロック符号の 線形符号 では、符号語の長さ $N$ と情報の長さ $K$ が決まっていて、生成行列は $\mathbb{F}_2$ 上の行列である。畳み込み符号では、時刻をずらす演算子 $D$ を変数とする多項式が係数になり、生成行列は $\mathbb{F}_2[D]$ や有理関数体 $\mathbb{F}_2(D)$ 上の行列になる。符号の状態はシフトレジスタの中身で、状態の数が有限なので、符号語は有限の状態図の上の道として表せる。この道の図(トレリス)の上で、受け取った列に最も近い符号語を 動的計画法 で求めるのが Viterbi 復号 である。
この記事では、生成行列による定義、状態とトレリス、自由距離を定める。主定理として、率 $1/n$ の多項式符号化器が 破滅的(有限個の通信路の誤りが無限個の復号の誤りを生みうる)でないための条件が、生成多項式の最大公約元が $D$ の冪であることだと証明する(thm-cc-catastrophic)。これを使って、自由距離が状態図の「迂回路」の最小の重みで求まることを示し(cor-cc-detour)、標準的な例である $(7,5)$ 符号の重みの分布をすべて求める(thm-cc-transfer)。最後に、2 元対称通信路の最尤復号がトレリス上の最短経路の問題になり、Viterbi 復号がそれを正しく解くことを示す(thm-cc-viterbi)。
時刻 $t\in\mathbb{Z}$ のビット $x_t\in\mathbb{F}_2$ の列を、$D$ を時刻を $1$ 進める記号として
$$
x(D)=\sum_{t\ge t_0}x_tD^t
$$
と書く。始まりの時刻 $t_0$ は列ごとに決まり、過去には有限にしか遡らない。このような形式的な Laurent 級数の全体 $\mathbb{F}:=\mathbb{F}_2((D))$ は体である。多項式環 $\mathbb{F}_2[D]$、Laurent 多項式環 $\mathbb{F}_2[D,D^{-1}]$、有理関数体 $\mathbb{F}_2(D)$ は $\mathbb{F}$ に含まれる。有理関数が $\mathbb{F}$ に入るのは、$0$ でない多項式が $D^aq(D)$($q(0)=1$)と書け、$q$ が 形式的冪級数 の環 $\mathbb{F}_2[\![D]\!]$ で可逆だからである。
列 $x$ の 重み $\operatorname{wt}(x)$ を $x_t=1$ となる $t$ の個数($\infty$ もとる)とし、ベクトル $v=(v^{(1)},\dots,v^{(n)})\in\mathbb{F}^n$ では成分の重みの和とする。$\operatorname{wt}(x)< \infty$ と $x\in\mathbb{F}_2[D,D^{-1}]$ は同じことである。
$1\le k\le n$ とする。$\mathbb{F}_2(D)$ に成分をもつ $k\times n$ 行列 $G(D)$ で階数が $k$ のものを 生成行列 といい、写像
$$
\mathbb{F}^k\to\mathbb{F}^n,\qquad u(D)\mapsto v(D)=u(D)G(D)
$$
を $G$ の 符号化器 という。その像 $C=\{uG:u\in\mathbb{F}^k\}$ を 畳み込み符号、$k/n$ を 符号化率 という。$G$ の成分がすべて多項式のとき 多項式符号化器 といい、成分の次数の最大値 $m$ を 記憶の長さ という。
$C$ は $\mathbb{F}$ 上の $k$ 次元部分空間である。同じ $C$ を与える生成行列はたくさんあり(prop-cc-equivalent)、「符号」と「符号化器」は区別する。以下、主に率 $1/n$ の多項式符号化器 $G=(g^{(1)},\dots,g^{(n)})$、$g^{(j)}=\sum_{i=0}^mg^{(j)}_iD^i$ を扱う。このとき $v^{(j)}=ug^{(j)}$ の係数は
$$
v^{(j)}_t=\sum_{i=0}^{m}g^{(j)}_i\,u_{t-i}
$$
で、時刻 $t$ の出力 $(v^{(1)}_t,\dots,v^{(n)}_t)$ は、いまの入力 $u_t$ と直前の $m$ 個の入力だけで決まる。送るときは時刻ごとに $n$ ビットを並べる。
生成多項式は、係数 $(g_0,g_1,\dots,g_m)$ を 2 進数と読んで 8 進で書くことが多い。この記事の $(7,5)$ 符号 は
$$
G(D)=(1+D+D^2,\ 1+D^2)\qquad(111_2=7,\ 101_2=5)
$$
である。Mac03 p. 575 は逆の向き($g_m$ を最上位の桁)に読み、図 48.3 ではこの符号を $(5,7)_8$ と書くが、$7$ と $5$ は左右対称なので、生成多項式は同じである。
率 $1/n$、記憶の長さ $m\ge1$ の多項式符号化器で、時刻 $t$ の 状態 を $\sigma_t=(u_{t-1},\dots,u_{t-m})\in\mathbb{F}_2^m$ とする。入力 $u_t$ を受けると出力 $(v^{(j)}_t)_j$ を出し、状態は $(u_t,u_{t-1},\dots,u_{t-m+1})$ に移る。状態を頂点とし、各状態から入力 $0,1$ に応じて辺を 1 本ずつ引き、辺に「入力/出力」を書いた有向グラフを 状態図 という。辺の 重み は出力の重みである。状態図を時刻の順に並べ直し、時刻 $t$ の状態から時刻 $t+1$ の状態へ辺を引いた図を トレリス という。
入力は時刻 $0$ に始まり、$t<0$ では $u_t=0$(状態 $0$ から出発)とする。情報 $L$ ビットのあとに $0$ を $m$ 個入れると状態 $0$ に戻る。こうして得る長さ $n(L+m)$ の符号語の全体を 終端した符号 $C_L$ という。$C_L$ は $\mathbb{F}_2^{n(L+m)}$ の $L$ 次元の線形符号で、その符号語はトレリスで時刻 $0$ の状態 $0$ から時刻 $L+m$ の状態 $0$ へ行く道と 1 対 1 に対応する。
畳み込み符号 $C$ の 自由距離 を
$$
d_{\mathrm{free}}(C)=\min\{\operatorname{wt}(v):v\in C,\ 0< \operatorname{wt}(v)< \infty\}
$$
と定める。率 $1/n$、記憶の長さ $m\ge1$ の多項式符号化器の状態図で、状態 $0$ から入力 $1$ で出て、$0$ でない状態だけを通り、初めて状態 $0$ に戻る道を 迂回路 といい、通った辺の重みの和をその重みという。
符号化器 $G$ が 破滅的 であるとは、$\operatorname{wt}(u)=\infty$ で $\operatorname{wt}(uG)< \infty$ となる入力 $u\in\mathbb{F}^k$ があることをいう。
破滅的な符号化器では、$0$ を送ったときに通信路が $uG$ の有限個のビットを反転させると、受け取る列は符号語 $uG$ そのものになり、受信語が符号語ならそれを採る復号(最小距離復号など)は $u$ と読むので、情報のビットの誤りは無限個になる。この記事の定理を使える条件は次の 3 つである。
$(7,5)$ 符号 $G=(1+D+D^2,\,1+D^2)$ の量をまとめる。
| 量 | 値 | 条件 | 根拠 |
|---|---|---|---|
| 符号化率・記憶の長さ・状態の数 | $1/2$、$m=2$、$4$ | — | 定義 |
| 破滅的か | 破滅的でない | — | thm-cc-transfer の 1 |
| 迂回路の重みの母関数 | $T(W)=\dfrac{W^5}{1-2W}$ | — | thm-cc-transfer の 2 |
| 重み $w$ の迂回路の数 | $2^{w-5}$($w\ge5$)、$0$($w\le4$) | — | thm-cc-transfer の 2 |
| 自由距離 | $d_{\mathrm{free}}=5$ | — | thm-cc-transfer の 3 |
| 終端した符号 $C_L$ | 長さ $2(L+2)$、次元 $L$、最小距離 $5$ | $L\ge1$ | ex-cc-terminated |
| 確実に直せる誤りの数 | $2$ 個まで($C_L$ の最小距離復号) | $L\ge1$ | ex-cc-terminated |
| Viterbi 復号の手間 | 時刻ごとに辺 $8$ 本の比較 | 終端した符号 | thm-cc-viterbi |
一般の率 $1/n$ の多項式符号化器についての式:
| 公式 | 条件 | 根拠 |
|---|---|---|
| 破滅的でない $\iff\gcd(g^{(1)},\dots,g^{(n)})=D^a$ | 多項式、率 $1/n$ | thm-cc-catastrophic |
| $d_{\mathrm{free}}=$ 迂回路の重みの最小値 | 破滅的でない | cor-cc-detour |
| $G$ と $rG$($r\in\mathbb{F}_2(D)$、$r\ne0$)は同じ符号 | — | prop-cc-equivalent |
| 最尤復号 $=$ Hamming 距離の最小化 | 2 元対称通信路、$0< p< 1/2$ | prop-cc-ml |
| Viterbi 復号の手間 $O\bigl((L+m)\,2^{m}n\bigr)$ | 終端した符号 | thm-cc-viterbi |
$G=(g^{(1)},\dots,g^{(n)})$ を $0$ でない多項式の組とする。$G$ が破滅的でないための必要十分条件は、$\mathbb{F}_2[D]$ における最大公約元 $d=\gcd(g^{(1)},\dots,g^{(n)})$ がある $a\ge0$ について $D^a$ に等しいことである。
十分性。 $d=D^a$ とする。$\mathbb{F}_2[D]$ は単項イデアル整域なので、Bézoutの等式 により多項式 $a_1,\dots,a_n$ で $\sum_ja_jg^{(j)}=D^a$ となるものがある。$u\in\mathbb{F}$ について $\operatorname{wt}(uG)< \infty$ なら、各 $v^{(j)}=ug^{(j)}$ は Laurent 多項式であり、
$$
D^au=\sum_{j=1}^na_j\,(ug^{(j)})=\sum_{j=1}^na_jv^{(j)}
$$
も Laurent 多項式である。よって $u=D^{-a}\cdot D^au$ も Laurent 多項式で、$\operatorname{wt}(u)< \infty$ である。
必要性。 $d=D^ah$、$h(0)=1$ と書き、$\deg h\ge1$ と仮定する。$h$ は $\mathbb{F}_2[\![D]\!]$ で可逆なので $u:=1/h\in\mathbb{F}$ がとれる。各 $j$ について
$$
ug^{(j)}=\frac{g^{(j)}}{h}=D^a\cdot\frac{g^{(j)}}{d}
$$
は多項式なので、$\operatorname{wt}(uG)< \infty$ である。一方 $u$ が Laurent 多項式 $p(D)D^{-b}$($p$ は多項式)だとすると $hp=D^b$ となる。$h(0)=1$ より $h$ と $D$ は互いに素なので、$h$ は $D^b$ を割ることから $h$ は $1$ を割り、$\deg h=0$ となって矛盾する。よって $\operatorname{wt}(u)=\infty$ で、$G$ は破滅的である。$\square$
率 $1/n$、記憶の長さ $m\ge1$ の多項式符号化器 $G$ が破滅的でないとする。このとき $G$ の生成する符号 $C$ の自由距離は、状態図の迂回路の重みの最小値に等しい。より詳しく、$C$ の重み有限の $0$ でない符号語の重みは、いくつかの迂回路の重みの和である。
$v\in C$、$0< \operatorname{wt}(v)< \infty$ とし、$v=uG$ と書く。thm-cc-catastrophic の十分性の証明により $u$ は Laurent 多項式で、$v\ne0$ より $u\ne0$ である。$D^bv=(D^bu)G\in C$ で重みは変わらないので、$u_t=0$($t<0$)、$u_0=1$ としてよい。
時刻 $0$ から始まる状態の列 $\sigma_0=0,\sigma_1,\dots$ は、$t>\deg u+m$ で $0$ である。状態 $0$ から状態 $0$ への辺は入力 $0$ の辺だけで、その出力は $0$ である。状態の列を、状態 $0$ に留まる部分と、状態 $0$ を離れてから初めて $0$ に戻るまでの部分に切ると、後者はどれも迂回路である(離れる辺は入力 $1$ の辺)。$\operatorname{wt}(v)$ はこれらの迂回路の重みの和なので、迂回路の重みの最小値以上である。
逆に、迂回路を 1 つとり、その入力の列のあとに $0$ を続けた入力 $u$(多項式)を考える。状態は迂回路の終わりで $0$ になり、その後は $0$ に留まって出力も $0$ なので、$\operatorname{wt}(uG)$ は迂回路の重みに等しい。$u\ne0$ で $\mathbb{F}$ は体だから $uG\ne0$ であり、この重みは $1$ 以上の有限の値である。よって $d_{\mathrm{free}}$ は迂回路の重みの最小値以下である。$\square$
状態を $\sigma=(u_{t-1},u_{t-2})$ と書く。$(7,5)$ 符号の出力は $v^{(1)}_t=u_t+u_{t-1}+u_{t-2}$、$v^{(2)}_t=u_t+u_{t-2}$ である。
| 状態 | 入力 $0$:次の状態/出力 | 入力 $1$:次の状態/出力 |
|---|---|---|
| $00$ | $00$/$00$ | $10$/$11$ |
| $10$ | $01$/$10$ | $11$/$01$ |
| $01$ | $00$/$11$ | $10$/$00$ |
| $11$ | $01$/$01$ | $11$/$10$ |
$G=(1+D+D^2,\,1+D^2)$ について次が成り立つ。
1。 $1+D+D^2$ は $D=0,1$ で値 $1$ をとり根をもたないので、次数 $2$ の 既約多項式 である。$1+D^2=(1+D)^2$ はこれで割り切れないので、最大公約元は $1=D^0$ である。thm-cc-catastrophic から破滅的でない。
2。 状態 $s\in\{10,01,11\}$ について、状態 $00$ から入力 $1$ の辺で出て、その後 $0$ でない状態だけを通って $s$ で終わる道の全体を考え、$A_s(W)=\sum W^{\text{重み}}$ とおく。まずこれが 形式的冪級数 として意味をもつことを見る。$0$ でない状態の間の辺で重み $0$ のものは $01\to10$ だけで、その次の辺は $10$ から出るので重み $1$ である。したがって辺を $\ell$ 本もつ道の重みは $(\ell-1)/2$ 以上で、各重みの道は有限本しかない。
道を最後の辺で分けると、表から
$$
A_{10}=W^2+A_{01},\qquad A_{01}=W\,A_{10}+W\,A_{11},\qquad A_{11}=W\,A_{10}+W\,A_{11}
$$
が成り立つ($A_{10}$ の $W^2$ は最初の辺だけの道)。迂回路は $01$ から入力 $0$(重み $2$)で $00$ に戻る道なので $T=W^2A_{01}$ である。$1-W$、$1-2W$ は $\mathbb{Z}[\![W]\!]$ で可逆なので、3 番目の式から $A_{11}=WA_{10}/(1-W)$、2 番目から
$$
A_{01}=WA_{10}\Bigl(1+\frac{W}{1-W}\Bigr)=\frac{WA_{10}}{1-W}
$$
を得る。1 番目に代入して $A_{10}\,\dfrac{1-2W}{1-W}=W^2$、すなわち $A_{10}=\dfrac{W^2(1-W)}{1-2W}$、$A_{01}=\dfrac{W^3}{1-2W}$ となり、$T=W^5/(1-2W)$ である。
3。 2 から迂回路の重みの最小値は $5$ で、1 と cor-cc-detour から $d_{\mathrm{free}}=5$ である。$\square$
重み $5$ の迂回路は入力 $1,0,0$ の道 $00\to10\to01\to00$ で、出力は $11\,10\,11$ である。
$G$ を生成行列、$r\in\mathbb{F}_2(D)$ を $0$ でない有理関数とすると、$G$ と $rG$ は同じ畳み込み符号を生成する。
$r$ は体 $\mathbb{F}$ の $0$ でない元なので可逆である。$u\mapsto ur^{-1}$ は $\mathbb{F}^k$ の全単射で、$u(rG)=(ur)G$、$uG=(ur^{-1})(rG)$ だから、2 つの像は一致する。$\square$
$(7,5)$ 符号に $r=1/(1+D+D^2)$ を掛けた $G'=\bigl(1,\ (1+D^2)/(1+D+D^2)\bigr)$ は、最初の出力が入力そのものになる 組織的 な符号化器で、分母を帰還のあるシフトレジスタで実現するので 再帰的 という。$G$ に入力 $u$ を入れた符号語は、$G'$ に入力 $u(1+D+D^2)$ を入れても得られる。たとえば $G$ の入力 $1$ に対応する $G'$ の入力は $1,1,1$ である(Mac03 §48.2、pp. 576–577 は記憶の長さ $2$ の符号とその再帰的な組織的符号化器で、同じ符号を与えることと、この入力の対応を図 48.3–48.5 で示している)。符号は同じでも、$G'$ に入力 $1$ を入れた出力は $1+D+D^2\nmid1+D^2$ より重みが無限になり、入力と出力の対応は違う。
長さ $N$ の符号語の集合 $C'\subset\mathbb{F}_2^N$ を、各ビットが独立に確率 $p$($0< p< 1/2$)で反転する通信路で送り、$y$ を受け取ったとする。このとき尤度 $P(y\mid c)$ を最大にする $c\in C'$ は、Hamming 距離 $d(c,y)$ を最小にする $c$ と一致する。
$P(y\mid c)=p^{d(c,y)}(1-p)^{N-d(c,y)}=(1-p)^N\bigl(p/(1-p)\bigr)^{d(c,y)}$ で、$0< p/(1-p)< 1$ だから、これは $d(c,y)$ について狭義に減少する。$\square$
終端した符号 $C_L$ の受信語 $y=(y_0,\dots,y_{L+m-1})$($y_t\in\mathbb{F}_2^n$ は時刻 $t$ の $n$ ビット)について、トレリスの各状態 $s$ と時刻 $t$ に
$$
M_t(s)=\min\Bigl\{\sum_{\tau< t}d(o_\tau,y_\tau)\Bigr\}
$$
を定める。最小は、時刻 $0$ の状態 $0$ から時刻 $t$ の状態 $s$ へ行くトレリスの道(時刻 $L$ 以降は入力 $0$ の辺だけを使う)の全体にわたってとり、$o_\tau$ は道の時刻 $\tau$ の辺の出力である。道がないときは $M_t(s)=\infty$ とする。
時刻 $t+1$ に状態 $s'$ で終わる道は、時刻 $t$ に状態 $s$ で終わる道に辺 $s\to s'$ を 1 本つないだものとして一意に書け、距離は $\sum_{\tau< t}d(o_\tau,y_\tau)+d(o_{s\to s'},y_t)$ と分かれる。まず $s$ を止めて前半を最小にし、次に $s$ について最小をとれば 1 の式になる。
2 は $t$ についての帰納法で、「記録した辺を $(t,s)$ から後ろへたどった道の距離は $M_t(s)$ に等しい」ことを示す。$t=0$ では明らか。$t+1$ では、記録した辺を $s\to s'$ とすると、その道は $(t,s)$ からたどった道に $s\to s'$ をつないだもので、帰納法の仮定と 1 から距離は $M_t(s)+d(o_{s\to s'},y_t)=M_{t+1}(s')$ である。$C_L$ の符号語は時刻 $0$ と時刻 $L+m$ の状態 $0$ を結ぶ道と 1 対 1 に対応するので、$t=L+m$、$s'=0$ のとき主張が出る。
3:各時刻に $2^m$ 個の状態から高々 $2$ 本の辺があり、辺ごとに $n$ ビットの距離を計算する。$\square$
prop-cc-ml と合わせると、Viterbi 復号は 2 元対称通信路での $C_L$ の最尤復号である。符号語の数は $2^L$ あるが、手間は $L$ の 1 次で済む。これは 隠れMarkovモデル の Viterbi アルゴリズムと同じ構造で、辺の重みを $-\log P(y_t\mid o)$ にすれば、各時刻の受信が独立な(無記憶の)通信路の最尤復号になる(Mac03 §25.3、p. 329)。
率 $1/n$ の多項式符号化器で符号化し、終端した符号を Viterbi 復号する手順は次のとおり。
| 場面 | やること | 結果 |
|---|---|---|
| 最小を与える辺が 2 本ある | どちらを記録してもよい | 最も近い符号語の 1 つ(一意とは限らない) |
| 受信が長く、終端を待てない | 一定の遅れで、その時点で最良の状態から後ろへたどって確定する | 最尤ではない近似 |
| 軟判定(受信が実数) | 辺の重みを $-\log P(y_t\mid o)$ にする | 無記憶の通信路の最尤復号 |
以下の例題はすべて $(7,5)$ 符号 $G=(1+D+D^2,\,1+D^2)$ を使う。
情報 $u=1011$ を終端して送る符号語を求める。
使う公式:$v^{(j)}=ug^{(j)}$。
答え:$u(D)=1+D^2+D^3$ で
$$
v^{(1)}=(1+D^2+D^3)(1+D+D^2)=1+D+D^5,\qquad v^{(2)}=(1+D^2+D^3)(1+D^2)=1+D^3+D^4+D^5.
$$
時刻ごとに並べて $11\ 10\ 00\ 01\ 01\ 11$(長さ $12$、重み $7$)。状態は $00\to10\to01\to10\to11\to01\to00$ と移り、途中で $00$ を通らないので、この符号語は重み $7$ の迂回路 1 本からなる。
ex-cc-encode の符号語の 2 ビット目と 7 ビット目が反転し、$y=10\ 10\ 00\ 11\ 01\ 11$ を受け取った。Viterbi 復号する。
使う公式:thm-cc-viterbi($L=4$、$m=2$)。
答え:$M_t(s)$ は次のとおり($-$ は道がない)。
| $t$ | $00$ | $10$ | $01$ | $11$ |
|---|---|---|---|---|
| $0$ | $0$ | $-$ | $-$ | $-$ |
| $1$ | $1$ | $1$ | $-$ | $-$ |
| $2$ | $2$ | $2$ | $1$ | $3$ |
| $3$ | $2$ | $1$ | $3$ | $3$ |
| $4$ | $3$ | $2$ | $2$ | $2$ |
| $5$ | $3$ | $-$ | $2$ | $-$ |
| $6$ | $2$ | $-$ | $-$ | $-$ |
$M_6(00)=2$ で、後ろへたどると状態の列は ex-cc-encode と同じになり、復号結果は $u=1011$、受信語との距離は $2$ である。
たとえば $t=2\to3$ の状態 $10$:$00\to10$(出力 $11$、受信 $00$ と距離 $2$)から $2+2=4$、$01\to10$(出力 $00$、距離 $0$)から $1+0=1$。小さいほうの $1$ をとり、辺 $01\to10$ を記録する。時刻 $4$($=L$)からの辺は入力 $0$ の辺だけなので、$t=5$ では状態 $10,11$ に道がない。
$L\ge1$ のとき、$C_L$ の最小距離は $5$ で、最小距離復号は誤りが $2$ 個以下ならどれも正しく直すことを示す。
使う公式:cor-cc-detour、thm-cc-transfer。
答え:$C_L$ の $0$ でない符号語は多項式の入力から来るので、prf-cc-detour と同じく、その重みは迂回路の重みの和で $5$ 以上である。入力 $1,0,\dots,0$ の符号語は重み $5$ なので、最小距離は $5$。送った $c$ と受信 $y$ の距離が $2$ 以下なら、ほかの符号語 $c'$ について三角不等式から $d(c',y)\ge d(c',c)-d(c,y)\ge5-2=3>d(c,y)$ なので、最も近い符号語は $c$ だけである。$L=4$ の $16$ 個の符号語と $79$ 通りの誤りの置き方($0,1,2$ 個)のすべてで、ex-cc-viterbi の手順は正しい情報を返す。
$L=4$ で $0$ を送り、最初の 3 ビットが反転して $y=11\ 10\ 00\ 00\ 00\ 00$ を受け取ったとする。
答え:重み $5$ の符号語 $c'=11\ 10\ 11\ 00\ 00\ 00$(入力 $1000$)との距離は $2$、送った $0$ との距離は $3$ なので、Viterbi 復号は $u=1000$ を返し、誤る。3 個の誤りは最小距離 $5$ の保証の外である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-cc-catastrophic の「最大公約元が $D^a$」 | $G=(1+D,\,1+D^2)$(最大公約元 $1+D$) | 重み無限の入力 $1/(1+D)$ の出力 $(1,\,1+D)$ は重み $3$。$G$ は破滅的 |
| cor-cc-detour の「破滅的でない」 | 同じ $G=(1+D,\,1+D^2)$ | 迂回路の重みの最小値は $4$ だが、$d_{\mathrm{free}}=3$ |
| prop-cc-ml の $p< 1/2$($p>1/2$ にする) | $C_L$、$p=0.9$、$y=0$ | 尤度は距離について増加し、最尤の符号語は $y$ から最も遠い符号語になる |
| ex-cc-terminated の「誤りが 2 個以下」 | ex-cc-fail | 最も近い符号語が送った符号語でない |
$G=(1+D,\,1+D^2)$ とする。$u=1/(1+D)=1+D+D^2+\cdots$(重み無限)について $uG=\bigl(1,\ (1+D)^2/(1+D)\bigr)=(1,\,1+D)$ で重みは $3$ である。重み $3$ の符号語があるので $d_{\mathrm{free}}\le3$。重み $1$ や $2$ の符号語 $(a,b)$ は $b=(1+D)a$ をみたすが、$a$ の重みが $1$ なら $b$ の重みは $2$、$a$ の重みが $2$ 以上なら合計が $3$ 以上、$a=0$ なら $b=0$ なので、$d_{\mathrm{free}}=3$ である。一方、多項式の入力 $u\ne0$ では $(1+D)u$ も $(1+D)^2u$ も $D=1$ で $0$ になる多項式なので重みは偶数で $2$ 以上、合計は $4$ 以上で、$u=1$ で $4$ になる。迂回路は多項式の入力に対応するので、迂回路の重みの最小値は $4$ である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 符号と符号化器は同じもの | 同じ符号を多くの符号化器が生む | prop-cc-equivalent |
| 自由距離は迂回路を探せば必ず求まる | 破滅的な符号化器では、迂回路に現れない重み有限の符号語がある | ex-cc-cat |
| Viterbi 復号の手間は符号語の数 $2^L$ に比例する | 時刻ごとに状態の数 $2^m$ の手間で、$L$ について 1 次 | thm-cc-viterbi |
| 最も近い符号語を選べばいつも尤度最大 | 2 元対称通信路で $p< 1/2$ のとき | prop-cc-ml |
| 時刻ごとに受信に最も近い出力の辺を選べばよい | 道全体の距離を最小にする。辺ごとの貪欲な選択は誤る | thm-cc-viterbi の 1 の最小は過去の $M_t$ を含む |
畳み込み符号の説明(シフトレジスタによる生成、8 進の表し方、組織的・再帰的な符号化器と同じ符号を与えること)は Mac03 p. 184 と §48.1–48.2(pp. 574–577)に従った。トレリスの上の最小和の計算を Viterbi アルゴリズムと呼ぶことと、その帰属(Viterbi, 1967)は Mac03 §25.3(p. 329)による。thm-cc-catastrophic、cor-cc-detour、thm-cc-transfer、thm-cc-viterbi の証明は、この記事で書き下ろした。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する