ハミング符号再訪

ハミング符号は誤り訂正の基礎

The Continuing Story of Error Correction Code 2 - Smile Engineering Blog で7ビットハミング符号を構成してみました。
このハミング符号はSECDED、CRC符号、BCH符号、リードソロモン符号などの基礎となっています。
ハミング符号に色々なアイデアを追加して更に強力な訂正符号が作り出されていったわけですね。
これらの符号を理解するためにハミング符号をもっと深堀してみましょう。今回は訂正符号で頻繁に登場する排他論理和（XOR）について見ていきます。

排他論理和

入力をA、Bとしたときに出力Xが以下のようになる演算が排他論理和です。

$A$	$B$	$X$
0	0	0
0	1	1
1	0	1
1	1	0

なんか、この出力の並びどこかで見たような・・・
The Continuing Story of Error Correction Code 2 - Smile Engineering Blog の「検査符号の計算方法」で登場したこの演算。

$0+0=0 \\ 0+1=1 \\ 1+0=1 \\ 1+1=0$

これですね。
排他論理和は桁上がりを無視したビットの足し算になっています。
2を法とした演算ですね。

$2 \equiv 0 (mod 2)$

なので $1 + 1 = 0$ となります。

ちなみに引き算はどうなってるんよ

とりあえず普通に引き算をしてみましょう。

$0-0=0 \\ 0-1=-1 \\ 1-0=1 \\ 1-1=0$

ここで $0 - 1$ が $-1$ になってしまいますが、 $0$ と $1$ しかないはずなのに $-1$ ってどうしたらいいんでしょう？
足し算を見てみると計算のルールとして $1 + 1 = 0$ と定義しているので

$1 + 1 = 0 \\ 1 =-1$

より $0 - 1 = 1$ としてしまいます。
よって、引き算は以下のようになります。

$0-0=0 \\ 0-1=1 \\ 1-0=1 \\ 1-1=0$

この演算、足し算と見比べてみると演算の記号が $+$ から $-$ に変わっただけで他は同じですね。
このビット単位の演算では足し算も引き算も結果は同じになります。
引き算も2を法とした演算と考えれば

$1 \equiv -1 (mod 2)$

となるので $0 - 1 = 1$ となります。

排他論理和の不思議な性質

The Continuing Story of Error Correction Code 2 - Smile Engineering Blogで作ったハミング符号の $P_{3}$ 、 $P_{2}$ 、 $P_{1}$ を

$(P_{3},P_{2},P_{1})$

と表すことにします。 $P_{3}=1$ 、 $P_{2}=0$ 、 $P_{1}=1$ なら

$(1,0,1)$

となります。

この3ビットのパリティを加算します。加算は先ほど示したルールに従いビットごとに行います。
3ビットのパリティを3個適当に取り出して加算してみましょう。
とりあえず $(1,0,1)$ 、 $(0,0,1)$ 、 $(0,1,1)$ の3個を選んでみました。

$(1,0,1)+(0,0,1)+(1,1,0)=(0,1,0)$

答えは $(0,1,0)$ ですね。ではこの $(0,1,0)$ に再度 $(1,0,1)$ 、 $(0,0,1)$ 、 $(0,1,1)$ を加算してみます。

$(0,1,0)+(1,0,1)+(0,0,1)+(1,1,0)=(0,0,0)$

答えは $(0,0,0)$ になります。加算した結果に更に同じものを加算すると答えは0になるんですね。
なんか、不思議な感じがしますがこの演算は加算と減算は同じである、ということを思い出すと納得がいきます。

$(1,0,1)+(0,0,1)+(1,1,0)=(0,1,0) \\ (0,1,0)-(1,0,1)-(0,0,1)-(1,1,0)=(0,0,0)$

値を加算して、同じ値を減算すれば0になる、という当たり前の話です。
この当たり前が、ビット単位の演算でも成立しているよ、と。

では3個足して、その答えに2個だけ更に加算（減算）するとどうなるでしょうか？ $(1,0,1)$ を加算（減算）しないと・・・

$(1,0,1)+(0,0,1)+(1,1,0)=(0,1,0) \\ (0,1,0)+(0,0,1)+(1,1,0)=(1,0,1)$

ちゃんと加算（減算）しなかった1個 $(1,0,1)$ が残ってますね。加算と減算の結果が同じということを除くと普通の加算、減算と同じように考えてもよさそうです。

排他論理和でハミング符号を考えてみる

The Continuing Story of Error Correction Code 2 - Smile Engineering Blogのハミング符号は4ビットの送信語がありました。 $D_{4}$ 、 $D_{3}$ 、 $D_{2}$ 、 $D_{1}$ の4ビットです。
この4ビットのうち1ビットだけが1の時の符号語を取り出してみます。

$D_{4}$	$D_{3}$	$D_{2}$	$P_{3}$	$D_{1}$	$P_{2}$	$P_{1}$
0	0	0	0	1	1	1
0	0	1	1	0	0	1
0	1	0	1	0	1	0
1	0	0	1	0	1	1

$D_{1}$ だけが1のときのパリティは $(0,1,1)$ 、 $D_{2}$ だけが1のときのパリティは $(1,0,1)$ 、 $D_{3}$ だけが1のときのパリティは $(1,1,0)$ 、そして $D_{4}$ だけが1のときのパリティは $(1,1,1)$ になっています。

では $D_{1}$ と $D_{2}$ が1のときのパリティは？

$D_{4}$	$D_{3}$	$D_{2}$	$P_{3}$	$D_{1}$	$P_{2}$	$P_{1}$
0	0	1	1	1	1	0

になっているから $(1,1,0)$ ！！
正解！！、なんですが実は $D_{1}$ だけが1のときのパリティと $D_{2}$ だけが1のときのパリティから計算できるのです。
計算方法は $D_{1}$ だけが1のときのパリティと $D_{2}$ だけが1のときのパリティを加算する、だけです。
やってみましょう。
$D_{1}$ だけが1のときのパリティは $(0,1,1)$ 、 $D_{2}$ だけが1のときのパリティは $(1,0,1)$ だから

$(0,1,1)+(1,0,1)=(1,1,0)$

もう一個ぐらいやってみましょうか。
送信語の全ビットが1の場合は $D_{1}$ から $D_{4}$ までそれぞれだけが1のときのパリティを加算します。

$(0,1,1)+(1,0,1)+(1,1,0)+(1,1,1)=(1,1,1)$

表をみると確かに $(0,1,1)$ になっていますね。

$D_{4}$	$D_{3}$	$D_{2}$	$P_{3}$	$D_{1}$	$P_{2}$	$P_{1}$
1	1	1	1	1	1	1

では、符号語に1ビットの誤りがあった場合を考えてみます。
送信語の全ビットが1を送信したら $D_{3}$ が誤って0になったとします。
符号語は $(1,1,1,1,1,1,1)$ ですが、受信語は $(1,0,1,1,1,1,1)$ になりました。
受信語の $D_{4}$ 、 $D_{2}$ 、 $D_{1}$ が1、パリティは $(1,1,1)$ なので

$(1,1,1)+(0,1,1)+(1,1,0)+(1,1,1)=(1,0,1)$

で、答えは $(1,0,1)$ 、これは $D_{3}$ だけが1のパリティに該当します。
ということで誤っているのは $D_{3}$ のビットだとわかります。

なんか分かったような、分からんような・・・

延々と言葉で説明してきましたが、そろそろ数学的な表現を導入してハミング符号を表現できるようにしましょう。
まずは、あれですね。
みんな大好き「行列」。
え゛ーーー、って声が聞こえそうですが、慣れるとこのほうが楽ですよ。
いや、本当に。
ということで次回は行列の基礎。
ハミング符号を行列を使って表してみましょう！！