4-1 線形符号

1　距離と検査行列

有限体 $F$ 上の 長さ $n$ の線形符号 は $F^n$ の線形部分空間 $C$ である。$\dim_F C=k$ なら $[n,k]$ 符号と呼ぶ。$u,v\in F^n$ の Hamming距離 $d(u,v)$ は成分の異なる位置の個数、$v$ の 重み $\operatorname{wt}(v)$ は非零成分の個数である。$d(u,v)=\operatorname{wt}(u-v)$。$C$ が少なくとも二語を持つとき、最小距離 を異なる二符号語の距離の最小値とする。線形符号ではこれは $k\ge1$ に当たる。線形性から
$$d_{\min}(C)=\min_{0\ne c\in C}\operatorname{wt}(c).\tag{1}$$
実際、二符号語の差は非零符号語であり、逆に非零符号語 $c$ は $0$ と $c$ の差である。零符号 $C=\{0\}$ には異なる二語がないため、この定義では最小距離を付けない。$k$ 行の生成行列 $G$ の行を $C$ の基底に選べば $C=\{uG:u\in F^k\}$。さらに $n-k$ 行の行列 $H$ の行を $C$ に直交する空間の基底に選べば、階数・次元定理から $C=\{v\in F^n:Hv^T=0\}$ である。$H$ を検査行列と呼ぶ。
受信語 $r=c+e$ に対し 症候 は $Hr^T=He^T$。$j$ 番目の一記号だけが非零値 $\lambda\in F^\times$ だけ変わったなら、症候は $H$ の第 $j$ 列の $\lambda$ 倍になる。二元体では非零値は1だけなので列をそのまま照合できるが、一般の有限体では位置と誤りの値を併せて調べる。ただし症候だけで常に誤りが一意に定まるわけではない。
例えば $\mathbf F_3$ の反復符号 $\{(a,a,a):a\in\mathbf F_3\}$ では $H=\begin{psmallmatrix}1&-1&0\\1&0&-1\end{psmallmatrix}$ とできる。$(1,1,1)$ の第2成分に誤り $2$ が加わった受信語は $(1,0,1)$。その症候は $(1,0)^T=2(-1,0)^T$ であり、第2列を誤り値2倍したものになっている。

2　小さい符号

$\mathbb F_2^3$ の部分空間 $C=\{000,111\}$ を考える。生成行列を $G=(1\ 1\ 1)$、検査行列を
$$H=\begin{pmatrix}1&1&0\\1&0&1\end{pmatrix}$$
とすると $C=\{uG:u\in\mathbb F_2\}=\{v:Hv^T=0\}$。後者は二本の式 $v_1+v_2=0,v_1+v_3=0$ から分かる。異なる符号語のHamming距離は3なので、最小距離は3。
受信語 $r=c+e$ の 症候 $Hr^T=He^T$ は誤りの位置を示す。一個だけ誤ったとき、位置1,2,3の症候はそれぞれ $H$ の列 $(1,1)^T,(1,0)^T,(0,1)^T$。三列は相異なる非零ベクトルなので位置を一意に特定できる。例えば送信 $111$、受信 $101$ の症候は $(1,0)^T$ で位置2を戻す。
一般に最小距離が $d$ の符号では、半径 $t$ のHamming球が互いに交わらないための十分条件は $2t< d$ である。もし受信語 $r$ が相異なる符号語 $c,c'$ の両方から距離 $t$ 以下なら、三角不等式で $d(c,c')\le d(c,r)+d(r,c')\le2t< d$ となって矛盾する。従って $t=\lfloor(d-1)/2\rfloor$ 個までの誤りは、最も近い符号語を選ぶ方法で一意に訂正できる。この符号では $d=3$ なので $t=1$。二個の誤りでは、例えば $000$ を送って $110$ を受けると、$110$ は $111$ から距離1であり、同じ手順は誤訂正する。

3　演習と解答

演習1。 受信語 $011$ の症候と訂正語を求めよ。
解答。 $H(0,1,1)^T=(1,1)^T$。位置1を反転して $111$ に訂正する。
演習2。 $C=\{000,111\}$ について、$d_{\min}(C)=3$ を式 (1) と二符号語の比較の両方から求めよ。
解答。 非零符号語は $111$ だけで重み3なので式 (1) は3。異なる二符号語は $000,111$ の一組だけで、三成分すべて異なるから距離3。
一般の符号理論と復号算法は本書では扱わない。