ハミング距離

ハミング距離とエラー検出

以下では、図2.6に示したデータの値を変えずに伝送する、あるいは記憶するケースについて考える。

少し形式張るが、nビットの2進数をn次元2進空間の点と考える。これを3ビットの2進数について書くと図2.8のようになる。

この立方体のそれぞれの辺の長さを距離1とすると、2進数000と100の距離は1であり、000と101の距離は2、000と111の距離は3ということになる。回り道をしない2点の間の最短経路の距離を「ハミング距離(Hamming Distance)」という。4次元以上の立方体を図示することは難しいが、要するにハミング距離は2つの2進数の対応するビットの値が異なっているところの数ということになる。

そして、1ビットのエラーが起こるということは、n次元2進空間の中で2進数の位置が距離=1だけ動くということに相当する。

入力データのビットと図2.4のようなプレディクタで生成されたビット(これをチェックビットと呼ぶ)をひとまとめにして、これを「コードワード」と呼ぶことにする。入力データだけを見ると、これは任意の2進数であるので、2つの入力データが1ビットだけしか異なっていないという場合は存在する。しかし、この場合は異なるチェックビットを付けてやれば、コードワード全体では2ビット以上が異なりコードワード間のハミング距離を大きくすることができる。

図2.9に示すように、コードワード1にエラーが発生するとn次元2進空間での位置が動く。どの方向に動くかは、どのビットにエラーが発生したかによるが、1ビットのエラーの場合は、元のコードワード1の位置を中心として半径1の球の中の点になる。コードワード1とコードワード2の距離が2以上であれば、コードワード2はコードワード1の位置を中心とする半径1の球には含まれない。コードワード1にエラーが発生してそれがコードワード2に化けてしまうと、コードワード2が誤りなく送られた場合と区別がつかなくなるが、1ビットエラーの場合には、距離が2以上であればこのようなことは起こらず、エラーが発生したことを検出できる。

そして、どの2つのコードワードをとっても、その距離が2以上となるようにチェックビットを決めることができれば、どのような1ビットエラーが起こっても、エラーの発生を検出できることになる。