RS符号の復号
BCH符号の場合は多項式の係数が0または1なので誤り位置を求めればそれを反転することで訂正できた。
RS符号の場合、誤り位置における真の値も求める必要がある。ユークリッド復号法における方法を述べる。
$${GF(2^m)}$$における$${(n,k)}$$RS符号で、生成多項式は$${2t}$$の連続根を持つ。ユークリッド復号法においては、生成多項式$${g(x)}$$に含まれる因数によって結果が異なるので分けて説明する。
$${g(x) = (x-\alpha)(x-\alpha^2)\cdots(x-\alpha^{2t})}$$
$${g(x) = (x-\alpha^l)(x-\alpha^{l+1})\cdots(x-\alpha^{l+2t-1})}$$の場合
1の場合
すわなち$${g(x) = (x-\alpha)(x-\alpha^2)\cdots(x-\alpha^{2t})}$$の場合
(1)誤り位置の導出
s個の誤りがあるとして、誤り位置は$${i_1, i_2,\cdots,i_s}$$とすると、誤り多項式は$${e(x) = e_{i_1}x^{i_1} + e_{i_2}x^{i_2} + \cdots + e_{i_s}x^{i_s} = \sum_{k=1}^s e_{i_k}x^{i_k}}$$と書ける。$${e_{i_k}}$$は誤り数値という。受信多項式を$${v(x)}$$とすると、シンドロームは
$$
S_j = v(\alpha^j) = e(\alpha^j) = \sum_{k=1}^s e_{i_k}(\alpha^j)^{i_k} \\
S(z) = \sum_{j=1}^{2t} S_jz^{j-1}
= \sum_{j=1}^{2t} \sum_{k=1}^s e_{i_k}(\alpha^j)^{i_k}z^{j-1} \\
= \sum_{k=1}^s\sum_{j=1}^{2t} e_{i_k}(\alpha^j)^{i_k}z^{j-1} \\
$$
で与えられる。ここで、
$$
\sum_{j=1}^{2t} e_{i_k}(\alpha^j)^{i_k}z^{j-1}
\equiv
\dfrac{e_{i_k}\alpha^{i_k}}{1 - \alpha^{i_k}z}, (mod z^{2t})
$$
であるから、
$$
S(z) \equiv
\sum_{k=1}^{s}\dfrac{e_{i_k}\alpha^{i_k}}{1 - \alpha^{i_k}z}, (mod z^{2t})
$$
この式の両辺に誤り位置多項式
$$
\sigma(z) = \prod_{k=1}^s (1 - \alpha^{i_k}z)
$$
をかけると
$$
\sigma(z)S(z) \equiv
(1 - \alpha^{i_2}z)(1 - \alpha^{i_3}z) \cdots (1 - \alpha^{i_s}z)e_{i_1}\alpha^{i_1} \\
(1 - \alpha^{i_1}z)(1 - \alpha^{i_3}z) \cdots (1 - \alpha^{i_s}z)e_{i_2}\alpha^{i_2} \\
(1 - \alpha^{i_1}z)(1 - \alpha^{i_2}z) \cdots (1 - \alpha^{i_s}z)e_{i_3}\alpha^{i_3} // i_3の項なし\\
\cdots \\
(1 - \alpha^{i_1}z)(1 - \alpha^{i_2}z) \cdots (1 - \alpha^{i_{s-1}}z)e_{i_s}\alpha^{i_s} , (mod z^{2t}) \\
$$
が得られる。この右辺を$${\eta(z)}$$とおくと、
$$
\eta(z) = \sigma(z)S(z) + \phi(z)z^{2t}
$$
BCH符号と同じ手順で拡張ユークリッドアルゴリズムにより誤り位置を求める。
(2)誤り数値の導出
誤り位置多項式の根を$${\eta(z)}$$に代入すると、$${(1 - \alpha^{i_k})}$$を因数に持たない和項だけ残るから
$$
\eta(\alpha^{-i_k}) =
(1 - \alpha^{i_1}\alpha^{-i_k})
\cdots
(1 - \alpha^{i_{k-1}}\alpha^{-i_k})
\cdots
(1 - \alpha^{i_{k+1}}\alpha^{-i_k})
\cdots
(1 - \alpha^{i_{s}}\alpha^{-i_k})
e_{i_k}\alpha^{i_k}
$$
となる。一方、誤り位置多項式を$${z}$$で微分すると
$$
\sigma'(z) = - \alpha^{i_1}(1 - \alpha^{i_2}z)\cdots(1 - \alpha^{i_s}z) \\
- \alpha^{i_2}(1 - \alpha^{i_1}z)\cdots(1 - \alpha^{i_s}z) \\
\vdots \\
- \alpha^{i_s}(1 - \alpha^{i_1}z)\cdots(1 - \alpha^{i_{s-1}}z) \\
$$
これに誤り位置多項式の根を代入すると、$${(1 - \alpha^{i_k})}$$を因数に持たない和項だけ残るから
$$
\sigma'(\alpha^{-i_k}) = - \alpha^{i_k}(1 - \alpha^{i_1}\alpha^{-i_k})
\cdots
(1 - \alpha^{i_{k-1}}\alpha^{-i_k})
(1 - \alpha^{i_{k+1}}\alpha^{-i_k})
\cdots
(1 - \alpha^{i_s}\alpha^{-i_k})
$$
したがって、
$$
e_{i_k} = - \dfrac{\eta(\alpha^{-i_k})}{\sigma'(\alpha^{-i_k})}
$$
これをフォーニーの公式という。