直接的な復号法の動作例

例題で学ぶ符号理論入門　勉強メモ

例題6.3(改変) $${GF(2^4)}$$の原始元$${\alpha}$$の最小多項式を$${M_1(x) = x^4 + x+ 1}$$とする。生成多項式を$${g(x) = M_1(x)M_3(x)}$$とする(15,7,5)BCH符号において受信系列"110100101101110"を受信した。2重誤りまであり得るとして、誤りがあればこれを復号せよ。

(15,7,5)のBCHは最小距離が5なので4重誤りまでは原理的に検出が可能な符号方式だが、仮に4重誤りに対して2重誤りまでを想定した復号方法を使うと誤訂正(受信語が正しくない符号語へと変換されること)が発生しうる。あくまで2重誤りまでの範囲で推定してることに注意すること。設計上は通信路がどういうものかが、何重誤りまでを想定しなければならないかを与える。

解答 シンドロームを求める

$$
v(x) = 1 + x + x^3 + x^6 +x^8 + x^9 + x^{11} + x^{12} + x^{13} \\
S_1 = v(\alpha) = 1 + \alpha + \alpha^3 +\alpha^6 + \alpha^8 + \alpha^9 +\alpha^{11} +\alpha^{12} + \alpha^{13} \\
=\alpha^2 \\
\\
S_3 = v(\alpha^3) = 1 + \alpha^3 + \alpha^9 + \alpha^{3} + \alpha^{9} + \alpha^{12} + \alpha^{3} + \alpha^{6} + \alpha^{9} \\
=0
$$

誤り位置多項式の係数を計算する

$$
S_1 =\alpha^2 \\
S_1^2 + S_3/S_1 = \alpha^4
$$

よって、誤り位置多項式は、$${\sigma(x) = 1 + \alpha^2z + \alpha^4z^2}$$
根を求める。ひたすら代入していって確認する。

$$
\sigma(1) = 1 + \alpha^2 + \alpha^4 = \alpha^5\\ 
\sigma(\alpha) = 1 + \alpha^3 + \alpha^6 = \alpha^8\\ 
\sigma(\alpha^2) = 1 + \alpha^4 + \alpha^8 = \alpha^{10} \\ 
\sigma(\alpha^3) = 1 + \alpha^5 + \alpha^{10} = 0 \\ 
\sigma(\alpha^4) = 1 + \alpha^6 + \alpha^{12} = \alpha \\ 
\sigma(\alpha^5) = 1 + \alpha^7 + \alpha^{14} = \alpha^4 \\ 
\sigma(\alpha^6) = 1 + \alpha^8 + \alpha^{1} = \alpha^5 \\ 
\sigma(\alpha^7) = 1 + \alpha^9 + \alpha^{3} = \alpha^4 \\ 
\sigma(\alpha^8) = 1 + \alpha^{10} + \alpha^{5} = 0 \\ 
$$

誤りロケータは、$${\sigma(x)}$$の根の逆数をとって、$${\alpha^{-3} = \alpha^{12}}$$、および$${\alpha^{-8} = \alpha^7}$$となるから、誤り多項式は$${e(x)= x^7 + x^{12}}$$
したがって、
$${w(x) = v(x) + e(x) = 1 + x + x^3 + x^6 + x^7 + x^8 + x^9 + x^{11} + x^{13}}$$より、送信語は"110100111101010"と推定される。