ピーターソン法　例題

例題6.4 $${GF(2^4)}$$上の原始元$${\alpha}$$の最小多項式を$${M_1(x) = x^4 + x + 1}$$とする。符号長15の原始BCH符号の生成多項式を$${g(x) = M_1(x)M_3(x)M_5(x) = 1 + x + x^2 + x^4 + x^5 + x^8 + x^{10}}$$とするとき、次の問に答えよ。ただし、$${M_1(x),M_3(x), M_5(x)}$$はそれぞれ$${\alpha, \alpha^3, \alpha^5}$$の最小多項式である。

(1)符号のパラメータ$${(n,k,d_{min})}$$を求めよ
(2)受信語"101000100110010"をピーターソン法を用いて復号せよ

解答(1) n=15。n-kは生成多項式の次数で与えられるから10。したがってk=5。$${d_{min}}$$は連続根の数+1で与えられる。$${M_1(x)}$$の根は$${\alpha, \alpha^2, \alpha^4, \alpha^8}$$。$${M_3(x)}$$の根は$${\alpha^3, \alpha^6, \alpha^{12}, \alpha^9}$$。$${M_5(x)}$$の根は$${\alpha^5, \alpha^{10}}$$。したがって、$${g(x)}$$の一番長い連続根は$${\alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6}$$であり、6つなので、$${d_{min}}$$は7。よってこのBCH符号は、$${(15,5,7)}$$である。
解答(2) 受信語

$$
v(x) = 1 + x^2 + x^6 + x^9 + x^{10} + x^{13} 
$$

シンドロームを計算する。

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

$$

誤り位置多項式の係数について以下が成り立つ。

$$
\begin{pmatrix}
\alpha^{14} & \alpha^{13} & 1 \\
\alpha^{13} & 1 & \alpha^{11} \\
1 & \alpha^{11} & \alpha^{5} \\
\end{pmatrix}
\begin{pmatrix}
\sigma_1 \\
\sigma_2 \\
\sigma_3 \\
\end{pmatrix}
=
-
\begin{pmatrix}
\alpha^{11} \\
\alpha^{5} \\
1 \\
\end{pmatrix}
$$

係数行列は正則なので、解ける

$$
\begin{pmatrix}
\sigma_1 \\
\sigma_2 \\
\sigma_3 \\
\end{pmatrix}
=
\begin{pmatrix}
\alpha^{14} & \alpha^{13} & 1 \\
\alpha^{13} & 1 & \alpha^{11} \\
1 & \alpha^{11} & \alpha^{5} \\
\end{pmatrix}^{-1}
\begin{pmatrix}
\alpha^{11} \\
\alpha^{5} \\
1 \\
\end{pmatrix}
=
\begin{pmatrix}
\alpha^{14} \\
\alpha^{11} \\
\alpha^{14} \\
\end{pmatrix}
$$

したがって誤り位置多項式は$${\sigma(x) = 1+ \alpha^{14}z + \alpha^{11}z^2 + \alpha^{14}z^3}$$

これを$${GF(2^4)}$$の元を順次代入して解くと$${\alpha^8, \alpha^{10}, \alpha^{13}}$$が得られる。この逆数から誤りロケータ$${\alpha^7, \alpha^{5}, \alpha^{2}}$$を得る。
したがって誤り多項式は$${e(x) = x^2 + x^5 + x^7}$$
よって送信語は
$${w(x) = v(x) + e(x) = 1 + x^5 + x^6 + x^7 + x^9 + x^{10} + x^{13}}$$より、100001110110010と推定される。

ちなみに、$${GF(2^4)}$$上の行列が正則であることや逆行列を求める場合掃き出し法を使って解けばよい。