巡回符号のパリティ検査行列(その2)

符号長nが奇数であるような巡回符号のパリティ検査行列について 前章とは別の視点から考察する. 前章で見たように, Cを(n,k)-巡回符号とすると, $C=(g(X))\subset {\bf F}_2[X]/(X^n-1)$と書ける.

このとき,

$$f(X)\in C \Longleftrightarrow \text{全ての}g(X)\text{の根}\alpha \text{について, }f(\alpha)=0$$

が成り立つ. とくに $\Longleftarrow$は, nが奇数のときXⁿ-1が重根を持たない ことから従う.

$f(X)=f_0+f_1X+\cdots+f_{n-1}X^{n-1}\in C$と書き表したとき,

$$f(\alpha) =f_0+f_1\alpha+\cdots+f_{n-1}\alpha^{n-1} =\begi... ...begin{pmatrix}1\\ \alpha \\ \vdots \\ \alpha^{n-1}\end{pmatrix}$$

と書ける.

g(X)の${\bf F}_2$上での既約分解 (すなわち, ${\bf F}_2[X]$の既約元の積に書き表すこと)が,

$$g(X)=g_1(X)g_2(X)\cdots g_s(X)$$

であるとき,

$$\alpha_i : g_i(X)\text{の根} \Longrightarrow \alpha_i^2 : g... ...lpha)^2=0) \Longrightarrow \alpha_i^{2^j} : g_i(X)\text{の根}$$

より,

$$g(X)\text{の全ての根} =\alpha_1,\alpha_1^2,\alpha_1^4,\cdots... ..._2^2,\alpha_2^4,\cdots, \alpha_s,\alpha_s^2,\alpha_s^4,\cdots$$

となる.

ここで,

$$H= \begin{pmatrix} 1 & 1 & \cdots & 1 \\ \alpha_1 & \alph... ...} & \alpha_2^{n-1} & \cdots & \alpha_s^{n-1} \\ \end{pmatrix}$$

とおくと,

$$f=(f_0,f_1,\dots,f_{n-1})\in C \Longleftrightarrow fH=0$$

であることがわかる.

注意 1.1   $H\not\in M(n,s;{\bf F}_2)$であることに注意.

例 1.2 (tex2html_wrap_inline$(7,4,3)$-ハミング符号)  

X⁷-1=(X+1)(X³+X+1)(X³+X²+1)

$$C=(X^3+X+1)\subset {\bf F}_2[X]/(X^7-1)$$

このとき, $\alpha$ をX³+X+1の根(すなわち, $\alpha^3+\alpha+1=0$) とすると, $f(X)=f_0+f_1X+\cdots+f_6X^6\in{\bf F}_2[X]/(X^7-1)$に対して,

$$f(X)\in (X^3+X+1) \Longleftrightarrow (X^3+X+1)\vert f(X) ... ...\begin{pmatrix}1 \\ \alpha \\ \vdots \\ \alpha^6\end{pmatrix}=0$$

が成り立つ. よって, Cのパリティ検査行列は,

$$H= \begin{pmatrix} 1 \\ \alpha \\ \vdots \\ \alpha^6 \end{pmatrix}$$

となる.

前章のパリティ検査行列との関係.

$${\bf F}_2(\alpha)={\bf F}_2+{\bf F}_2\alpha+{\bf F}_2\alpha^2\cong {\bf F}_2^3$$

より,

${\bf F}_2(\alpha)={\bf F}_{2^{3}}$	${\bf F}_2^3$
1	1	0	0
$\alpha$	0	1	0
$\alpha^2$	0	0	1
$1+\alpha=\alpha^3$	1	1	0
$\alpha+\alpha^2=\alpha^4$	0	1	1
$1+\alpha+\alpha^2=\alpha^5$	1	1	1
$1+\alpha^2=\alpha^6$	1	0	1

上の対応から,

$$M(6,1;{\bf F}_{2^{3}})\ni \begin{pmatrix} 1 \\ \alpha \\ \v... ... 1 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \in M(6,3;{\bf F}_2)$$

送信語 $(a_0,a_1,\dots,a_6)$を送って,

$$\begin{pmatrix}b_0&b_2&\cdots&b_6\end{pmatrix} =\begin{pmatri... ..._6\end{pmatrix} +\begin{pmatrix}e_0&e_2&\cdots&e_6\end{pmatrix}$$

となったとすると,
$$\begin{align*}\begin{pmatrix}b_0&b_2&\cdots&b_6\end{pmatrix} \begin{pmatrix} 1 ... ...\ \alpha^6 \end{pmatrix} \\ &= e_0+e_1\alpha+\cdots+e_6\alpha^6 \end{align*}$$
となる. エラー個所が一ヵ所ならば, 唯一つのiについてのみe_i=1で, 他のe_jについてはe_j=0となるから,

エラー箇所	0	1	2	3	4	5	6
bH	1	$\alpha$	$\alpha^2$	$\alpha^3$	$\alpha^4$	$\alpha^5$	$\alpha^6$

となることが分かる.

誤り訂正手順

1.

受信語 b=b(X)に対して, ${\mathbf s}=b(\alpha)$を計算,

2.

s=ならば, 誤りなし,

3.

${\mathbf s}=\alpha^i$ならば, b+e_i, ${\mathbf e}_i:= \begin{pmatrix} 0 & \cdots & 0 & 1 & 0 &\cdots & 0 \end{pmatrix}$ で誤り訂正.

考察 1.3   前々章のハミング符号の誤り訂正アルゴリズムと比較せよ.