ピーターソン法

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

ピーターソン法は間接的な復号法に分類されている。直接的な復号法との違いは、誤り位置多項式係数のシンドロームからの求め方が、任意の誤り数について定義されてる点だろう。正直何を以て直接・間接を分類しているのか良く分からない。

ではピーターソン法を説明する。
導入は誤り位置多項式についてまでは以前の直接的な復号法の説明と同じであるので読み飛ばして良い。誤りが3つであるケースで、誤り位置の$${e(x)}$$の次数対応が$${k,l,m}$$とする。$${e(x) = x^k + x^l + x^m}$$。シンドロームは$${S_j = v(\alpha^j) = \alpha^{jk} + \alpha^{jl} + \alpha^{jm}  (j=1,2,\cdots,6) }$$。
誤り位置多項式$${\sigma(x) = (1 - \alpha^kz)(1 - \alpha^lz)(1 - \alpha^mz) = 1 + \sigma_1z + \sigma_2z^2 + \sigma_3z^3 }$$。

ここからがピーターソン法の違いになる。まず$${\sigma(\alpha^{-k}) = \sigma(\alpha^{-l}) = \sigma(\alpha^{-m}) = 0}$$より、展開後の方に代入して

$$
(6.32) \\
1 + \sigma_1\alpha^{-k} + \sigma_2\alpha^{-2k} + \sigma_3\alpha^{-3k} = 0 \\
1 + \sigma_1\alpha^{-l} + \sigma_2\alpha^{-2l} + \sigma_3\alpha^{-3l} = 0 \\
1 + \sigma_1\alpha^{-m} + \sigma_2\alpha^{-2m} + \sigma_3\alpha^{-3m} = 0
$$

それぞれ、$${\alpha^{4k},\alpha^{4l},\alpha^{4m}}$$をかけると

$$
\alpha^{4k} + \sigma_1\alpha^{3k} + \sigma_2\alpha^{2k} + \sigma_3\alpha^{k} = 0 \\
\alpha^{4l} + \sigma_1\alpha^{3l} + \sigma_2\alpha^{2l} + \sigma_3\alpha^{l} = 0 \\
\alpha^{4m} + \sigma_1\alpha^{3m} + \sigma_2\alpha^{2m} + \sigma_3\alpha^{m} = 0
$$

等式を全部足し合わせると

$$
(6.34) \\
S_4 + \sigma_1S_3 + \sigma_2S_2 + \sigma_3S_1 = 0 
$$

同様に、$${(6.32)}$$にそれぞれ、$${\alpha^{5k},\alpha^{5l},\alpha^{5m}}$$をかけてから等式全部合わせると、

$$
(6.35) \\
S_5 + \sigma_1S_4 + \sigma_2S_3 + \sigma_3S_2 = 0 
$$

同様に、$${(6.32)}$$にそれぞれ、$${\alpha^{6k},\alpha^{6l},\alpha^{6m}}$$をかけてから等式全部合わせると、

$$
(6.36) \\
S_6 + \sigma_1S_5 + \sigma_2S_4 + \sigma_3S_3 = 0 
$$

$${(6.34)}$$~$${(6.36)}$$より、

$$
S
\begin{pmatrix}
\sigma_1 \\
\sigma_2 \\
\sigma_3 \\
\end{pmatrix}
=
-
\begin{pmatrix}
S_4 \\
S_5 \\
S_6 \\
\end{pmatrix}
$$

ただし

$$
S =
\begin{pmatrix}
S_1 & S_2 & S_3 \\
S_2 & S_3 & S_4 \\
S_3 & S_4 & S_5 \\
\end{pmatrix}
$$

が得られる。行列Sが正則のときは

$$
\begin{pmatrix}
\sigma_1 \\
\sigma_2 \\
\sigma_3 \\
\end{pmatrix}
=
-S^{-1}
\begin{pmatrix}
S_4 \\
S_5 \\
S_6 \\
\end{pmatrix}
$$

により、誤り位置多項式の係数が求められる。あとは誤り位置多項式を解けばよい。