小学5年生が理解する「誤り訂正符号」（デジタル社会を支えるテクノロジー：誤り訂正符号って何？その9）
いよいよ本格的な『誤り訂正符号』の『ハミング符号』の話しになった前回、今日は少し詳しい紹介。
息子：「うぇ～い！！帰ってきたぞ～い。」
私：「おっ！帰ってきたな。暇人が～！テン・テン・テン・テレレン・・・（ジョン・レノンの「イマジン」の前奏のつもり）」
息子：「暇人じゃなーいっ！！パパの仕事の話しを聞いてやるために早く帰ってきたのにさー。」
私：「まー今は帰ってくるしかないからな・・・。それは良いとして、夕ご飯になる前に、終わるように早速昨日の話しの続きをしようか。『ハミング符号』が何で1ビットの誤り訂正ができるのかの説明がまだだったね。」
息子：「そうそう。」
私：「まず、昨日、タクムが書いた全ての『ハミング符号』を見てみよう。ここで便利な用語を教えておくと、元々のデータ4ビットを『情報記号（じょうほうきごう）』、元々のデータ4ビットから計算して付け足した3ビットを『検査記号（けんさきごう）』元々のデータ4ビットから作った7ビットの並びを『符号語（ふごうご）』って言うんだ。それでは『ハミング符号』の『符号語』を並べてみよう。」
息子：「
0000000
0001011
0010110
0011101
0100111
0101100
0110001
0111010
1000101
1001110
1010011
1011000
1100010
1101001
1110100
1111111
で、1のビットの個数が0と7のが1つずつで、他は1のビットの個数が3個か4個しかなくて、1個、2個、5個、6個のが無い、ことに気が付いた。それが『ハミング符号』が1ビットの誤り訂正できる理由ってとこまで聞いた。」
私：「各『符号語』の数1のビットの個数、正確には数0でないビットの数を『ハミング重み』って言うんだ。だから、『ハミング符号』の『符号語』は『ハミング重み』が0、3、4、および7を持つ。0以外の最小の『ハミング重み』が3だから、『ハミング符号』の『最小ハミング重み』は3になる。ここで、『ハミング符号』の全ての『符号語』をよく見てみよう。そして、同じ位置のビットの数が０と1とで入れ替わっている『符号語』の組が無いかな？」
息子：「えっ・・・
まずは
0000000と1111111
0001011と1110100
0010110と1101001
0011101と1100010
0100111と1011000
0101100と1010011
0110001と1001110
0111010と1000101
っ！！あれっ！！全部、組になってる！！」
私：「そう！全部、2つの『符号語』で1組になってるんだ。これは『ハミング符号』が『線形符号（せんけいふごう）』という『誤り訂正符号』だからなんだ。『線形符号』の性質として、同じ位置のビット同士で足した『符号語』、つまり『符号語』に『符号語』を足してできたビットの並びはまた『符号語』になる、という性質があるんだ。ただし、ここで言っているビット同士を足す、というのは足した結果を2で割った余りを言っているので注意してね。タクムが組にしてくれた同じ位置のビットの数が０と1とで入れ替わっている『符号語』同士は、互いにその『符号語』自身に全てのビットが1の『符号語』、つまり1111111を足した『符号語』でもある。だから、『ハミング符号』の『符号語』の各ビットの0と1が入れ替わった7ビットが、また『符号語』になるんだ。」
息子：「うん。そうも見えるね。」
私：「ここで、ひとつ気づかないかな？」
息子：「何を？」
私：「『符号語』と『符号語』の同じ位置のビット同士を足したものがまた『符号語』になるということは、『ハミング符号』の2つの別の『符号語』の同じ位置のビットが違う数も『ハミング重み』と同じになる、ということだ。」
息子：「うん。そうだね。だけど、同じこと言ってるだけじゃないの？」
私：「それは『ハミング符号』が『線形符号』という『誤り訂正符号』だからそう言えるんだ。2つの別の『符号語』の同じ位置のビットが違う数のことを『ハミング距離』と言うんだけど、最小の『ハミング距離』はいくつかな？」
息子：「最小の『ハミング距離』は3だね。」
私：「その通り、最小の『ハミング距離』を『最小ハミング距離』と言う。『最小ハミング距離』というと違和感があるかもしれないけど、1+1=0という計算の世界では1-1=0でもあるから、足すことは引くことでもある。つまり、2つの別の『符号語』同士の同じ位置のビットを足すことは、2つの別の『符号語』同士の同じ位置のビットを引くことでもある、つまり『符号語』同士の距離、つまり『ハミング距離』を計算していることと同じなんだ。」
息子：「『ハミング距離』を知って何の意味があるの？」
私：「2つの別の『符号語』同士の距離って考えると、それぞれの『符号語』の縄張りの範囲であれば誤りを見つけられて、かつ誤りを訂正できる範囲って考えるとわかるかな？」
息子：「んっ！？・・・」
私：「そうだな、方眼紙の縦線と横線の交わった場所、つまりグリッドに、それぞれの『符号語』を１つの点として書いて、お互いに3以上グリッドが離れた場所に点を打ってみよう。そうすると、全ての点と点の間は必ず3以上グリッド離れてるから『符号語』の点を中心に半径1グリッドの円が描ける。こうすると、全ての『符号語』の点を中心にした円は全て離れていて重ならない。このことは、この円の範囲内までの『ハミング距離』の誤りまで訂正できる、つまり『最小ハミング距離』が3なら『ハミング距離』が1までの誤りビット数なら誤り訂正できる、ってことなんだ。」
息子：「距離って言い方を図にするとわかるね。ってことは、『最小ハミング距離』が5なら2個のビット、7なら3個のビットまでなら誤り訂正できるってこと？でも『最小ハミング距離』が2とか4とか偶数の場合は円がくっついちゃうね。」
私：「そういうことになる。『最小ハミング距離』が3以上の奇数の場合はうまい具合に、『最小ハミング距離』の半分より小さい最大の自然数個の誤り訂正ができる。『最小ハミング距離』が2以上の偶数の場合は『最小ハミング距離』の半分も自然数なんだけど、その数までは誤り訂正できなくて、誤り検出で、半分より1つ小さい自然数までの誤り訂正ができるんだ。」
息子：「『最小ハミング距離』は奇数の方が都合が無駄が無いね。」
私：「そうだね。」
息子：「でもさー。『ハミング符号』は『最小ハミング距離』が3なんでしょ？結局、1つの誤りしか訂正できないんだね。しかも、『最小ハミング距離』を調べるのって面倒じゃない？」
私：「『ハミング符号』は確かにあまり誤り訂正する能力はないけど、当時は画期的だったんだ。それにこの『ハミング符号』だって、当時はかなり役に立ったし、その後にもっと誤り訂正能力の高い『誤り訂正符号』が出てくるきっかけとなった発展の初めの大きな第一歩なんだ。」
息子：「そうなんだね。」
私：「また、『線形符号』である『ハミング符号』の『最小ハミング距離』は『最小ハミング重み』と同じ数となる。このことから、『ハミング符号』ではわざわざ全ての『符号語』同士の同じ位置のビットの引き算をして『最小ハミング距離』を求めなくても『最小ハミング重み』さえわかれば、誤り訂正できるビット数がわかる。『ハミング符号』は高々16個の『符号語』しかなかったからまだ楽な方だけど、もっと多くの『符号語』を持つ『線形符号』では、『線形符号』の性質を使って比較的楽に『最小ハミング距離』、つまり『ハミング重み』を調べることができる。また、『線形符号』の中でも、もっと楽に作れて、楽に『最小ハミング重み』を求められるいろいろな種類の『線形符号』があるから大丈夫なんだ。」