例題6.5 $${GF(2^4)}$$の原始元$${\alpha}$$および$${\alpha^3, \alpha^5}$$の最小多項式を$${M_1(x) = x^4 +x +1, M_3(x), M_5(x)}$$とし、原始BCH符号の生成多項式を

$$
g(x) = M_1(x)M_3(x)M_5(x) = 1 + x + x^2 + x^4 + x^5 + x^8 + x^{10}
$$

とする。"11000 01110 00000"を受信したとき、ユークリッド復号法を用いて送信語を推定せよ。

解答

受信多項式は$${v(x) = 1 + x + x^6 + x^7 + x^8}$$。

符号の性質
$${g(x)}$$の連続根は$${\alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6}$$だから、3重誤り訂正が可能。したがって、$${(15, 5, 7)}$$の符号であることが分かる。

シンドロームを求める。

$$
S_1 = v(\alpha) = 1 + \alpha + \alpha^6 + \alpha^7 + \alpha^8 = 1 \\
S_2 = v(\alpha^2) = 1 + \alpha^2 + \alpha^{12} + \alpha^{14} + \alpha^{1} = 1 \\
S_3 = v(\alpha^3) = 1 + \alpha^3 + \alpha^{3} + \alpha^6 + \alpha^9 = \alpha^{10} \\
S_4 = v(\alpha^4) = 1 + \alpha^4 + \alpha^9 + \alpha^{13} + \alpha^2 = 1 \\
S_5 = v(\alpha^5) = 1 + \alpha^5 + 1 + \alpha^{5} + \alpha^{10} = \alpha^{10} \\
S_6 = v(\alpha^6) = 1 + \alpha^6 + \alpha^6 + \alpha^{12} + \alpha^3 = \alpha^5 \\
$$

シンドローム多項式

$$
S(z) = 1 + z + \alpha^{10}z^2 + z^3 + \alpha^{10}z^4 + \alpha^{5}z^5
$$

誤り位置多項式を求める。$${a_0(z) = z^{2t} = z^6, a_1(z) = S(z)}$$として

$$
a_0(z) = (\alpha^{10}z + 1)a_1(z) + a_2(z), ※a_2(z) = \alpha^{10}z^3 + \alpha^5z + 1 \\
a_1(z) = (\alpha^{10}z^2 + z)a_2(z) + a_3(z) ※a_3(z) = \alpha^{5}z^2 + 1 \\
$$

ここで$${deg \lbrace a_3(z) \rbrace \leq 3-1}$$であるから終了。

$$
\begin{pmatrix}
a_2(z) \\
a_3(z) 
\end{pmatrix}
=
\begin{pmatrix}
0 & 1 \\
1 &  \alpha^{10}z^2 + z
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 &  \alpha^{10}z + 1
\end{pmatrix}
\begin{pmatrix}
a_0(z) \\
a_1(z) 
\end{pmatrix}
\\
=
\begin{pmatrix}
1 & \alpha^{10}z + 1 \\
\alpha^{10}z^2 + z &  \alpha^{5}z^3 + z + 1
\end{pmatrix}
\begin{pmatrix}
a_0(z) \\
a_1(z) 
\end{pmatrix}

$$

となり、これより、

$$
a_3(z) = (\alpha^{10}z^2 + z)a_0(z) +(  \alpha^{5}z^3 + z + 1) a_1(z) 
$$

となる。$${\gamma(  \alpha^{5}z^3 + z + 1)}$$の定数項が1になるように$${\gamma}$$を決めると1になるので、$${\sigma(z) = \alpha^{5}z^3 + z + 1}$$

誤り多項式を求める。
$${\sigma(z)}$$に$${GF(2^4)}$$の根を代入していき求めると、根は$${\alpha^3, \alpha^{10}, \alpha^{12}}$$。よって誤りロケータは、$${\alpha^{-3}=\alpha^{12}, \alpha^{-10}=\alpha^{5}, \alpha^{-12}=\alpha^{3}}$$より、誤り多項式は

$$
e(x) = x^3+x^{5}+x^{12}
$$

と得られる。よって送信語は、

$$
v(x) + e(x) = 1 + x + x^3 + x^5 + x^6 + x^7 +x^8 + x^{12}
$$

から、"11010 11110 00100"と推定される。