ハミングコードの符号化原理の解析と検証方法

1. パリティチェック

文字列中の1の数が偶数であれば、その文字列で運ばれている情報は正しく、そうでなければ間違っているということになるのです。文字列の最初にチェックデジットを追加することで、パリティを実現することができます。

例

コード文字列10010を送信したいので、送信時に010010を渡すのですが、ここが The 0 at the beginning is the checksum bit .
文字列コード10000を送信したいので、送信時に110,000を渡す、ここで The 1 at the beginning is the check digit .
どちらの例も1の数は偶数です。

2. ハミングコード

まず、ハミングコードというのは、パリティを利用したコードです。数字の羅列をグループ化し、グループチェックでどのビットが誤りかを判断するという非常に巧妙な方法を用いています。そして、その誤りの位置を修正することができます

注意してください。

ハミングコードデフォルトは、1つのエラーで1つの文字列のデータになります

ハミングコードのグループ化方法。

実際にP1グループとP2グループの両方に入っているデータもあることがわかります。これをどのようにグループ化するか、これは覚えておいてほしいのですが、原理はないんですよ、ハハ。あらかじめやっておくことは、この位置を表す数字を2進数に変換して、:

ポジション1をポジション0001に

ポジション2、これはポジション0010になります。

ポジション3は、ポジション0011になります。

ポジション4は、ポジション0100となります。

ポジション5、ポジション0101になります。

ポジション6、ポジション0110となる。

というルールが登場するわけです。

位置がこのフォーム、XXX1、に一致するところ、P1へ。

位置がこの形式、XX1X、に一致する場合、P2へ。

位置が本形式の X1XX と一致する場合、P3 へ。

位置がこのフォームの1XXXと一致する場合、P4へ。

そして、個々のチェックサムもグループに分けられ、各グループには1つのチェックサムしかありません。

例を挙げましょう。

このコード一式を渡したいのです。XX1X101X011

ビットは全部で11ビットです。

マークXはチェックサムの位置で、その値は今のところわかりません。

1,3,5,7,9,11の位置のデータはP1グループに入る。(これらの位置のバイナリを変換すると、位置がXXX1に一致することがわかります）。

2,3,6,7,10,11の位置のデータはP2グループに入ります。(ポジションはXX1Xと一致します）

ポジション 4,5,6,7 のデータはグループ P3 に入ります。(ポジションはX1XXと一致)

8,9,10,11のデータはP4グループに入ります。(位置は1XXXに一致)

そして、グループ分けを決定し、それに伴いチェックサムの値を決定する。

こうして、コードの文字列全体が決定される。

チェックサムコードの位置

ハミングコードを使うデータの文字列の中で、2のi乗のところにチェックデジットを入れる、これがルールだから覚えておいてね。

チェックデジットは1か0であり、チェックデジットがあるグループの1の数は偶数である。

図に示すように

緑色の場所はチェックサムを入れる場所で、1,2,4,8,16 ......と、2のi乗を繰り返していきます。

チェックサムは実際には各グループに固有であり、各グループはチェックサムに対してのみ固有である

送信側から見て、ハミングコードでデータを送るにはどうしたらいいのでしょうか？

まず、実際に送信するビットが何ビットかを考えてみましょう。チェックデジットは全部でkビット、送りたい元のデータは全部でnビットとします。チェックデジットはチェックデジットの間違いもチェックしなければならないので、チェックするビットは全部でk+nビット、kビットチェックデジットは2^kビットのコードを検出できるけどできないので、チェックデジのビット数は次の式を満たさなければならないことに注目します。

2 k > k + n 2^k>k+n 2k>k+n, または 2 k - 1 ≧ k + n 2^{k}-1 \geq k+n 2k-1 ≧ k+n

これにより、何個のチェックサムを使用するかを把握することができます。

実はハ、実はそんなに面倒なことはしなくていいんだ。教科書はいつも複雑だからね。例えば、101011111を送りたいなら、まずチェックデジットを取って、空いたビットに送りたいデータを埋めればいいんだ。

1,2,4,8 ......といったビットを取っていくわけですが、もちろんこれは手でやった方が直感的です。

じゃあ、フィールドを埋めてグループ分けして、チェックサムの値も決めたと思うから、送信して。

私は受信者ですが、ハミングコードを受信しました。ハミングコードの性質を利用して、どのようにエラーをチェックすればよいのでしょうか。

1. P1、P2、P3 ......にグループ分けする。

2. 各グループを別々にチェックし、エラーがなければ0、エラーがあれば1を与える。

3. 最初の質問を思い出してください、ハミングコードはどのように機能するのでしょうか？3つのグループなら3つの円を描けるけど、100のグループだと円を描くのが大変だ！」と思われたかもしれませんね。

これに相当するのがこちら、ハミングは実に巧妙です。

Pを大きいものから小さいものへと並べると、1010という文字列になります。

例えば

     グループ P5 P4 P3 P2 P1

     フラグです。1 0 1 0 1

大きいものから順に並べると、フラグが0を1つずつ並んだ文字列となる。この数字が、間違っていたデータの位置です。

この場合、10101の位置のビットが間違っており、10進数に変換すると21の位置の数値が間違っていることになります。

そして、間違った位置を見つけると、2進数なので0か1のどちらかなので、途中で修正することができるのです。 <リンク

以上、ハミングコードの符号化原理と検証方法について詳しく分析しましたが、ハミングコードの符号化と検証に関するより詳しい情報は、スクリプトハウスの他の関連記事にもご注目ください!