【東大「情報」講義用資料】ハミング距離の意義を直観的に理解する

ハミング距離を十分にとることによって，ある程度の誤り訂正ができるということを説明する．まずは次の図を見てほしい．

この図において，伝送したいメッセージはAとBの二種類である．AとBはそれぞれ，「1001011000101」および「1011011010010」というコードで符号化されている．

確認1：AとBのハミング距離は5であることを確かめよ

さて，残念ながら伝送路は雑音が多く，一定の確率でときどき誤りが生じ，ビットが反転してしまうという現象が生じるものとする．たとえば，Aを伝送したときに先頭から9ビットめが反転してしまったものがA’であり，さらに7ビットめも，すなわち7ビットめと9ビットめが反転してしまったものがA’’であるとする．

確認2：AとA’，およびAとA’’のハミング距離がそれぞれ1と2であることを確かめよ

同様に，Bから派生した誤りを含む符号がB’とB’’である．

ところで，上記において，とりあえずAとBしか今は考えていないので，A’やB’が観測されたときに，AまたはBから誤りが生じたものであることは明らかである．図では，AとBからのハミング距離を半径として，同心円が描かれているが，A’やA’’，あるいはB’やB’’といった誤りを含む符号はこの同心円状に配置される．

このとき，3個以上のビット誤りが生じてAとB双方へのハミング距離が3以上になってしまったらどうなるだろうか？その符号の元の符号はAなのかBなのか．

これは判定できない．

確認3：AとBへのハミング距離が3以上であるような符号を考え，その符号の元となった符号はAなのかBなのか，判定できないことを確かめよ

以上の理屈により，t個までの誤りが生じたときに，2t+1個のハミング距離を確保しておけば誤りを修正できる（元の符号を推定できる）ということになるのである．