こんにちは、みっちゃんです。

コンピュータ間での情報のやり取りは、「1」と「0」だけからなるビット列を用いて行われています。

やり取りの最中に、何らかのアクシデントが発生し、ビット列の数字が変わってしまうようなことがあると大問題です。

今回の記事では、情報のやり取りの最中に、ビット列の数字が変わっていないかどうか判定する仕組みについて紹介します。

目次（まとめ）
- ハミング符号を使えば、ビット列の誤りを検出・訂正できる
- ハミング符号は、アメリカ人のハミングさんによって考案された
- ハミング符号では「排他的論理和」を使用する
- 参考文献

ハミング符号を使えば、ビット列の誤りを検出・訂正できる

情報が正しく届いているかどうかをチェックする仕組みはいろいろあります。

一番簡単な仕組みは「パリティビット」という検査用のビットを使ったものです。

「パリティビット」には「偶数パリティ」と「奇数パリティ」があります。

例えば、AさんがBさんに「０１１０」という情報を送りたいとします。

「偶数パリティ」を使う場合、送りたい情報の「１」の数が偶数になるようにします。

つまり、この場合には、先頭に「０」をつけた「００１１０」を送るということです。

逆に「奇数パリティ」を使う場合、送りたい情報の「１」の数が奇数になるようにします。

もし、情報の受け取り手であるBさんが「奇数パリティ付きの情報を受け取ったはずなのに、「1」の数が偶数」であれば、情報が正しく届いていないと判定することができます。

しかし、「パリティビット」では、「１」の数を数えているだけなので、ビット列のどこに誤りがあったのかわからず、情報の訂正ができないという問題があります。

そこで、誤り位置の検出と訂正が可能な「ハミング符号」が考案されました。

ハミング符号は、アメリカ人のハミングさんによって考案された

ハミング符号は、アメリカ人の数学者・計算機科学者であるリチャード・ウェスリー・ハミング（Richard Wesley Hamming）さんによって考案されました。

以前の記事で紹介したノイマンさんと同様、戦時中には、原子爆弾の開発にも携わっていたようです。

Wikipediaによると、計算機科学や電気通信の分野で多大な功績ということで知られています。

ハミング符号では「排他的論理和」を使用する

「排他的論理和」とは、以前の記事で紹介した「OR」に相当し、「１が奇数個あれば０」「１が偶数個あれば１」を出力します。

ハミング符号では、上の図に示すように、送りたい情報（ビット列）を使って、いくつかの組み合わせを考えます。

上の図の場合は、最大4パターン考えられます（実は、そのうち3パターンを用いれば、1ビットの誤りを検出・訂正できることがわかっています）。

それぞれの組み合わせについて「排他的論理和」を計算します。

計算することにより得られたビット列を「検査用冗長ビット」として、送りたい情報の末尾につけて送ります。

データを受け取る側も、検査用冗長ビットを用いて排他的論理和を計算し、全てに対して値が「０」となれば、情報が正しく送られてきたと判断します。

参考文献

きたみりゅうじ「キタミ式イラストIT塾 応用情報技術者」技術評論社