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

ハミングコードでは、1 ビットの誤りまでは対応できますが、万が一それ以上の誤りがあった場合にもろさを露呈します。そこで、この方法を改良して、もし 2 ビット誤っていた場合でも訂正が効くコードを作ることにします。

BCH コード

$H=\begin{pmatrix}1&0&0&0&1&0&0&1&1&0&1&0&1&1&1\\0&1&0&0&1&1&0&1&0&1&1&1&1&0&0\\0&0&1&0&0&1&1&0&1&0&1&1&1&1&0\\0&0&0&1&0&0&1&1&0&1&0&1&1&1&1\\1&0&0&0&1&1&0&0&0&1&1&0&0&0&1\\0&0&0&1&1&0&0&0&1&1&0&0&0&1&1\\0&0&1&0&1&0&0&1&0&1&0&0&1&0&1\\0&1&1&1&1&0&1&1&1&1&0&1&1&1&1\end{pmatrix}$
とおきます。この行列に対して $H\vec{a}=\vec{0}$ を満たす $\vec{a}$ を BCH コードと言います*1。
$H$ の最初の 8 列からなる正方行列の行列式は 1 となるので、 $\mathrm{rank}H=8$ となり、従って $\dim\ker H=7$ *2 がわかります。従って BCH コードは $2^7=128$ 種類あることがわかります。
実際に $H$ を行基本変形してみると
$\begin{pmatrix}1&0&0&0&0&0&0&0&1&1&0&1&0&0&0\\0&1&0&0&0&0&0&0&0&1&1&0&1&0&0\\0&0&1&0&0&0&0&0&0&0&1&1&0&1&0\\0&0&0&1&0&0&0&0&0&0&0&1&1&0&1\\0&0&0&0&1&0&0&0&1&1&0&1&1&1&0\\0&0&0&0&0&1&0&0&0&1&1&0&1&1&1\\0&0&0&0&0&0&1&0&1&1&1&0&0&1&1\\0&0&0&0&0&0&0&1&1&0&1&0&0&0&1\end{pmatrix}$
となるので、 $H\vec{a}=\vec{0}$ の一次独立な解として
${}^t\begin{pmatrix}1&0&0&0&1&0&1&1&1&0&0&0&0&0&0\end{pmatrix},\\{}^t\begin{pmatrix}1&1&0&0&1&1&1&0&0&1&0&0&0&0&0\end{pmatrix},\\{}^t\begin{pmatrix}0&1&1&0&0&1&1&1&0&0&1&0&0&0&0\end{pmatrix},\\{}^t\begin{pmatrix}1&0&1&1&1&0&0&0&0&0&0&1&0&0&0\end{pmatrix},\\{}^t\begin{pmatrix}0&1&0&1&1&1&0&0&0&0&0&0&1&0&0\end{pmatrix},\\{}^t\begin{pmatrix}0&0&1&0&1&1&1&0&0&0&0&0&0&1&0\end{pmatrix},\\{}^t\begin{pmatrix}0&0&0&1&0&1&1&1&0&0&0&0&0&0&1\end{pmatrix}$
を得ます。

16 元体 $\mathbb{F}_{16}$

$x^4+x+1\in\mathbb{F}_2[x]$ は既約であることがわかっています。そこで
$\mathbb{F}_{16}=\mathbb{F}_2[x]/(x^4+x+1)$
とおくと、これはちょうど 16 個の元を持つことが確認できます。 $\mathbb{F}_8$ のときと同じように、 $x$ を含む同値類を $\alpha$ とおいて $\alpha$ のべき乗を調べると
$\begin{align}\alpha^4&=\alpha+1\\\alpha^5&=\alpha^2+\alpha\\\alpha^6&=\alpha^3+\alpha^2\\\alpha^7&=\alpha^4+\alpha^3=\alpha^3+\alpha+1\\\alpha^8&=\alpha^4+\alpha^2+\alpha=\alpha^2+1\\\alpha^9&=\alpha^3+\alpha\\\alpha^{10}&=\alpha^4+\alpha^2=\alpha^2+\alpha+1\\\alpha^{11}&=\alpha^3+\alpha^2+\alpha\\\alpha^{12}&=\alpha^4+\alpha^3+\alpha^2=\alpha^3+\alpha^2+\alpha+1\\\alpha^{13}&=\alpha^4+\alpha^3+\alpha^2+\alpha=\alpha^3+\alpha^2+1\\\alpha^{14}&=\alpha^4+\alpha^3+\alpha=\alpha^3+1\\\alpha^{15}&=\alpha^4+\alpha=1\end{align}$
となって、今度は $\alpha^{15}=1$ となることがわかります。
この $\mathbb{F}_{16}$ を用いて、BCH コードの仕組みを調べていくことにしますが、続きは夜の部で。