3 日でわか(らせ)る符号理論(1 日目) - Red cat の数学よもやま話

今日から 3 日間、自身の勉強も兼ねて、符号理論にお付き合いいただくことにしましょう。

パリティビット

7 ビット*1あれば、 $2^7=128$ 種類の情報を表すことができます。しかし、通常は 8 ビット = 1 バイトの単位で情報を扱うことが一般的になっています。
そこで、与えられた 7 ビットの情報に対し、残る 1 ビットを、1 の数が奇数個になるように定めてみましょう。
すると、仮に 1 ビットだけ誤った情報が送られてきたとき、1 の数が偶数個になってしまうので、その情報が誤っていることを検出することができます。この 1 ビットのことをパリティビットと呼びます。
しかし、この方法では誤りを検出することはできても、どこが誤りなのかまでは検出できないので、訂正はできません。また、万が一 2 ビット誤っていた場合には、誤りの検出すらできなくなります。
そこで、誤った情報を検出し、なおかつ訂正するために、必然的にビット数に余裕を持たせることになります。そういった、誤りの検出・訂正の方法を与えるのが符号理論です。

ハミングコード

$H=\begin{pmatrix}1&0&0&1&0&1&1\\0&1&0&1&1&1&0\\0&0&1&0&1&1&1\end{pmatrix}$
という行列を考えます。これと
$\vec{a}={}^t\begin{pmatrix}a_1&a_2&a_3&a_4&a_5&a_6&a_7\end{pmatrix}$
の積を取ると
$H\vec{a}=\begin{pmatrix}a_1+a_4+a_6+a_7\\a_2+a_4+a_5+a_6\\a_3+a_5+a_6+a_7\end{pmatrix}$
となります。符号理論においては 0 か 1 かだけが重要なので、これらの話は、0 と 1 の二つだけの元を持つ体 $\mathbb{F}_2$ の上で考えて差し支えありません。そこで、 $a_4,a_5,a_6,a_7\in\mathbb{F}_2$ に対して $a_1,a_2,a_3\in\mathbb{F}_2$ を
$\begin{align}a_1&=a_4+a_6+a_7\\a_2&=a_4+a_5+a_6\\a_3&=a_5+a_6+a_7\end{align}$
となるように(もちろん等号は全て $\mathbb{F}_2$ の意味で)取ると
$H\vec{a}=\vec{0}=\begin{pmatrix}0\\0\\0\end{pmatrix}$
が成り立ちます。
そこで、 $H\vec{a}=\vec{0}$ が成り立つような情報だけを扱うことにしましょう。このような $\vec{a}$ のことをハミングコードと言います。 $2^4=16$ 種類の情報を、3 ビット余裕を持たせて 7 ビットで表すわけです。
これでどのようにして誤りを検出し、なおかつ訂正をすることができるのかを見て行きたいのですが、見通しを良くするための代数的な道具を一つ用意しておきます。

8 元体 $\mathbb{F}_8$

$\mathbb{F}_2$ の元を係数に持つ多項式の全体 $\mathbb{F}_2[x]$ は可換環になり、 $x^3+x+1\in\mathbb{F}_2[x]$ は既約な多項式になることがわかります。そこで
$\mathbb{F}_8=\mathbb{F}_2[x]/(x^3+x+1)$
とおくことにします。容易(?)にわかるように、 $\mathbb{F}_8$ はちょうど 8 個の元からなります。 $x$ の同値類を $\alpha$ と表すことにすれば、 $\mathbb{F}_8$ は $\mathbb{F}_2$ に、 $\alpha^3+\alpha+1=0$ を満たすような元 $\alpha$ を添加することによってできる単拡大体 $\mathbb{F}_2(\alpha)$ そのものです*2。
$\alpha$ のべき乗について調べてみると
$\begin{align}\alpha^3&=\alpha+1\\\alpha^4&=\alpha^2+\alpha\\\alpha^5&=\alpha^3+\alpha^2=\alpha^2+\alpha+1\\\alpha^6&=\alpha^3+\alpha^2+\alpha=\alpha^2+1\\\alpha^7&=\alpha^3+\alpha=1\end{align}$
が成り立つので、集合として
$\mathbb{F}_8=\{0,1,\alpha,\alpha^2,\alpha^3,\alpha^4,\alpha^5,\alpha^6\}$
ということになります。このように $\mathbb{F}_8$ の 0 以外の元を $\alpha$ のべき乗で表しておくことは、積を計算するのに便利です。後のことを考えて、0 以外の 7 個の元に関する和の表を作っておくとさらに便利です。
$\begin{array}{c|c.c.c.c.c.c.c}+&1&\alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6\\\hline 1&0&\alpha^3&\alpha^6&\alpha&\alpha^5&\alpha^4&\alpha^2\\\hdash \alpha&\alpha^3&0&\alpha^4&1&\alpha^2&\alpha^6&\alpha^5\\\hdash \alpha^2&\alpha^6&\alpha^4&0&\alpha^5&\alpha&\alpha^3&1\\\hdash \alpha^3&\alpha&1&\alpha^5&0&\alpha^6&\alpha^2&\alpha^4\\\hdash \alpha^4&\alpha^5&\alpha^2&\alpha&\alpha^6&0&1&\alpha^3\\\hdash \alpha^5&\alpha^4&\alpha^6&\alpha^3&\alpha^2&1&0&\alpha\\\hdash \alpha^6&\alpha^2&\alpha^5&1&\alpha^4&\alpha^3&\alpha&0\end{array}$

$\mathbb{F}_8$ とハミングコードと誤りの訂正

さて、ハミングコードのために用意した 3 行 7 列の行列 $H$ に対して、左から $\begin{pmatrix}1&\alpha&\alpha^2\end{pmatrix}$ を掛けると
$\begin{pmatrix}1&\alpha&\alpha^2\end{pmatrix}H=\begin{pmatrix}1&\alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6\end{pmatrix}$ … (*)
となって見通しが良くなります。(*) 式の右辺を改めて $H$ と置いても、 $\vec{a}$ がハミングコードとなる条件は $H\vec{a}=0$ *3で変わりがありません。
さて、ハミングコード $\vec{a}$ を送ったときに、 $i+1$ ビット目が誤って送られた、つまり $\vec{a}+\vec{e_{i+1}}$ が送られたとしましょう。そうすると
$H(\vec{a}+\vec{e_{i+1}})=H\vec{e_{i+1}}=\alpha^i$
となって何ビット目が誤っているかを検出することができるため、訂正が可能になるわけです。
このように、ハミングコードは 1 ビットの誤りであれば、検出し、なおかつ訂正することができます。
もし 2 ビット誤っていた場合、つまり $i+1$ ビット目と $j+1$ ビット目が誤っていた場合
$H(\vec{a}+\vec{e_{i+1}}+\vec{e_{j+1}})=H\vec{e_{i+1}}+H\vec{e_{j+1}}=\alpha^i+\alpha^j$
となり、右辺は $i\neq j$ ならば 0 にはならないので、誤っている、という事だけは検出ができます。ただし、情報が何ビット誤って送られてくるかはわからないので、このままでは $\alpha^i+\alpha^j=\alpha^k$ となる $k$ について、 $k+1$ ビット目だけが誤っていた場合との区別をつけることができないため、訂正は不可能です*4。
さらに、万が一 3 ビット誤って送られてしまうと、例えば 1 ビット目と 2 ビット目と 4 ビット目が誤っていたりすると
$H(\vec{a}+\vec{e_1}+\vec{e_2}+\vec{e_4})=H\vec{e_1}+H\vec{e_2}+H\vec{e_4}=1+\alpha+\alpha^3=0$
となってしまい、最早誤りの検出すらできなくなります。
しかし、現実には 2 ビット以上誤って情報が送られる確率はかなり低いでしょう。