ハミング符号の原理（１）

　コンピュータの主記憶装置として、ＤＲＡＭなどの半導体メモリが使用されており、記憶されたデータのエラーを訂正する誤り訂正符号として、ハミング符号（ハミングコード）が用いられています。
　このハミング符号の原理を難しい数式を使わず、小中学生でも理解できるように簡単に説明します。

【表１：検査ビット生成表（パリティ生成テーブル）】

　　　　(1**) (*1*) (**1)
a　011　　　　 a　　　a
b　101　b　　　　　　 b
c　110　c　　　c
d　111　d　　　d　　　d
--------------------------
　　　　p1　　　p2　　　p3

上記の表は、半導体メモリなどの記憶装置に情報ビット(a,b,c,d)からなるデータを書き込むときに、
情報ビット a をアドレス011番地に書き込み、情報ビット b をアドレス101番地に書き込み、
情報ビット c をアドレス110番地に書き込み、情報ビット d をアドレス111番地に書き込む際の、ハミング符号（ハミングコード）の作成方法を示します。

(1**) は、最上位ビット（一番左の桁）が 1 であるアドレスを意味します。
(*1*)は、中間のビット（真ん中の桁）が 1 であるアドレスです。
(**1)は、最下位ビット（一番右の桁）が 1 であるアドレスです。
なお、* は任意の数字です。２進数なので 0、1 の両方を示します。

(1**) に該当するアドレス 101、110、110番地に記憶される情報ビットは b,c,d なので、この b,c,d に基づいて検査ビット（チェックビット） p1 を作ります。

(*1*) に該当するアドレス 011、110、111番地に記憶される情報ビット a,c,d に基づいて検査ビット p2 をつくります。

(**1) に該当するアドレス 011、101、111番地に記憶される情報ビット a,b,d に基づいて検査ビット p3 をつくります。

◆具体的なデータの符号化方法（書き込み時の動作）

例えば、情報ビット(a,b,c,d)=(1101)からなるデータを記憶するときは、次のように検査ビットをつけることとします。

まず(1**) の列に注目し、情報ビット b,c,d に含まれる 1 の数を数えます。
b,c,d を足して奇数なら p1 を 1 とし、偶数なら p1 を 0 とします。
言い換えると、b,c,d,p1 中の 1 の数の合計が偶数となるようにします。これを偶数パリティと言います。

(a,b,c,d)=(1101)では、b,c,d のうちで 1 は b,d の 2 個なので、p1 は 0 です。

(*1*)の列では、データ a,c,d のうちで、1 は a,d の 2 個なので、p2 は 0 です。
(**1)の列では、データ a,b,d の 3 つが 1 なので、p3 を 1 とします。

以上の説明を、数式で書くと、次のようになります。

a=1 b=1 c=0 d=1

p1 = b+c+d = 1+0+1 = 0
p2 = a+c+d = 1+0+1 = 0
p3 = a+b+d = 1+1+1 = 1

p1,p2,p3 は、1 の数が奇数か偶数かを検査しているので、奇偶検査ビット（パリティビット）と言います。

この計算で求めた検査ビット p1,p2,p3 をそれぞれメモリのアドレス 100、010、001番地に記憶します。

p1 100
p2 010
p3 001

情報ビット(a,b,c,d)=(1101)には、検査ビットがつけられ、
記憶されるデータは(a,b,c,d, p1,p2,p3)=(1101 001) となって、メモリに格納されます。

このようにして格納したデータの誤り訂正（エラー訂正）の方法は、以下のとおりです。

◆復号化方法（読み出し時の動作）
何らかのノイズの影響で、1ビットだけデータが反転し、誤って読み出されたとします。

例えば、(a,b,c,d, p1,p2,p3)=(1001 001) が読み出されたとします。
この読み出しデータ中の情報ビット(a,b,c,d)=(1001)に基づいて、先ほどと同様にして、検査ビット p1,p2,p3 を計算します（再計算します。）。

　a=1 b=0 c=0 d=1

p1 = b+c+d = 0+0+1 = 1
p2 = a+c+d = 1+0+1 = 0
p3 = a+b+d = 1+0+1 = 0

この再計算された検査ビット(p1,p2,p3)=(100) は、読み出された検査ビット(p1,p2,p3)=(001) と異なるため、どこかのビットが誤っていることになります。

読み出した検査ビット(p1,p2,p3)=(001)
再計算した検査ビット(p1,p2,p3)=(100)

ここで、上記２つの検査ビットを各桁ごとに比較して、異なったら 1 、同じだったら 0 とします。
比較すると、真ん中のビットは同じなので 0 、最上位ビットと最下位ビットは異なるので 1 とします。
よって

　(p1,p2,p3)=(001)
+ (p1,p2,p3)=(100)
-------------------
　 (s1,s2,s3)=(101)

となり、アドレス 101番地から読み出した情報ビット b が間違っていることがわかります。

よって、
(a,b,c,d, p1,p2,p3)=(1001 001)のうち、情報ビット b を反転させて、
(a,b,c,d, p1,p2,p3)=(1101 001)とデータを訂正することができます。

ここでは、データ中の情報ビットのエラー訂正を例に説明しましたが、検査ビットのエラーも同様の方法で訂正することができます。
検査ビット自体のエラー訂正が可能な点が、ハミング符号の特徴の一つです。

以上が簡単なハミング符号の原理です。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
★おまけ：

情報ビットは、通信分野においては、通報ビットとも言います。
検査ビットは、チェックビット、パリティビット、奇偶検査ビット、冗長ビットなどとも言われます。

上記の記号 + は、排他的論理和（エクスクルッシブＯＲ）です。記号は　EXOR、EOR、XOR などとも書かれます。

(s1,s2,s3)=(101)は、読出しデータの誤っているアドレスを示しており、シンドロームと言います。

【表２：シンドローム生成テーブル（誤り位置の生成表）】

　　　　 　(1**) (*1*) (**1)
a 　011　　　　　 a　　　a
b 　101　　b　　　　　　 b
c 　110　　c　　　c
d 　111　　d　　　d　　　d
p1　100　　p1
p2　010　　　　　p2
p3　001　　　　　　　　　p3
--------------------------
　　　　　 s1　　　s2　 　s3　（←書込み時は、0 0 0 になっている。）

最計算された検査ビットと、読み出された検査ビットとの比較によってシンドロームを求める方法を説明しましたが、
シンドロームの計算は、この表２の(a,b,c,d, p1,p2,p3)に読出しデータ(1001 001)を代入し、(s1,s2,s3)を直接求めることができます。

　a=1 b=0 c=0 d=1 p1=0 p2=0 p3=1

s1 = b+c+d+p1 = 0+0+1+0 = 1
s2 = a+c+d+p2 = 1+0+1+0 = 0
s3 = a+b+d+p3 = 1+0+1+1 = 1

シンドローム(s1,s2,s3)=(0,0,0)なら誤りなし（エラーなし）です。
それ以外の場合は、シンドロームは、エラーが生じたデータビット（情報ビット又は検査ビット）のアドレスを示します。

試しに、(a,b,c,d, p1,p2,p3)=(0000 000) を記憶させ、このデータの1ビット誤りのデータを上記のシンドローム生成テーブル（表２）に入力してみれば、シンドロームがエラーとなったデータ（情報ビット、検査ビット）の位置（アドレス）を示すことは一目瞭然です。

以上をまとめると、
ハミング符号の原理（２）

ハミング符号の原理（３）
ハミング符号の原理（４）　－拡大ハミング符号－
ハミング符号の原理（５）　－グレイ・ハミング符号－
ハミング符号の原理（６）　－巡回ハミング符号－