情報訂正符号の一つ。ハミング符号ともいう。

目次 概要 ハミングコード 算出 訂正

概要

情報を記録する際に、実際のデータに加えてエラーチェック用のコードを付加しておき、読み出したときにそれを検証して、正しいかどうかを判断する技術のこと。

ECC付きメモリーやRAID2などで使われる。なお、RAID3・RAID4・RAID5では、ハミングコードの代わりにより簡略なパリティビットとバイトを使用して誤り訂正をしている。

ハミングコード

算出

例えば4ビットのデータ列があった場合、これに3ビットのハミングコードを与える。

データ列がd0 d1 d2 d3とすると、次のように3ビットのハミングコードを求める。

• p0 = d0 XOR d1 XOR d3
• p1 = d0 XOR d2 XOR d3
• p2 = d1 XOR d2 XOR d3

訂正

もし読み出してエラーが発生していた場合は、次のようなXOR演算をしてe0〜e2を算出する。

• e0 = p0 XOR d0 XOR d1 XOR d3
• e1 = p1 XOR d0 XOR d2 XOR d3
• e2 = p2 XOR d1 XOR d2 XOR d3

正常時は、e0 e1 e2は全て0であるので、どのビットが1になるかで、エラービットの位置が求められる。

e2=0				e2=1
e1=0		e1=1		e1=0		e1=1
e0=0	e0=1	e0=0	e0=1	e0=0	e0=1	e0=0	e0=1
正常	p0 NG	p1 NG	d0 NG	p2 NG	d1 NG	d2 NG	d3 NG

これにより、エラービットが一つまでであれば、その誤りを訂正することが可能となる。

リンク

関連する用語
RAID
排他的論理和
ハミング距離
グレイコード

[再検索] [戻る]