1ビット訂正ハミングコード

まず、図3.12のように、4行15列の表を作り、縦方向に2進数で0001、0010、0011、…、1111と順に書き込んで行く。そして上に行を追加して、各列の意味を書き込む。ここで、"1"が1つしかない列はC、2つ以上の"1"がある列はDとして、順番に番号を付けていく。C列はチェックビット、D列はデータビットに対応する。

図3.12 データ11ビット、チェックビット4ビットのハミングコードの生成行列

そして、保護すべきデータビットに対して、チェックビットの値を求める。C0ビットの値を求める式は、C0が"1"の行を横に見て、"1"があるデータビットのXORを取る。C1～C3ビットの値を求める式も同様で、論理式で書くと次のようになる。

C0=D0・D1・D3・D4・D6・D8・D10
C1=D0・D2・D3・D5・D6・D9・D10
C2=D1・D2・D3・D7・D8・D9・D10
C3=D4・D5・D6・D7・D8・D9・D10

元のデータのD0～D10が決まると、上記の式でC0～C3を計算して、図3.11のビット順になりようにD0～D10に付け加える。

そして、データを受信した側では、次の式を計算する。この式は、前の式の右辺と左辺を・でつないだものである。

S0=C0・D0・D1・D3・D4・D6・D8・D10
S1=C1・D0・D2・D3・D5・D6・D9・D10
S2=C2・D1・D2・D3・D7・D8・D9・D10
S3=C3・D4・D5・D6・D7・D8・D9・D10

このように計算されるSをSyndrome(症状)という。元々、C0はD0・D1・D3・D4・D6・D8・D10と同じになるように作られているので、エラーが無ければ、S0はゼロになる。S1～S3も同様である。しかし、どこかのビットにエラーが発生すると、そのビットを含むSの式の値が変わってくる。例えば、D6ビットがエラーで値が反転したとすると、D6を含むS0とS1とS3が"1"になり、D6を含まないS2は"0"のままであるので、S3、S2、S1、S0は1011となる。これは10進数では11であり、11列目のビットがエラーで反転したという症状を示している。つまりD6のエラーである。従って、受け取ったデータのD6ビットを反転すれば、正しい、元のデータが得られる。

やってみれば分かるが、Cビットも含めて、どのビットが反転しても、S3～S0の値はエラーが起こった列の番号を示す1ビットエラー訂正コードになっている。

この方法で、よりチェックビット数の長いコードを作ることができる。例えば7ビットのチェックビットのコードでは全長が127ビットで120ビットがデータとして使える。しかし、通常はデータビットは2のべきであるので、64ビットをデータとして使用し、残りの56ビットは常にゼロとして省略する。こうすると、コードの全長は71ビットで、データビットは64ビットというコードが得られる。

このコードで、例えばD0とD1の2ビットが反転すると、両方を含んでいるS0は"0"になり、S1とS2は"1"、どちらも含まないS3は"0"となる。そして、S3～S0は0110となり6行目のD2が誤ったという症状と同じになってしまい、D2を反転するという誤訂正を行ってしまう。訂正ができないのはやむを得ないとしても、訂正できないエラーが起こったということが分かる方が望ましい。

このためにはもう1ビット、Cpというチェックビットを追加し、Cp=C0・…Cm・D0・D1・…Dnと全ビットのXORでCpを計算する。そして、Sc=Cp・ C0・…Cm・D0・D1・…Dnとすると、どのビットにもエラーが無い場合は、S0～Sm、Spは全てゼロになり、1ビットエラーの場合はSpが"1"になり、S0～Smでエラーした行番号が分かる。2ビットエラーの場合はSpがゼロで、その他のS0~Smの中に非ゼロのものがあるという症状になるので、2ビットエラーが発生したことが分かる。このように全体のパリティービットを追加することで2ビットエラーの発生を検出することができるコードが得られる。

このようなコードは「Single bit Error Correct Double bit Error Detect(SECDED)コード」と呼ばれ、サーバで一般的に使われている。また、NVIDIAのKepler GPUもSECDEDコードを使っている。

コードのデータビットが64ビットの場合、チェックビット数は8ビット必要であり、×8のDRAMチップを使う場合、9チップ搭載のDIMMを使えば、必要なビット数が得られるという点でも実現しやすいということも広く使われている理由である。ただし、前に述べたように、32ビット幅のGDDR5 DRAMでの実現には工夫が必要である。

なお、1ビットエラーを訂正できるコードは数多く存在し、2ビット以上のエラーを訂正できるコードも抽象代数を使った作り方が確立されているが、専門的になるので、ここでは割愛する。