3 日でわか(らせ)る符号理論(3 日目・午前の部)

数学・代数

リード・ソロモンコードと誤りの訂正

さて、リード・ソロモンコード \vec{a} において i+1 番目が \beta\in\mathbb{F}_8 だけ変化したとします。つまり、3i+1,3i+2,3i+3 ビット目に誤りが集中した場合です。このときは
H(\vec{a}+\beta\vec{e_{i+1}})=\beta H\vec{e_{i+1}}=\begin{pmatrix}\beta\alpha^i\\\beta\alpha^{2i}\\\beta\alpha^{3i}\\\beta\alpha^{4i}\end{pmatrix}
となるので
\alpha^i=(\beta\alpha^{2i})/(\beta\alpha^i),\beta=\beta\alpha^i/\alpha^i
として \alpha^i と \beta を求めることができるので、誤りの訂正ができます。
次に リード・ソロモンコード \vec{a} において i+1 番目が \beta\in\mathbb{F}_8、j+1 番目が \gamma\in\mathbb{F}_8 だけ変化したとします。このときは
H(\vec{a}+\beta\vec{e_{i+1}}+\gamma\vec{e_{j+1}})=\beta H\vec{e_{i+1}}+\gamma H\vec{e_{j+1}}=\begin{pmatrix}\beta\alpha^i+\gamma\alpha^j\\\beta\alpha^{2i}+\gamma\alpha^{2j}\\\beta\alpha^{3i}+\gamma\alpha^{3j}\\\beta\alpha^{4i}+\gamma\alpha^{4j}\end{pmatrix}
となります。\delta=\alpha^i,\varepsilon=\alpha^j とおき
\begin{align}s_1&=\beta\delta+\gamma\varepsilon\\s_2&=\beta\delta^2+\gamma\varepsilon^2\\s_3&=\beta\delta^3+\gamma\varepsilon^3\\s_4&=\beta\delta^4+\gamma\varepsilon^4\end{align}
とおきます。
まず最初に \delta と \varepsilon を求めます。
\delta^2-(\delta+\varepsilon)\delta+\delta\varepsilon=0,\varepsilon^2-(\delta+\varepsilon)\varepsilon+\delta\varepsilon=0 … (*)
(*) の第 1 式の両辺に \beta\delta を、第 2 式の両辺に \gamma\varepsilon を掛けて加えると
(\beta\delta^3+\gamma\varepsilon^3)-(\delta+\varepsilon)(\beta\delta^2+\gamma\varepsilon^2)+\delta\varepsilon(\beta\delta+\gamma\varepsilon)=0
すなわち
s_3-s_2(\delta+\varepsilon)+s_1(\delta\varepsilon)=0
を得ます。
同様に、(*) の第 1 式の両辺に \beta\delta^2 を、第 2 式の両辺に \gamma\varepsilon^2 を掛けて加えることで
s_4-s_3(\delta+\varepsilon)+s_2(\delta\varepsilon)=0
を得ます。これによって \delta+\varepsilon と \delta\varepsilon に関する連立方程式を得るので、\delta+\varepsilon と \delta\varepsilon が求まり、さらに二次方程式
x^2-(\delta+\varepsilon)x+\delta\varepsilon=0
を解いて \delta と \varepsilon が得られます。
\delta と \varepsilon が得られたら
s_1=\beta\delta+\gamma\varepsilon,s_2=\beta\delta^2+\gamma\varepsilon^2
が \beta と \gamma の連立方程式になるので、\beta と \gamma も求まり、誤りを訂正できることになります。
午後の部で、二つの実例を元にして実際の計算を見て行くことにしましょう。