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

リード・ソロモンコード

往々にしてノイズというものは、特定の箇所に集中して発生するものです。そのようなノイズに対して強い検出力を持つのがリード・ソロモンコードです。
リード・ソロモンコードでは 21 ビットを使用しますが、これを 3 ビットごとに区切り、その 3 ビットを $\mathbb{F}_8$ の元と思うことにします。例えば
${}^t\begin{pmatrix}1&0&1&\cdots\end{pmatrix}$
というコードがあったら、これを
${}^t\begin{pmatrix}\alpha^2+1&\cdots\end{pmatrix}={}^t\begin{pmatrix}\alpha^6&\cdots\end{pmatrix}$
と思うわけです。
リード・ソロモンコードの判定に使用する行列を
$\begin{align}H&=\begin{pmatrix}1&\alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6\\1&\alpha^2&\alpha^4&\alpha^6&\alpha^8&\alpha^{10}&\alpha^{12}\\1&\alpha^3&\alpha^6&\alpha^9&\alpha^{12}&\alpha^{15}&\alpha^{18}\\1&\alpha^4&\alpha^8&\alpha^{12}&\alpha^{16}&\alpha^{20}&\alpha^{24}\end{pmatrix}\\&=\begin{pmatrix}1&\alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6\\1&\alpha^2&\alpha^4&\alpha^6&\alpha&\alpha^3&\alpha^5\\1&\alpha^3&\alpha^6&\alpha^2&\alpha^5&\alpha&\alpha^4\\1&\alpha^4&\alpha&\alpha^5&\alpha^2&\alpha^6&\alpha^3\end{pmatrix}\end{align}$
とします。
例えば
$\vec{a}={}^t\begin{pmatrix}\alpha^3&\alpha&1&\alpha^3&1&0&0\end{pmatrix}$
とおくと
$\begin{align}H\vec{a}&=\begin{pmatrix}\alpha^3+\alpha^2+\alpha^2+\alpha^6+\alpha^4\\\alpha^3+\alpha^3+\alpha^4+\alpha^9+\alpha\\\alpha^3+\alpha^4+\alpha^6+\alpha^5+\alpha^5\\\alpha^3+\alpha^5+\alpha+\alpha^8+\alpha^2\end{pmatrix}\\&=\begin{pmatrix}\alpha^3+\alpha^6+\alpha^4\\\alpha^4+\alpha^2+\alpha\\\alpha^3+\alpha^4+\alpha^6\\\alpha^3+\alpha^5+\alpha^2\end{pmatrix}\\&=\begin{pmatrix}(\alpha+1)+(\alpha^2+1)+(\alpha^2+\alpha)\\\\(\alpha^2+\alpha)+\alpha^2+\alpha\\(\alpha+1)+(\alpha^2+\alpha)+(\alpha^2+1)\\(\alpha+1)+(\alpha^2+\alpha+1)+\alpha^2\end{pmatrix}=\begin{pmatrix}0\\0\\0\\0\end{pmatrix}\end{align}$
となり、 $\vec{a}$ はリード・ソロモンコードになります。
$H$ を行基本変形すると
$\begin{pmatrix}1&0&0&0&\alpha^3&\alpha^6&\alpha^5\\0&1&0&0&\alpha&\alpha^6&\alpha^4\\0&0&1&0&1&1&1\\0&0&0&1&\alpha^3&\alpha^2&\alpha^4\end{pmatrix}$
となるので、 $H\vec{a}=\vec{0}$ の一次独立な解として
${}^t\begin{pmatrix}\alpha^3&\alpha&1&\alpha^3&1&0&0\end{pmatrix},\\{}^t\begin{pmatrix}\alpha^6&\alpha^6&1&\alpha^2&0&1&0\end{pmatrix},\\{}^t\begin{pmatrix}\alpha^5&\alpha^4&1&\alpha^4&0&0&1\end{pmatrix}$
の三つを得ます。従ってリード・ソロモンコードでは $8^3=512$ 種類の情報を扱えることになります。