巡回符号のパリティ検査行列

今度は, パリティ検査行列を求めてみよう.

$$\begin{CD} {\bf F}_2^k @>{T_G}>> {\bf F}_2^n @>{T_H}>> {\bf ... ...M(n,n-k), \quad \operatorname{rank}H=n-k, \quad GH=O \end{CD}$$

g(X)h(X)=Xⁿ-1

なる $h(X)\in{\bf F}_2[X]$, $\deg h(X)=k$をとると,

$$f(X)\in{\bf F}_2[X],\quad \deg f\le n$$

に対して,

$$f(X)h(X)\equiv 0 \in {\bf F}_2[X]/(X^n-1) \Longleftrightarrow f(X)\in (g(X))=C$$

ここで,

$$f(X)h(X)\equiv 0 \in {\bf F}_2[X]/(X^n-1) \Longleftrightarrow (fh)_k=(fh)_{k_1}=\cdots =(fh)_{n-2}=(fh)_{n-1}=0$$

である. なぜなら,

$$(fh)_k=(fh)_{k_1}=\cdots =(fh)_{n-2}=(fh)_{n-1}=0$$

ならば, $\deg (fh)\le n+k-1$より,

$$f(X)h(X) \mod (X^n-1)$$

の次数は, k-1 以下. 一方,

h(X) | gcd(f(X)h(X),Xⁿ-1)

より, 結局,

$$f(X)h(X)\equiv 0\mod (X^n-1)$$

となるからである.

よって,

$$T_H : {\bf F}_2^n\ni(f_0,f_1,\dots,f_{n-1}) \longmapsto ((fh)_{n-1},(fh)_{n-2},\dots,(fh)_k)\in {\bf F}_2^{n-k}$$

とすると,

$$T_H(f)=0 \Longleftrightarrow f\in C$$

となる.

このT_Hの表現行列Hは, 簡単な計算で,

$$H= \begin{pmatrix} & O & & h_k \\ & h_k & \cdots & \vdots... ...ts & h_0 \\ h_1 & h_0 & & \\ h_0 & & O & \\ \end{pmatrix}$$

となることがわかる.

問題 4.1   前節で求めた生成行列Gと上で求めたパリティ検査行列Hの積GHが 零行列になることを確かめよ.