畳み込み符号

同義語:convolutional code

概要

畳み込み符号(convolutional code)とは、情報のビット列をシフトレジスタに通し、各時刻に直前の数ビットの 1 次式を送り出す誤り訂正符号である。遅延の記号 $D$ を変数として、情報の列 $u(D)$ に多項式(一般には有理関数)の生成行列 $G(D)$ を掛けた $u(D)G(D)$ が符号語になる。符号語は有限個の状態をもつトレリスの上の道で表され、2 元対称通信路での最尤復号は、受信語に Hamming 距離で最も近い道を時刻ごとに求める Viterbi 復号で、長さに比例する手間で行える。率 $1/n$ の多項式符号化器は、生成多項式の最大公約元が $D$ の冪のときに限り破滅的でなく、そのとき自由距離は状態図の迂回路の重みの最小値に等しい。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形符号, 有限体, 形式的冪級数

畳み込み符号(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 つである。

  1. 符号化器の形:率 $1/n$ の多項式符号化器(thm-cc-catastrophic、cor-cc-detour)。
  2. 破滅的でないこと:自由距離を迂回路で求めるとき(cor-cc-detour)。
  3. 通信路:各ビットが独立に確率 $p$ で反転する 2 元対称通信路で、$0< p< 1/2$(prop-cc-ml)。

公式の表

$(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

主定理と証明

破滅的でないための条件

率 1/n の多項式符号化器が破滅的でない条件

$G=(g^{(1)},\dots,g^{(n)})$ を $0$ でない多項式の組とする。$G$ が破滅的でないための必要十分条件は、$\mathbb{F}_2[D]$ における最大公約元 $d=\gcd(g^{(1)},\dots,g^{(n)})$ がある $a\ge0$ について $D^a$ に等しいことである。

Bézout の等式と、$1/h$ が Laurent 多項式にならないこと

十分性。 $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$ でない符号語の重みは、いくつかの迂回路の重みの和である。

符号語の道を状態 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$

$(7,5)$ 符号の重みの分布

状態を $\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$
$(7,5)$ 符号の重みの分布

$G=(1+D+D^2,\,1+D^2)$ について次が成り立つ。

  1. $G$ は破滅的でない。
  2. 迂回路の重みの母関数 $T(W)=\sum_{\text{迂回路}}W^{\text{重み}}$ は
    $$ T(W)=\frac{W^5}{1-2W}=\sum_{i\ge0}2^iW^{5+i} $$
    である。すなわち重み $w$ の迂回路は $w\ge5$ なら $2^{w-5}$ 本、$w\le4$ なら $0$ 本ある。
  3. $d_{\mathrm{free}}=5$ である。
状態ごとの母関数の連立方程式

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$ より重みが無限になり、入力と出力の対応は違う。

最尤復号と Viterbi 復号

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$ とする。

Viterbi 復号
  1. $M_0(0)=0$、$M_0(s)=\infty$($s\ne0$)であり、
    $$ M_{t+1}(s')=\min_{s\to s'}\bigl(M_t(s)+d(o_{s\to s'},y_t)\bigr) $$
    が成り立つ。最小は時刻 $t$ に使える辺 $s\to s'$(出力 $o_{s\to s'}$)にわたる。
  2. 各 $t,s'$ で最小を与える辺を 1 本記録し、時刻 $L+m$ の状態 $0$ から記録した辺を後ろへたどった道の出力は、$C_L$ の符号語のうち $y$ に Hamming 距離で最も近いものの 1 つであり、その距離は $M_{L+m}(0)$ である。
  3. 手間は $O\bigl((L+m)\,2^mn\bigr)$ である。
距離は時刻ごとの和である

時刻 $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 復号する手順は次のとおり。

  1. 符号化器を確かめる:生成多項式の最大公約元を Euclidの互除法 で求め、$D$ の冪であることを確かめる(thm-cc-catastrophic)。そうでなければ共通因子で割った符号化器に替える(prop-cc-equivalent により符号は変わらない)。
  2. 状態遷移の表を作る:$2^m$ 個の状態と入力 $0,1$ ごとに、次の状態と出力を書く(上の $(7,5)$ 符号の表)。
  3. 符号化する:状態 $0$ から始め、情報 $L$ ビットと $0$ を $m$ 個入れて、出力を時刻順に並べる。
  4. 自由距離を求める:状態図で迂回路の重みの最小値を探す(cor-cc-detour)。重みの分布が要れば、状態ごとの母関数の連立方程式を解く(thm-cc-transfer の証明)。
  5. 復号する:受信語を時刻ごとの $n$ ビットに区切り、$M_t$ を時刻 $0$ から順に計算して、各状態で最小を与えた辺を記録する。時刻 $L+m$ の状態 $0$ から後ろへたどり、入力の列の最初の $L$ ビットを出力する(thm-cc-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 本からなる。

Viterbi 復号

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 の手順は正しい情報を返す。

誤りが 3 個の場合

$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$ を含む

補足

  • ターボ符号:構成要素となる畳み込み符号化器(多くは 2 つ)に、情報ビットをそれぞれ決まった置換で並べ替えて入れ、出てくるビットを並べて送る符号である。復号では、各トレリスで前向き・後ろ向きの計算をしてビットごとの尤度を求め、それをもう一方のトレリスへ渡すことをくり返す(Mac03 §48.4、pp. 579–580)。
  • トレリスの上の確率計算:Viterbi 復号は最も確からしい符号語を求める。各ビットの事後確率を求めるには、同じトレリスの上で最小と和を和と積に替えた前向き・後ろ向きの計算を使う(Mac03 §25.3、p. 329、隠れMarkovモデル)。
  • ブロック符号との関係:終端した符号 $C_L$ は普通の 線形符号 で、Hamming符号 などと同じく生成行列と最小距離で比べられる。疎な検査行列をもつ符号との比較は LDPC符号 にある。

歴史と出典

畳み込み符号の説明(シフトレジスタによる生成、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 の証明は、この記事で書き下ろした。

関連項目

参考文献

[1]
David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003, p. 184(畳み込み符号の説明)、§25.3(p. 329、トレリス上の最小和の計算と Viterbi アルゴリズム)、§48.1–48.2(pp. 574–577、シフトレジスタ、8 進の表し方、組織的・再帰的な符号化器、図 48.3–48.5)、§48.4(pp. 579–580、ターボ符号)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する