キーワード辞典
ハミングコード

登録日 08/12/05   更新日 08/12/05


1950年にベル研究所のリチャード・ハミング(Richard Wesley Hamming)によって考案された誤り訂正符号。鼻歌(humming)ではない。 コードに検査用のビットを付加する事でお互いのコードとの差(ハミング距離という)が大きくなり誤りを発見し易くなるとともに、 ある程度までの訂正も可能になる。

たとえば、ある会社で、16人の社員コードを4ビットで表現される値で表現しているとする。
それぞれのビットを d0、d1、d2、d3 とする。

    d0 d1 d2 d3
社長 0 0 0 0
部長 0 0 0 1
課長 0 0 1 0
係長 0 0 1 1
    d0 d1 d2 d3
阿藤 0 1 0 0
伊藤 0 1 0 1
有働 0 1 1 0
江藤 0 1 1 1
    d0 d1 d2 d3
尾藤 1 0 0 0
加藤 1 0 0 1
木藤 1 0 1 0
工藤 1 0 1 1
    d0 d1 d2 d3
華藤 1 1 0 0
小藤 1 1 0 1
佐藤 1 1 1 0
須藤 1 1 1 1

このコード体系では、1ビットでも誤りが発生すると別のコードになってしまい、混乱してしまう。 この様な、違いが1つだけである状態を「ハミング距離が1である」という。


これでは困るので、3ビットの検査用ビット p0、p1、p2 を、
p0 = d0 xor d1 xor d3
p1 = d0 xor d2 xor d3
p2 = d1 xor d2 xor d3
で求めて、付加することにする。 xor は排他的論理和だが、「それぞれの式で1のビットの数が奇数ならば結果は1、でなければ0」と考えても構わない。 この方法によると、各コードは以下の様な7ビットのビット列になる。

    d0 d1 d2 d3  p0 p1 p2
社長 0 0 0 0  0 0 0
部長 0 0 0 1  1 1 1
課長 0 0 1 0  0 1 1
係長 0 0 1 1  1 0 0
阿藤 0 1 0 0  1 0 1
伊藤 0 1 0 1  0 1 0
有働 0 1 1 0  1 1 0
江藤 0 1 1 1  0 0 1
    d0 d1 d2 d3  p0 p1 p2
尾藤 1 0 0 0  1 1 0
加藤 1 0 0 1  0 0 1
木藤 1 0 1 0  1 0 1
工藤 1 0 1 1  0 1 0
華藤 1 1 0 0  0 1 1
小藤 1 1 0 1  1 0 0
佐藤 1 1 1 0  0 0 0
須藤 1 1 1 1  1 1 1

このコード体系では、ハミング距離が3になる為、2ビットまでの誤りを見つける事が出来(存在しないコードになるから)、 それを1ビットの誤りであるとみなすならば誤りを訂正する事が出来る。


「1000000」というコードは会社には存在しないので明らかに誤り。
d0の1ビットが誤りとすると社長のコードに、p0とp1の2ビットが誤りとすると尾藤のコードになる。
信頼性として1ビットの誤りとするならば、社長のコードに訂正する事が出来る。





[ 赤い玉の画像 ] 「キーワード辞典」の目次へ

[ 黒板消しとチョーク受けの画像 ]