このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

ハミング符号方式

  • nビットの情報に対して、複数のチェックビットを付加して、誤り訂正能力を持たせた方法。

例:8ビットのデータ(D1〜D7)を図のように並べ、縦(行)と横(列)のそれぞれが偶数パリティになるように、ハミングビット(H0〜H3)を決める。そして、データとハミングビットの合計12ビットを符号として使用する。

D0D3D6H2
D1D4D7H3
D2D5
H0H1

 検査するときはあらためてハミングビットを決め直して、先に求めておいたものと比較する。このとき両方のハミングビットが同一であれば、誤りはなかったことになる。ところが一致しないビットがあった場合には、それがどのハミングビット位置かによって、データ中の誤りビットの位置を判明させることができる。さらに、2進数であれば、誤りビット位置さえわかれば、訂正は1/0を反転させてやればよい。

 例えば、ハミングビットのH0とH2の2ビットが不一致の場合は、H0を含む行とH2を含む列に共通している要素、即ちD0が誤っていることになる。
 また、H1だけが不一致の場合は、H1を含む行だけに関する要素D5の誤りであることがわかる。

 これらハミングビットの不一致箇所の組み合わせとデータ中の誤りビット位置は次の通りである。

H3H2H1H0エラービットの位置
エラーなし
×D7
×D6
××エラーあり(訂正不能)
×D5
××D4
××D3
×××エラーあり(訂正不能)
×D2
××D1
××D0
×××エラーあり(訂正不能)
××エラーあり(訂正不能)
×××エラーあり(訂正不能)
×××エラーあり(訂正不能)
××××エラーあり(訂正不能)

 「・」は一致、「×」は不一致を表す。

 ただし、2ビット以上の誤りが生じた場合には検出はできるが、訂正はできない。 ◇

参考文献

  • 『見てわかるノイズの試験法と対策』