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

数学・代数

リード・ソロモンコードと誤りの訂正(続き)

計算例 I

\vec{b}={}^t\begin{pmatrix}\alpha^3&\alpha&\alpha^6&\alpha^3&1&\alpha&0\end{pmatrix}
が送られてきたとします。
\begin{align}H\vec{b}&=\begin{pmatrix}\alpha^3+\alpha^2+\alpha^8+\alpha^6+\alpha^4+\alpha^6\\\alpha^3+\alpha^3+\alpha^{10}+\alpha^9+\alpha+\alpha^4\\\alpha^3+\alpha^4+\alpha^{12}+\alpha^5+\alpha^5+\alpha^2\\\alpha^3+\alpha^5+\alpha^7+\alpha^8+\alpha^2+\alpha^7\end{pmatrix}\\&=\begin{pmatrix}\alpha^3+\alpha^2+\alpha+\alpha^4\\\alpha^3+\alpha^2+\alpha+\alpha^4\\\alpha^3+\alpha^4+\alpha^5+\alpha^2\\\alpha^3+\alpha^5+\alpha+\alpha^2\end{pmatrix}=\begin{pmatrix}\alpha^3\\\alpha^3\\\alpha^4\\\alpha\end{pmatrix}\end{align}
となります。このことから
\alpha^3(\delta+\varepsilon)+\alpha^3(\delta\varepsilon)=\alpha^4,\alpha^4(\delta+\varepsilon)+\alpha^3(\delta\varepsilon)=\alpha
という連立方程式を得ます。各式の両辺に \alpha^4 を掛けて
(\delta+\varepsilon)+\delta\varepsilon=\alpha,\alpha(\delta+\varepsilon)+\delta\varepsilon=\alpha^5
となるので辺辺加えて
\alpha^3(\delta+\varepsilon)=\alpha^6
すなわち \delta+\varepsilon=\alpha^3 を得ます。従って \delta\varepsilon=1 となります。これらのことから \delta=\alpha^2,\varepsilon=\alpha^5 となるので
\alpha^2\beta+\alpha^5\gamma=\alpha^3,\alpha^4\beta+\alpha^{10}\gamma=\alpha^3
すなわち
\beta+\alpha^3\gamma=\alpha,\alpha\beta+\gamma=1
という連立方程式を得ます。第 1 式の \alpha 倍と第 2 式を辺辺加えて
\alpha^5\gamma=\alpha^6
すなわち \gamma=\alpha となるので第 1 式に代入して \beta=\alpha^2 を得ます。従って正しいコードは 3 番目を \alpha^2、6 番目を \alpha 訂正して
\begin{align}\vec{a}&={}^t\begin{pmatrix}\alpha^3&\alpha&\alpha^6+\alpha^2&\alpha^3&1&\alpha+\alpha&0\end{pmatrix}\\&={}^t\begin{pmatrix}\alpha^3&\alpha&1&\alpha^3&1&0&0\end{pmatrix}\end{align}
となります。

計算例 II

\vec{b}={}^t\begin{pmatrix}\alpha^5&\alpha^4&1&\alpha&\alpha&0&1\end{pmatrix}
が送られてきたとします。
\begin{align}H\vec{b}&=\begin{pmatrix}\alpha^6+\alpha^5+\alpha^4+\alpha^2\\\alpha^6+\alpha^4+\alpha^2+1\\\alpha^5+\alpha^4+\alpha^3+1\\\alpha^6+\alpha^5\end{pmatrix}\\&=\begin{pmatrix}0\\\alpha^2+\alpha\\\alpha+1\\\alpha\end{pmatrix}=\begin{pmatrix}0\\\alpha^4\\\alpha^3\\\alpha\end{pmatrix}\end{align}
となります。このことから
\alpha^4(\delta+\varepsilon)=\alpha^3,\alpha^3(\delta+\varepsilon)+\alpha^4(\delta\varepsilon)=\alpha
という連立方程式を得ます。第 1 式から \delta+\varepsilon=\alpha^6 を得ます。従って
\alpha^2+\alpha^4(\delta\varepsilon)=\alpha
すなわち
\alpha^4(\delta\varepsilon)=\alpha^4
となるので \delta\varepsilon=1 となります。これらのことから \delta=\alpha^3,\varepsilon=\alpha^4 となるので
\alpha^3\beta+\alpha^4\gamma=0,\alpha^6\beta+\alpha^8\gamma=\alpha^4
すなわち
\beta+\alpha\gamma=0,\beta+\alpha^2\gamma=\alpha^5
という連立方程式を得ます。第 1 式と第 2 式を辺辺加えて
\alpha^4\gamma=\alpha^5
すなわち \gamma=\alpha となるので第 1 式に代入して \beta=\alpha^2 を得ます。従って正しいコードは 4 番目を \alpha^2、5 番目を \alpha 訂正して
\begin{align}\vec{a}&={}^t\begin{pmatrix}\alpha^5&\alpha^4&1&\alpha+\alpha^2&\alpha+\alpha&0&1\end{pmatrix}\\&={}^t\begin{pmatrix}\alpha^5&\alpha^4&1&\alpha^4&0&0&1\end{pmatrix}\end{align}
となります。

昨今の符号理論事情

さて、線型代数を応用した三つのコードを紹介しましたが、昨今ではこれらの方法ではなく、代数幾何を応用したコードを利用することが多く、符号理論の研究も専らそちらの方面が進められている状況です。そういった辺りを知りたい方は、その方面の専門書を繙かれることをお勧めします。
今回の参考書です。計算例等は全て同書の計算例、あるいは演習問題から引用しています。

計算数学 (新数学講座)

計算数学 (新数学講座)