キーワード辞典
ハミングコード
登録日 ０８/１２/０５ 更新日 ０８/１２/０５
1950年にベル研究所のリチャード・ハミング(Richard Wesley Hamming)によって考案された誤り訂正符号。鼻歌（humming）ではない。 コードに検査用のビットを付加する事でお互いのコードとの差（ハミング距離という）が大きくなり誤りを発見し易くなるとともに、 ある程度までの訂正も可能になる。
たとえば、ある会社で、１６人の社員コードを４ビットで表現される値で表現しているとする。
それぞれのビットを d0、d1、d2、d3 とする。
|
d0 d1 d2 d3 社長 ０ ０ ０ ０ 部長 ０ ０ ０ １ 課長 ０ ０ １ ０ 係長 ０ ０ １ １ |
d0 d1 d2 d3 阿藤 ０ １ ０ ０ 伊藤 ０ １ ０ １ 有働 ０ １ １ ０ 江藤 ０ １ １ １ |
d0 d1 d2 d3 尾藤 １ ０ ０ ０ 加藤 １ ０ ０ １ 木藤 １ ０ １ ０ 工藤 １ ０ １ １ |
d0 d1 d2 d3 華藤 １ １ ０ ０ 小藤 １ １ ０ １ 佐藤 １ １ １ ０ 須藤 １ １ １ １ |
このコード体系では、１ビットでも誤りが発生すると別のコードになってしまい、混乱してしまう。 この様な、違いが１つだけである状態を「ハミング距離が１である」という。
これでは困るので、３ビットの検査用ビット p0、p1、p2 を、
p0 = d0 xor d1 xor d3
p1 = d0 xor d2 xor d3
p2 = d1 xor d2 xor d3
で求めて、付加することにする。
xor は排他的論理和だが、「それぞれの式で１のビットの数が奇数ならば結果は１、でなければ０」と考えても構わない。
この方法によると、各コードは以下の様な７ビットのビット列になる。
|
d0 d1 d2 d3 p0 p1 p2 社長 ０ ０ ０ ０ ０ ０ ０ 部長 ０ ０ ０ １ １ １ １ 課長 ０ ０ １ ０ ０ １ １ 係長 ０ ０ １ １ １ ０ ０ 阿藤 ０ １ ０ ０ １ ０ １ 伊藤 ０ １ ０ １ ０ １ ０ 有働 ０ １ １ ０ １ １ ０ 江藤 ０ １ １ １ ０ ０ １ |
d0 d1 d2 d3 p0 p1 p2 尾藤 １ ０ ０ ０ １ １ ０ 加藤 １ ０ ０ １ ０ ０ １ 木藤 １ ０ １ ０ １ ０ １ 工藤 １ ０ １ １ ０ １ ０ 華藤 １ １ ０ ０ ０ １ １ 小藤 １ １ ０ １ １ ０ ０ 佐藤 １ １ １ ０ ０ ０ ０ 須藤 １ １ １ １ １ １ １ |
このコード体系では、ハミング距離が３になる為、２ビットまでの誤りを見つける事が出来（存在しないコードになるから）、 それを１ビットの誤りであるとみなすならば誤りを訂正する事が出来る。
例
「１００００００」というコードは会社には存在しないので明らかに誤り。
d0の１ビットが誤りとすると社長のコードに、p0とp1の２ビットが誤りとすると尾藤のコードになる。
信頼性として１ビットの誤りとするならば、社長のコードに訂正する事が出来る。
![[ 赤い玉の画像 ]](../Gif/RedBall.gif)
![[ 黒板消しとチョーク受けの画像 ]](../Gif/BlackBoardEnd.gif)