応用情報技術者平成30年春期 午前問3
ハミング符号とは，データに冗長ビットを付加して， 1ビットの誤りを訂正できるようにしたものである。ここでは，X1，X2，X3，X4の4ビットから成るデータに，3ビットの冗長ビットP3，P2，P1を付加したハミング符号 X1X2X3P3X4P2P1を考える。付加ビットP1，P2，P3は，それぞれ
X1⊕X3⊕X4⊕P1＝0
X1⊕X2⊕X4⊕P2＝0
X1⊕X2⊕X3⊕P3＝0
となるように決める。ここで⊕は排他的論理和を表す。
ハミング符号 1110011 には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。
ロジックとしては、
X1X2X3P3X4P2P1 ＝ 1110011 とすると、
X1=1，X2=1，X3=1，X4=0，
P1=1，P2=1，P3=0
になりますね。
そうすると、付加したハミング符号の結果は、
式１） X1⊕X3⊕X4⊕P1 ＝1⊕1⊕0⊕1 0⊕1 =1
式２） X1⊕X2⊕X4⊕P2 ＝1⊕1⊕0⊕1 0⊕1 =1
式３） X1⊕X2⊕X3⊕P3 ＝1⊕1⊕1⊕1 0⊕1 =1
になります。
つまり、三つはすべて間違っているよね。
その三つは、全てあるのビットは、X1ですので、X1が間違っていることが分かれます。
なので、X1を訂正しなきゃいけないです。訂正の方法は唯一で、反転ですね、
1110011 → 0110011
になります。
考え方が分かった上で、仮に、条件は下記のよう
式１）０
式２）１
式３）１
に変わるとすると、間違っているのはどれかとは、X2ですね。
式達の結果により、どのビットが間違っていることが分かれることは、ハミング符号とのものです。