直接的な復号法(3重誤り)

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

上記noteで2重誤りに対する直接的な復号法を記した。本noteでは参考書にはない3重誤りにおける誤り位置多項式導出を行い、3重誤りの直接的な復号法を記す。

以前の記事と同様、$${GF(2^m)}$$の原始元を$${\alpha}$$とし、符号長nを$${2^m-1}$$とする$${(n, k, d_{min})}$$原始BCH符号の復号を考える。生成多項式は、連続根$${\alpha, \alpha^2,\cdots,\alpha^{2t} (t \geq 2)}$$を持つとする。受信多項式を$${v(x)}$$とし、誤り多項式$${e(x)}$$とおく。

3重誤りの位置がそれぞれp+1, q+1, r+1とすると、誤り多項式は$${e(x) = x^p + x^q+x^r}$$となる。誤り位置多項式は

$$
\sigma(x) = (1 - \alpha^p z)(1 - \alpha^q z)(1 - \alpha^r z) \\
=1 + (\alpha^p + \alpha^q + \alpha^r) z + (\alpha^p \alpha^q + \alpha^q\alpha^r +\alpha^r\alpha^p)z^2 +\alpha^p\alpha^q\alpha^rz^3
$$

2重誤りの時同様に各係数をシンドロームで表せればよい。まず$${\alpha}$$を受信多項式に代入したシンドローム$${S_1}$$は$${S_1 = \alpha^p + \alpha^q + \alpha^r}$$であるから、$${z^1}$$の係数は$${S_1}$$である。
次に$${\alpha^3,\alpha^5}$$を受信多項式に代入したシンドローム$${S_3, S_5}$$は

$$
S_3 = v(\alpha^3)=e(\alpha^3)=\alpha^{3p} + \alpha^{3q} + \alpha^{3r} \\
S_5 = v(\alpha^5)=e(\alpha^5)=\alpha^{5p} + \alpha^{5q} + \alpha^{5r}
$$

$${S_1}$$の3乗を計算してみると、

$$
S_1^3 = (\alpha^{2p} + \alpha^{2q} + \alpha^{2r})(\alpha^{p} + \alpha^{q} + \alpha^{r}) \\
= \alpha^{3p} + \alpha^{2p}(\alpha^{q} + \alpha^{r}) \\
+\alpha^{3q} + \alpha^{2q}(\alpha^{r} + \alpha^{p}) \\
+\alpha^{3r} + \alpha^{2r}(\alpha^{p} + \alpha^{q}) \\
= S_3 + \alpha^p\alpha^p\alpha^q + \alpha^p\alpha^r\alpha^p \\
+  \alpha^q\alpha^q\alpha^r + \alpha^q\alpha^p\alpha^q \\
+  \alpha^r\alpha^r\alpha^p + \alpha^r\alpha^q\alpha^r \\
= S_3 + (\alpha^p+ \alpha^q)\alpha^p\alpha^q + (\alpha^q + \alpha^r)\alpha^q\alpha^r + (\alpha^r+\alpha^p)\alpha^r\alpha^p \\
= S_3 + (S_1 + \alpha^r)\alpha^p\alpha^q + (S_1 + \alpha^p)\alpha^q\alpha^r + (S_1 +\alpha^q)\alpha^r\alpha^p \\
= S_3 + S_1(\alpha^p\alpha^q +\alpha^q\alpha^r +\alpha^r\alpha^p) + \alpha^p\alpha^q\alpha^r \\
$$

というわけで、誤り位置多項式の不明な係数と同じような積和項が現れてくる。
同様に、$${S_1}$$の5乗を計算してみると、