5-1 巡回符号

1　回転と掛け算

語 $(c_0,c_1,c_2)$ を多項式 $c_0+c_1t+c_2t^2$ に対応させ、$R=\mathbb F_2[t]/(t^3-1)$ を考える。$t$ を掛けると $c_2+c_0t+c_1t^2$ となり、座標を一つ巡回移動する。線形符号が巡回移動で閉じることは、対応する $R$ の部分集合が $t$ 倍で閉じることと同値である。$t^3=1$ から $t^{-1}=t^2$ なので逆回転にも閉じ、線形性と合わせて全ての多項式倍に閉じる。従って巡回符号は $R$ のイデアルである。
$t^3-1=(t+1)(t^2+t+1)$ と分解する。$g=t+1$ が生成するイデアルは
$$C=\{0,1+t,t+t^2,1+t^2\}.$$
語では $000,110,011,101$、すなわち偶数個の1を持つ長さ3の符号である。最小距離は2で、一個の誤りは検出できるが、訂正位置は一意には決められない。

2　生成多項式と検査多項式

一般に $R_q=\mathbb F_q[t]/(t^n-1)$ のイデアル $C$ を商写像で $\mathbb F_q[t]$ に引き戻すと、$(t^n-1)$ を含むイデアルとなる。$\mathbb F_q[t]$ はEuclid環なので、そのイデアルは一つのモニック多項式 $g$ で生成され、$g\mid t^n-1$。従って巡回線形符号は $C=(g)$ と表せる。$g$ を生成多項式と呼ぶ。
$h=(t^n-1)/g$ と置くと、語の多項式 $c$ が $C$ に入ることと $hc=0$ が $R_q$ で成り立つことは同値である。前向きは $c=ag$ から従い、逆向きは $gh\mid hc$ なら整域 $\mathbb F_q[t]$ で $g\mid c$ となることから従う。$h$ は検査多項式である。$\deg g=r$ なら $g,tg,\ldots,t^{n-r-1}g$ の類は符号の基底となり、次元は $n-r$。独立性は、次数 $< n-r$ の $a$ について $ag$ が $t^n-1$ の倍数なら $a=0$ であることから分かる。
先の例では $g=t+1$、$h=t^2+t+1$。$\deg g=1$ だから $C$ は二次元で、表に挙げた語は $2^2=4$ 個である。$h(1+t)=t^3+1=0$ が $R$ で成立し、符号語を検査できる。

3　長さ7の巡回Hamming符号

$\mathbb F_2$ 上では $t^7-1=t^7+1$ であり、
$$t^7+1=(t+1)(t^3+t+1)(t^3+t^2+1).\tag{1}$$
$R_7=\mathbb F_2[t]/(t^7+1)$ で $g=t^3+t+1$ が生成するイデアル $C=(g)$ を考える。検査多項式は
$$h=\frac{t^7+1}{g}=t^4+t^2+t+1.$$
$\deg g=3$ なので次元は $7-3=4$。基底 $g,tg,t^2g,t^3g$ を係数ベクトルで並べると生成行列
$$G=\begin{pmatrix} 1&1&0&1&0&0&0\\ 0&1&1&0&1&0&0\\ 0&0&1&1&0&1&0\\ 0&0&0&1&1&0&1 \end{pmatrix}\tag{2}$$
を得る。従って符号語は $2^4=16$ 個ある。
最小距離も多項式から求められる。$g=t^3+t+1$ は0と1を根にもたない三次式なので既約である。根を $\alpha\in\mathbb F_8$ とすると、$\alpha\ne0,1$ であり、$\mathbb F_8^\times$ の位数は7だから $\alpha$ の位数は7である。
重み1の語 $t^i$ は $g$ で割り切れない。重み2の語が $C$ に入ると仮定し、巡回移動して $1+t^d$（$1\le d\le6$）の形にする。$g\mid1+t^d$ なら $1+\alpha^d=0$、すなわち $\alpha^d=1$ となるが、$\alpha$ の位数7に反する。一方、$g$ 自身の係数ベクトルは重み3である。従って
$$\boxed{d_{\min}(C)=3.}\tag{3}$$
第4章の $2e< d_{\min}$ を使えば、この符号は一個の誤りを一意に訂正できる。長さ3の偶重み符号では一誤りを検出するだけだったが、長さ7では冗長な3座標により誤り位置まで区別できる。

4　演習と解答

演習。 $110$ を巡回移動した語が $C$ に属することを多項式で示せ。
解答。 $110\leftrightarrow1+t$。$t(1+t)=t+t^2\leftrightarrow011$ で、$g$ の倍数だから $C$ に属する。
演習。 同じ環 $R$ で $g=t^2+t+1$ が生成する巡回符号を求め、最小距離を答えよ。
解答。 $tg=t^3+t^2+t=1+t+t^2=g$ が $R$ で成り立つので $(g)=\{0,g\}$。語は $000,111$ で、最小距離は3である。
演習。 長さ7の符号で情報多項式 $a=1+t^2+t^3$ を式 (2) の基底により符号化せよ。検査多項式を掛けて符号語であることも確かめよ。
解答。
$$ag=g+t^2g+t^3g=1+t+t^2+t^3+t^4+t^5+t^6,$$
従って語は $1111111$。また $h(ag)=a(t^7+1)=0$ が $R_7$ で成り立つ。
符号の距離の上界・下界や効率的な復号算法は本書では扱わない。