ハミング符号ってなんだっけ？ハミング符号でデータの誤り訂正・検出を行う

はじめに

電波などでデジタルでデータの通信を行う場合、波に0と1の２つの状態を持たせデータのやり取りを行います

この時受信したデータが0か1かを区別するために、ある閾値を設定して0か1か判定します

具体例を挙げると、ASKのように振幅の大小を用いてデータのやり取りを行う場合、閾値を0.5と設定すれば、振幅が0.5より大きければ1、小さければ0としてデータを処理します

ここで、通信環境が悪いと様々なノイズが混入し、本来1として送信されたデータは閾値を下回り、0として判定されるように誤ったデータを受信することが頻繁に発生します

コンピュータでは一つのビットでも違うとデータを正常に復元することができず、時にはクラッシュを引き起こします

この厄介な問題を解決する手段の一つとして、誤り訂正符号の一つであるハミング符号を紹介します

ハミング符号とは

ハミング符号とは、1950年代にベル研究所のリチャード・ハミングによって考案されたデータの誤りを検出・訂正できる訂正符号の一つです

伝達したいデータに対して、特定の位置のデータが偶数(or 奇数)になるようにパリティと呼ばれるビットを付与することで、誤り訂正を行います

ハミング符号を作成してみる

ここでは、 0101 という4ビットのデータを伝達したい場合にハミング符号にすることを考えてみます

伝達したいデータのビットを左から順にd1, d2, d3, d4として、まずはd1, d2, d4における1の数が奇数なら1, 偶数なら0とするようなパリティp1を計算します

$p1 = d1 \oplus d2 \oplus d4 = 0 \oplus 1 \oplus 1 = 0$

( $\oplus$ は排他的論理和を表す)

これによって、パリティを含むデータp1d1d2d4 は 0011 となり1の数は偶数になります

同様に、d1, d3, d4のパリティp2とd2, d3, d4のパリティp3を計算するとそれぞれp2 = 1, p3 = 0となります

以上より、パリティとデータを p1p2d1p3d2d3d4 になるように並べると 0100101 の7ビットのパリティが付与されたデータとなり、これをハミング符号(Hamming Code)といいます

　表1 パリティを付与したハミング符号

p1	p2	d1	p3	d2	d3	d4
0	1	0	0	1	0	1

ハミング符号によるデータ訂正

先程計算された 0100101 というデータがノイズによって受信側では 1100101 となったことを考えてみましょう

　表2 p1に誤りが生じたデータ

p1	p2	d1	p3	d2	d3	d4
1	1	0	0	1	0	1

ここでは、パリティを含むデータ p1d1d2d4 , p2d2d3d4 , p3d2d3d4の排他的論理和の計算を行い、1の数が偶数になるかどうかでデータに誤りが生じたかどうかを確認します

それぞれの結果をs1, s2, s3として、計算を行うと以下のようになりました

$\begin{align} s1 &= p1 \oplus d1 \oplus d2 \oplus d4 &= 1 \oplus 0 \oplus 1 \oplus 1 &= 1 \\\ s2 &= p2 \oplus d1 \oplus d3 \oplus d4 &= 1 \oplus 0 \oplus 0 \oplus 1 &= 0 \\\ s3 &= p3\oplus d2 \oplus d3 \oplus d4 &= 0 \oplus 1 \oplus 0 \oplus 1 &= 0 \end{align}$

データに誤りが発生していない場合、s1, s2, s3は偶数になるようにパリティを設定したので0になります

しかし、s1が1となっているので、データに誤りが発生していることがわかります

s1に含まれて、s2, s3には含まれないビットが誤りが生じていることになり、この条件を満たすビットはp1となり、送信されたデータはp1を訂正し正常なデータを復元することができます

ここで、s1, s2, s3の組み合わせのことを シンドローム と呼び、このシンドロームの値によってどのビットに誤りが生じているか判定することができます

　表3 シンドロームと訂正すべきビット

s3	s2	s1	誤りが生じているビット
0	0	0	なし
0	0	1	p1
0	1	0	p2
0	1	1	d1
1	0	0	p3
1	0	1	d2
1	1	0	d3
1	1	1	d4

情報ビット数と検査ビット数の関係

上記の例では4ビットのデータに対して3ビットの検査ビットをつけることによって、誤りの訂正を行いました

ここでは、パリティとしての検査ビットを何ビット追加すればよいか考えてみます

情報ビット数をk、検査用のパリティビット数をm、全体のデータビット数をnとすると、n = k + mとなります

nビットのどれか1ビット以下の誤りがある場合、その組み合わせの数は、

全く誤りのない場合
1ビット目に誤りがある場合
2ビット目に誤りがある場合

・

nビット目に誤りがある場合

となり、n+1通りあります

mビットの検査ビットの組み合わせによって表現できる情報量は $2^m$ となるので、先程の全データの誤りと検査ビットには以下の関係式が成り立ちます

$(検査ビットの情報数) \geq (誤りが発生する場合の数) \\\$

つまり、

$2^m \geq n + 1$

となり、n = m + kの関係を代入すると

$2^m - m \geq k + 1$

を満たす必要があります

式の等号が成立する時のnとkの組み合わせは下記の通りです

　表4 検査ビット数と全体ビット数・訂正可能な情報ビット数

符号全体のビット数(n)	情報ビット数(k)	検査ビット数(m)
3	1	2
7	4	3
15	11	4
31	26	5
63	57	6

表を見て分かるようにデータサイズが4ビットの場合、検査ビットは少なくとも3ビット必要になります

ここで、全体データのビットサイズがnで情報ビットがkビットである符号のことを、一般に(n, k)符号と呼ばれ,H(n, k)とも表されます

データ転送効率

全データビットの内、情報ビットの容量の割合が伝達効率となります

各データの伝達効率を計算するとH(3,1)の時1 / 3 ≒ 33%, H(7, 4)の時, 4/7 ≒ 57%, H(15, 11)の時 11/ 15 ≒ 73%, H(31, 26)の時 26 / 31 = 84%, H(63, 57)の時 57/63 = 92%と情報ビット数を長くするとデータ転送効率がよくなります

誤り検出の機能を追加する

今まで述べてきたハミング符号は1ビット以下の誤りを訂正することのみに焦点を当てていました

ゆえに、2つ以上のデータの誤りある場合、受信データを誤って訂正してしまいます

この問題に対しては、全データビットのパリティビットを含めることによって、2つのデータの誤りの検知をすることができるようになります

先程のハミング符号に、全体のパリティビットを追加したものは拡張ハミング符号(extended Hamming Code)といいます

この拡張ハミング符号は、一つのエラーを訂正し、2つのエラーを検知する機能を保有しているので、SECDED(Single Error Correction, Double Error Detection)とも呼ばれています

では、実際に試してみましょう

拡張ハミング符号

0100101 というデータが2つの誤りをもつ 1000101 というデータが受信された場合を考えてみましょう

　表5 2つのデータ誤りが生じたデータ

p1	p2	d1	p3	d2	d3	d4
1	0	0	0	1	0	1

今までどおり計算を行うと

$\begin{align} s1 &= p1 \oplus d1 \oplus d2 \oplus d4 &= 1 \oplus 0 \oplus 1 \oplus 1 &= 1 \\\ s2 &= p2 \oplus d1 \oplus d3 \oplus d4 &= 0\oplus 0 \oplus 0 \oplus 1 &= 1 \\\ s3 &= p3\oplus d2 \oplus d3 \oplus d4 &= 0 \oplus 1 \oplus 0 \oplus 1 &= 0 \end{align}$

となり、d1が訂正され 1010101 と誤った訂正がされることになります。

そこで、全体のパリティビットs0を計算して追加します

$p0 = p1 \oplus p2 \oplus d1 \oplus d2 \oplus p3 \oplus d3 \oplus d4 = 0 \oplus 1 \oplus 0 \oplus 0 \oplus 1 \oplus 0 \oplus 1 = 1$

表6 全体データのパリティを追加した拡張ハミング符号

p0	p1	p2	d1	p3	d2	d3	d4
1	0	1	0	0	1	0	1

ここで、先程同じようにp1とp2にデータの誤りが生じた場合を考えましょう

表7 拡張ハミング符号において2つのデータ誤りが生じた場合

p0	p1	p2	d1	p3	d2	d3	d4
1	1	0	0	0	1	0	1

同様に、各パリティについて計算を行ってみます

$\begin{align} s0 &= p0 \oplus p1 \oplus p2 \oplus d1 \oplus d2 \oplus p3 \oplus d3 \oplus d4 \\\ &= 1 \oplus 0 \oplus 1 \oplus 0 \oplus 0 \oplus 1 \oplus 0 \oplus 1 &= 0 \\\ s1 &= p1 \oplus d1 \oplus d2 \oplus d4 &= 1 \\\ s2 &= p2 \oplus d1 \oplus d3 \oplus d4 &= 1 \\\ s3 &= p3\oplus d2 \oplus d3 \oplus d4 &= 0 \end{align}$