ハミングコードを用いたエラー訂正

このHマトリクスを使ってデータに対してチェックビットを作るには、チェックビットに1がある行を横に見て、1のある項のデータをXORする。例えばC0は第1列の3行目に1があるので、3行目を横に見る。そうすると、D0、D1、D3の列に1があるので、C0=D0・D1・D2と計算する。そして、C1、C2も同様にC1=D0・D2・D3、C2=D1・D2・D3と計算する。そして、このように計算したC0～C2を、データD0～D3に付加して送信する。

受信側では、まず、受信したデータから、各行の1のある項をすべてXORして、

S0=C0・ D0・D1・D2
S1=C1・ D0・D2・D3
S2=C2・ D1・D2・D3

を計算する。これらのSビットはシンドローム(Syndrome)と呼ばれる。こられの式は、前述のチェックビットを計算する式の右辺と左辺をXORしているので、エラーが無ければS0～S2はすべて0になる。

ここで、例えば5ビット目のD1にエラーが発生しデータ値が反転したとすると、D1を含むS0とS2は値が反転して1になり、D1を含まないS1は影響を受けず0のままとなる。つまり、S2、S1、S0は101となり、2進数の5となって5ビット目のD1にエラーが生じたことを示している。ここでは5ビット目のエラーを例として取り上げたが、Hマトリクスの各列が2進数の順になっているので、どのビットでエラーが起こっても、S2～S0はエラーが発生したビット番号を示す。

したがって、図2.15に示すように、シンドロームを計算し、S2～S0をデコードし、エラーしたビット番号のデータ値を反転してやれば、エラーを訂正することができる。

このハミングコードのチェックビットの計算を見ると、D0はC0とC1の式に含まれている。したがって、D1～D3が同じでD0だけが異なる2つのコードワードを考えると、C0とC1の値が異なることになる。そうすると、D0とC0とC1が異なるので、両者の距離は3となる。同様にD1とD3も2つのチェックビットの計算に含まれており、これらのデータビットだけが異なるコードワードの距離は3となる。一方、D2は3つのチェックビットの計算の含まれており、D2だけが異なるコードワード間の距離は4となる。

この説明では不十分であるが、確認すれば、複数のデータビットが異なるコードワード間の距離も3以上となっていることが分かる。

なお、ここでは説明を簡単にするため、全長が7ビットでデータビットが4ビットの(7、4)ハミングコードを例に使ったが、Hマトリクスの作り方を拡張すれば、チェックビット数がkビットの ハミングコードが作れる。また、この上限よりも短いコードワードを作ることも可能で、64ビットのデータのエラー訂正を行う場合は、もとの(127、120)ハミングコードから不要な56ビットのデータを常に0とみなして削除した(71、64)ハミングコードを使えばよい。