ハミング符号とは，データに冗長ビットを付加して，1ビットの誤りを訂正できるようにしたものである。
ここでは，X_1，X_2，X_3，X_4の4ビットから成るデータに，3ビットの冗長ビットP_3，P_2，P_1を付加したハミング符号X_1X_2X_3P_3X_4P_2P_1を考える。
付加したビットP_1，P_2，P_3は，それぞれ
X_1⊕X_3⊕X_4⊕P_1＝0
X_1⊕X_2⊕X_4⊕P_2＝0
X_1⊕X_2⊕X_3⊕P_3＝0
となるように決める。
ここで，⊕は排他的論理和を表す。
ハミング符号1110011には1ビットの誤りが存在する。
誤りビットを訂正したハミング符号はどれか。
正答1
解説
正解は1です。
ハミング符号では、検査用の式が成り立つかどうかを調べ、成り立たない式の組合せから誤ったビットの位置を特定します。
受信した1110011を並び順X_1X_2X_3P_3X_4P_2P_1に当てはめると、X_1＝1、X_2＝1、X_3＝1、P_3＝0、X_4＝0、P_2＝1、P_1＝1です。
【計算】
1つ目の式はX_1⊕X_3⊕X_4⊕P_1＝1⊕1⊕0⊕1＝1となり、成り立ちません。
2つ目の式はX_1⊕X_2⊕X_4⊕P_2＝1⊕1⊕0⊕1＝1となり、成り立ちません。
3つ目の式はX_1⊕X_2⊕X_3⊕P_3＝1⊕1⊕1⊕0＝1となり、成り立ちません。
3つの式すべてに含まれるビットはX_1だけです。
したがって誤りはX_1であり、1を0に直すと0110011になります。
【選択肢別解説】
1：○ X_1を反転した符号です。
3つの式がすべて不成立であることと、3式すべてに含まれる唯一のビットがX_1であることが一致します。
2：× 2ビット目のX_2を反転したものです。
X_2は1つ目の式に含まれないので、X_2の誤りなら1つ目の式は成り立つはずであり、今回の結果と合いません。
3：× 3ビット目のX_3を反転したものです。
X_3は2つ目の式に含まれないので、X_3の誤りなら2つ目の式は成り立つはずです。
4：× 5ビット目のX_4を反転したものです。
X_4は3つ目の式に含まれないので、X_4の誤りなら3つ目の式は成り立つはずです。
【ポイント】
1ビットの誤りでは、誤ったビットを含む式だけが不成立になります。
どの式が不成立かの組合せと、各ビットがどの式に含まれるかを照らし合わせるのが定石です。
排他的論理和は、1の個数が奇数なら1、偶数なら0になると考えると速く計算できます。