今日は、リチャード・ハミングの誕生日(1915)
プログラミング…というより、情報理論をやったことのある人は、「ハミング符号」を聞いたことがあるかもしれません。
その考案者です。
他にも、ハミング距離やハミング重み、ハミング窓やハミング数など、彼の名がついた概念は多数。
ハミング符号については後で説明しようと思いますが、ハミング距離・重みは、ハミング符号に関連した概念。
ハミング窓は、通信における周波数特性などの問題改善に役立つ概念。
（応用は幅広いのですが、例えばインターネットで高速な通信ができるのは、こうした概念のおかげです）
ハミング数は、1,2,3,5 の掛け算だけで作られる数。
1,2,3,4,5,6,8,9,10,12,15... などです。
10,12,60 などを含むため、よく使われる「 n 進法」との相性が良い数値になります。
実は、昔からこれらの数は特別視されていたのですが、ハミングが「効率よくこれらの数字を作り出すアルゴリズムを求めよ」という問題を出したため、ハミング数とも呼ばれるようになりました。
＃この問題に対する最初の一般解は、ダイクストラが出したようです。
さて、ハミング符号について説明しましょう。
大学の時に情報理論の講義でこれを知って、感動しました。
1980年代のパソコン少年にとって、「チェックサム」は見慣れたものでした。
雑誌に載っているプログラムには数値データが延々と続く場合があって、入力の際にどこか1カ所間違えただけで、プログラムは動かなくなってしまう。
でも、人間だから打ち間違いは当然生じます。
このミスを防ぐのがチェックサム (check sum) で、当時の雑誌プログラムではお馴染みでした。
sum は「集計」の意味。数値を全部足したものです。
例えば、メモリ上の 16進数を延々と打ち込むのだとしたら、16byte ごとに「全部足して、下1byteだけを取り出した数値」がついている。
数値を打ち込むためのツールの方にもチェックサムを表示する機能があるので、合っていれば打ち間違いはありません。
でも、打ち間違いがある、とわかった時には、どこが間違っているのかを自分で探し、訂正する必要がありました。
同じように「パリティ」という概念もあります。
こちらは、1byte とか 1word の範囲内でのチェックサムのようなもの。
1byte は 8bit ですが、この 8bit を、すべて XOR します。
XOR っていうのは、「2つのビットが違っていれば 1、同じなら 0」という単純な計算で、回路も簡単に作れます。
これを、8bit 分全部行います。
結果は「8bit 中、1のビットが奇数個あれば 1、偶数個なら 0」です。
この結果を「パリティビット」と呼びます。9bit 目として保存しておきます。
再びこのデータを使うときにも、同じようにデータ部分からパリティビットを求め、保存してあった結果と比較します。
合っていれば、データは壊れていません。大丈夫。
壊れていたら？ …コンピューターに異常があった、と信号を出して、緊急停止でしょうね。
計算はやり直しですが、間違った計算を延々と続けて気づかない、というよりは良いでしょう。
このやり方だと、8bit のデータごとに 1bit のパリティが必要になります。データを保持する、という意味では、1/9 の無駄。
でも、16bit で 1bit のパリティ、でも構いません。それなら無駄は 1/17 です。
ただし、間違いが起きた個所を特定したい、と考えたときには、「8bit のどれか」まで絞り込めるか、「16bit のどれか」になるか、という違いがあります。
無駄を少なくすると、場所の特定はしにくくなるのです。
ここら辺までは「間違いがないかチェックしよう」という話です。
でも、ハミングが考案した「ハミング符号」(1950)はちょっと違いました。
「間違いがあるなら、直すところまでやってしまおう」というのです。
ハミング符号では、全体の長さに決まりがあります。
必ず、2^m-1 bit にならなくてはなりません。
7 とか 15 とか、今のパソコンで扱うにはちょっと中途半端な単位。
そして、この長さの中に「データ」と「誤り訂正符号」が入ります。
誤り訂正符号の長さは、m です。ということは、全体から mを引いたのが、使えるデータ部分。
全体が 7bit の場合、データが 4bit 、全体が 15bit なら、データは 11bit になります。
話を簡単にするために、ここでは 7bit で考えてみます。
データは 4bit あるので、それぞれのビットに小文字で名前を付けます。
abcd 、としましょう。
誤り訂正符号は 3bit なので、ABC とします。
誤り訂正符号は、全体の中の 1,2,4,8 ... 番目に入っているとします。
全体のビットの並びはこうなります。
ABaCbcd
これで 7bit です。
a は、３番目、２進数で書くと 011 番目に並んでいます。
b は、５番目、２進数で書くと 101 番目です。
c は、６番目、２進数で書くと 110 番目です。
d は、７番目、２進数で書くと 111 番目です。
A は、並び順の最下位ビット…1の位が 1 だった部分のビットのパリティです。
B は、2の位が 1だったビットのパリティ、C は、4 の位が 1 だったビットのパリティです。
XOR を + で表現することにすると、
A = a+b+d
B = a+c+d
C = b+c+d
となります。
これで計算終了。簡単です。
データの 4bit が、 1010 だったとしましょう。
全体の 7 bit は、次のようになります。
1011010
どこか 1bit がおかしくなったとしましょう。
例えば、先頭がおかしい。
先頭は誤り訂正符号ですから、データ部に影響はないです。
そして、データ部から「誤り訂正符号」を求め直すと、パリティ A が間違っている、ということが分かります。
ここで、A が 1の位、B が 2の位、C が 4の位の２進数（つまり CBA と並んでいる）と考えます。
「違った部分」を 1 、正しい部分を 0 として考えると、2進数で 001 という数値が現れます。
これが「１番目のビット」、つまり A が誤っている、という意味になるのです。
今度は、データ部分である a が間違っている、と考えましょう。
誤り訂正符号の計算式をもう一度書きます。
A = a+b+d
B = a+c+d
C = b+c+d
a の部分がおかしいのですから、A B が変化します。
すると、誤り訂正符号は 011 番目…つまり３番目のビットがおかしいことを示すようになります。
３番目のビットというのは、まさに a のことです。
bit の値は 0 か 1 しかないので、「誤っている」のであれば、反転すれば訂正できます。
これで訂正完了。
同じように、どこのビットを変えても、正しく誤りの位置を示します。
数学的に検証してみると、A B C はそれぞれ、ただのパリティにすぎません。
しかし、パリティを取る bit を巧妙に絞り込んであります。
そのため、A B C の誤り検出が、そのまま誤りの「位置」を示せるようになっているのです。
これにより、ハミング符号では、1bit が間違えていても正しく訂正できます。
ここでは、全体が 7bit でした。
誤り訂正符号は 3bit だから、８つの状態があるのだけど、エラーがない場合は「0」になるので、位置を示すのには使えない。
だから、残りの「７つ」の状態で、7bit の位置を示すのです。
これが、全体が 7 とか 15 とか、中途半端に見える長さになってしまう理由。
2進数の性質をうまく使い、非常に巧妙にできています。
大学生の時にこれを知り、ちょっと感動しました。
ちょっと話は違うのですが、室町時代から伝わる手品で、「目付字」というものがあります。
後から知ったのですが、これが、２進数の性質を巧妙に使ったもので、知った時に「ハミング符号」を思い出しました。
本当に、全く目的は違うし、やっていることも違う。
だけど、２進数の性質を同じように応用したトリック。
詳しく知りたい人は、上のリンク先を読んでみてください。
こういう数学トリックを思いつく人はすごいなぁ、と思います。
ハミング符号では、2bit 以上間違えると、誤りを訂正しようとして失敗します。
これを防ぐ「拡張ハミング符号」というのもあります。
「1bit のパリティを付加し、誤りが 1bit か 2bit かを検出できるようにしたもの」です。
長くなるので詳細は省きます。これ以上知りたい人は自分で調べて。
今ではハミング符号よりも巧妙でよくできた誤り訂正符号もあります。
でも、誤りの「検出」しか考えられていなかった頃に、最初に「訂正」という概念を作り出したのは、ハミング符号なのです。
最初にやってみせた、というすごさは、いつまでたっても変わりません。
同じテーマの日記(最近の一覧)
別年同日の日記
申し訳ありませんが、現在意見投稿をできない状態にしています。 |