多重誤りを訂正する復号法として、以下がある。

• 直接的な復号法

• 間接的な復号法

  • ピーターソン法

  • バーレカンプ・マッシィ法

  • ユークリッド復号法

本noteでは2重誤り訂正と3重誤り訂正の直接的な復号法についてまとめる。

直接的な復号法

2重誤り訂正

$${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)}$$とおく。

いま、受信語の$${i+1}$$および$${j+1}$$ビット目$${i, j = 0,1,2,\cdots,n-1)}$$に誤りがあるとすると、誤り多項式が$${e(x) = x^i + x^j}$$となる。
今、$${\alpha^i, \alpha^j}$$の逆数を根に持つ多項式(式1)$${\sigma(x) = (1 - \alpha^i z)(1 - \alpha^j z)}$$を考える。この式の根の逆数が誤りロケータ(誤り位置を示すもの)になっている。この意味で、$${\sigma(x)}$$を誤り位置多項式という。式1を展開すると、

$$
\sigma(x) = (1 - \alpha^i z)(1 - \alpha^j z) \\
(式2) \sigma(x) = 1 - (\alpha^i + \alpha^j)z + \alpha^i\alpha^j z^2\\
$$

次に、受信多項式に生成多項式の2つの根$${\alpha, \alpha^3}$$をそれぞれ代入したシンドロームを$${S_1, S_3}$$とおくと、

$$
(式3) S_1 = v(\alpha) = e(\alpha)=\alpha^i+\alpha^j \\
(式4) S_3 = v(\alpha^3) = e(\alpha^3)=\alpha^{3i}+\alpha^{3j} \\
$$

式3を3乗して、

$$
S_1^3 = (\alpha^{2i} + \alpha^{2i})(\alpha^i + \alpha^j) \\
= \alpha^{3i} + \alpha^{2i}\alpha^j + \alpha^i\alpha^{2j} + \alpha^{3i} \\
= \alpha^{3i} + \alpha^{3i} + \alpha^{i}\alpha^j( \alpha^i + \alpha^j) \\
= S_3 + \alpha^{i}\alpha^jS_1
$$

$${\alpha^{i}\alpha^j}$$について解くと、$${\alpha^{i}\alpha^j = S_1^2 - S_3 / S_1}$$。これを式2に代入すると

$$
\sigma(x) = 1 - S_1z + (S_1^2 - S_3 / S_1) z^2\\
$$

となって係数がシンドロームから決まることが分かる。この多項式を解けば誤り位置が得られる。多項式を解くのは別途考慮が必要だが、ひとまず以上で手法は概ね明確になった。

誤りの数が少ない場合