しょうがくせい向けハミング符号のしくみ
ハミング符号の仕組みを小学生にでもわかりやすいように、なるべく簡単な用語で解説しています。
4人の生徒と3人の監視者
出席確認
ここに4人の生徒（緑1人赤3人）がいます。この4人は気まぐれで授業に出席しないことがあります。生徒は大量にいて、先生は名前は知っていますが、顔は全く覚えていません。 先生はその4人の出席状況を確認する為に3人の監視者をつけます。
監視者3人とも、人の顔を覚えるのが苦手で監視者1人につき生徒2人の顔しか覚えていません。 ただ、緑色の生徒に限っては目立つのでどの監視者も教室にいるかどうか確認する事が出来ます。
監視者は大勢の中から自分の覚えている生徒が全員いるかどうかを確認し、誰か1人いないならば「手を挙げて」先生に伝えます。ここで注意するのは偶数人いない場合は手を挙げないことです。覚えておきましょう。
先生は考えて、監視者の覚える生徒を図の様に決めました。ちょうど赤い生徒１人につき2人の監視者がついている事になります。もちろん、緑の生徒は目立つので監視者全員、いるかどうかを知る事が出来ます。
赤の生徒が１人欠席した場合
今、赤の生徒が１人欠席していたとします。すると、その生徒の顔を知っている監視員は2人なので、2人が手を挙げます。 先生は監視員2人が手を挙げ、1人が手を挙げていない事を確認し、休んでいる1人を推測します。
緑の生徒が1人欠席した場合
緑の生徒が欠席した場合はどうでしょうか。もちろん監視者は3人とも緑の生徒の顔は知っているので、3人とも手を挙げます。先生は監視員3人の手が挙がったのを確認し、緑の生徒が休んだ事を知る事が出来ます。
監視員が1人間違えて手を挙げた場合
監視員も人間です。なにかの勘違いで生徒がいるのに挙手してしまったとしましょう。
この場合は今までとは異なり、監視員が2人ではなく１人だけ手を挙げる格好になります。生徒が誰か1人いないのであれば監視員は2人手を挙げるはずです。先生は、この監視員が間違えたんだなと判断できます。
合計2人以上の欠席・監視員の間違えの場合
今までは生徒が1人欠席した場合について例を挙げて来ました。どれも１人だけの場合は正確に真実を把握できました。 それでは2人以上、例えば生徒が2人欠席したり、監視員が2人間違えたり、生徒が1人休んで、さらに監視員が1人間違えた場合はどうでしょうか。
結論から言うと、先生はここで割り切りが必要になります。どんな割り切りかと言うと「欠席・間違えは合計1人だけで正確に真実を把握する」か、「欠席・間違えを合計2人、起きた事だけを把握する」かです。
具体例を挙げていきましょう。
赤の生徒が2人欠席した場合
赤の生徒が二人欠席した場合を考えます。「二人（偶数人）いない場合は手を挙げない」ルールを覚えていますか？監視員は二人手を挙げます。どこかで見た事あります。そう、前に生徒が１人休んだ場合と同じです。
これでは先生は、赤の生徒が1人休んだのか別の2人が休んだのかわかりません。ただ、一つわかる事があります。それは「なにかがおかしい」ことです。
これが割り切りが必要ということです。2人の異常を想定する場合、「真実を把握」するののではなく「異常を検出」することに割り切る必要があります。
続けましょう。
緑の生徒と赤の生徒がそれぞれ1人ずつ欠席した場合
「監視員は全員、緑の生徒は把握」出来ること、「偶数人いない場合は手を挙げない」ことを思い出してください。
監視員が1人。これは監視員が間違えている場合と同じですね。どちらかはわかりませんが、割り切りにより「なにか異常がおこった」ことは把握出来ました。
実際のハミング符号
なんだかつかみ所のない例えになってしまいましたが、ハミング符号の雰囲気を感じて頂くのが目的なのでがまんしてください。
実際のハミング符号との対応を書きます。
生徒の数は情報数
先ほどの例えでは生徒は4人いました。実際のコンピューターの中の情報では0と1が4つならんでいます。0000や1111、1010などです。この4つという数を情報数といいます。それぞれの0と1にはどんな意味合いを持たせても構いません。0を雨、1を晴として1010は晴雨晴雨としてもいいですし、0が負け、1を勝ちとして1001を勝負負勝という記録としてもよいです。
しかし、コンピュータの情報は伝わる時に「間違える」可能性があります。晴雨晴雨を1010としてネットワークに流したはずが、実際には1011で晴雨晴晴と伝わったりする事があります。
生徒と監視員の合計が符号長
それをより確実に伝える方法が誤り検出符号や誤り訂正符号です。「違う事」を知るだけなのが検出符号、「訂正」まで出来るのが訂正符号です。
先の例でいう監視員がそれに該当します。3人いたのでコンピュータでは0か1が3つ並んでいます。000かも知れませんし111かも知れません。この3つと先の情報数4を足した7を「符号長」と呼びます。
誤り検出と訂正
三人の監視員はそれぞれ2人と共通の1人を監視していました。ハミング符号においても同様です。それぞれの誤り訂正符号は4つの情報数のうちの3つを「監視」しています。具体的には符号に対応した3つの情報数から符号自身が決定されます。計算は排他的論理和（XOR)を使います。符号は自分を含めた4つの0と1を「合計で偶数」になるように決定されます。監視する情報数が110だったら0、100だったら1という具合です。
監視する情報数のパターンは先の例の様に無駄無く割り当てられています。それにより対応情報数とハミング符号が「偶数でない」という異常から問題を「訂正」または「検出」できる仕組みが出来上がります。
まとめ
今回紹介したのは情報数4に誤り訂正符号3の場合でした。実際はもっと長い情報数でも対応するハミング符号長があります。下記のサイトが参考になります。
半世紀以上前にベル研究所の技術者によって開発されたこのハミング符号、今日においてもメモリやハードディスクの信頼性向上技術として使われています。情報の間違いを検出するだけではなく訂正してしまうという技術の面白みを感じていただれば幸いです。
