ハミングコードを使っての訂正(キャッシュ）

下にある、6-bit data words をシングル　エラー　コレクション　ハミング　コードをつかって書き直せ。
という問題なんですが。ハミングコードエラーを出すとすると、6bitなのでものすごい大きい数になってしまうことが予想されて、不に落ちない感じがします。しかも書き直せと書いてあるんですよねぇ。。いったい何から初めてどうすればいいのか分かりません。。ヒントでもいいのでいただけると、ありがたいです。
よろしくお願いします。

Rewrite the following 6-bit data words using a single error correction Hamming code:
Ａ　100 011
B. 110 010

No.1 ベストアンサー 回答者： ymmasayan 回答日時： 2011/04/18 12:46

↓の問１５のように４ビット＋３ビットの例がよく使われます。

６ビットでも８ビットでも＋４ビットにすれば１６ビットまで表せますので
問題ありません。
後は１ビットどこに追加するかということと
式を１個追加して整理することですね。

参考URL：http://www.mirai.ne.jp/~suehiro/am/h0904/1-h9am1 …

この回答へのお礼

凄くよく分かりました！ありがとうございます＾＾

AとBの２進数の中に冗長ビットが含まれて居ないと思っていたのですが含まれていたようなので、シンプルにできました。
ちなみに

情報ビットＸ1,Ｘ2,Ｘ3,Ｘ4の４ビットに、冗長ビットとしてＰ3,Ｐ2,Ｐ1の３ビットを付加したハミング符号Ｘ1Ｘ2Ｘ3Ｐ3Ｘ4Ｐ2Ｐ1

のＸ1Ｘ2Ｘ3Ｐ3Ｘ4Ｐ2Ｐ1はP3とX4は逆ですよね？

即効の回答ありがとうございました＾＾

お礼日時：2011/04/18 13:54

No.2 回答者： mtaka2 回答日時： 2011/04/18 13:30

ハミング符号では、

「パリティ値」が「全体のビット数」の中のエラービットの位置を示す形になります。

つまり、パリティ値が3ビットの時は、3ビットで表現できる数は0～7なので(0=エラーなし)で、
1～7がエラービットの位置を表すことになり、全体では上限7bitになります。つまり、データは上限4bit。

パリティ値を4ビットにすると、4ビットで表現できる数は0～15なので(0=エラーなし)で、
1～15がエラービットの位置を表すことになり、全体では上限15bitになります。つまり、データビットは最大11bit。
11bit以下である6ビットのデータも、パリティ4ビットでエラー訂正可能であり、その時は全体のハミング符号は10bitになります。


次に解き方。基本はデータ4bit-パリティ3bitの場合と同じです。パリティ4bitの場合、データの列びは、たとえば下記のようになります。
データ:X6 X5 X4 X3 X2 X1
パリティ: P4 P3 P2 P1
ハミング符号: X6 X5 P4 X4 X3 X2 P3 X1 P2 P1

このハミング出力のビットのならびは、P1が2^0=1番目、P2が2^1=2番目、P3が2^2=4番目、P4が2^3=8番目にくるように、パリティ値をデータの中に混ぜこんだものです。


あとは、各データのビット位置を二進数で表すと
X6=10ビット目=1010
X5= 9ビット目=1001
P4= 8ビット目=1000
X4= 7ビット目=0111
X3= 6ビット目=0110
X2= 5ビット目=0101
P3= 4ビット目=0100
X1= 3ビット目=0011
P2= 2ビット目=0010
P1= 1ビット目=0001

ですので、この2進数で表したビット位置が1になっているビットをXORすればパリティ値が求まります。右から4ビット目: これが1になっているのはP4、X5、X6 →P4=X6 xor X5
右から3ビット目: これが1になっているのはP3、X2、X3、X4 →P3=X4 xor X3 xor X2
右から2ビット目: これが1になっているのはP2、X1、X3、X4、X6→P2=X6 xor X4 xor X3 xor X1
右から1ビット目: これが1になっているのはP1、X1、X2、X4、X5→P1=X5 xor X4 xor X2 xor X1
となります。

これを元に、Ａ:100 011の場合のハミング符号を求めると、
X6=1、X5=0、X4=0、X3=0、X2=1、X1=1ですから、
P4=1 xor 0 = 1
P3=0 xor 0 xor 1 = 1
P2=1 xor 0 xor 0 xor 1 = 0
P1=0 xor 0 xor 1 xor 1 = 0
ですので、
ハミング符号: X6 X5 P4 X4 X3 X2 P3 X1 P2 P1 = 1010011100
になります。

これは上述のビットならびを仮定した解法です。ハミングコードの符号の混ぜ込み方は特に定められいるものではなく、
問題によっては逆順に並べる場合もあったりするので、問題条件にあわせて考え直して下さい。

この回答へのお礼

あああー！せっかく長く答えていただいたのに、行き違いでした。。。でも、冗長ビットが含まれていると思いましたが、こう考えて見ると含まれていないですよね、。。。きっと。問題があまり理解できていないと思うので、両方もとめることにします。ありがとうございました＞＜

お礼日時：2011/04/18 14:04