ハミング符号の誤り訂正
出典: 令和4年度 春期 応用情報技術者試験 午前 問4 (IPA)
ハミング符号とは，データに冗長ビットを付加して，1 ビットの誤りを訂正できるようにしたものである。ここでは，X₁，X₂，X₃，X₄ の 4 ビットから成るデータに，3 ビットの冗長ビット P₃，P₂，P₁ を付加したハミング符号 X₁ X₂ X₃ P₃ X₄ P₂ P₁ を考える。付加したビット P₁，P₂，P₃ は，それぞれ
X₁ ⊕ X₃ ⊕ X₄ ⊕ P₁ ＝ 0
X₁ ⊕ X₂ ⊕ X₄ ⊕ P₂ ＝ 0
X₁ ⊕ X₂ ⊕ X₃ ⊕ P₃ ＝ 0
となるように決める。ここで，⊕ は排他的論理和を表す。
ハミング符号 1110011 には 1 ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。
- ア 0110011
- イ 1010011
- ウ 1100011
- エ 1110111
正解と解説を見る
正解: ア
- ア: 3 つの式が全て成り立たないので、3 つに共通する X₁ を反転した 0110011 になります。正しい答えです。
- イ: X₂ を反転したものです。X₂ は 1 番目の式に含まれないので、3 つとも成り立たない状況と合いません。
- ウ: X₃ を反転したものです。X₃ は 2 番目の式に含まれないので、3 つとも成り立たない状況と合いません。
- エ: X₄ を反転したものです。X₄ は 3 番目の式に含まれないので、3 つとも成り立たない状況と合いません。
ポイント
1110011 は X₁=1, X₂=1, X₃=1, P₃=0, X₄=0, P₂=1, P₁=1 です。3 つの式を調べます。
- X₁⊕X₃⊕X₄⊕P₁ = 1⊕1⊕0⊕1 = 1 (成り立たない)
- X₁⊕X₂⊕X₄⊕P₂ = 1⊕1⊕0⊕1 = 1 (成り立たない)
- X₁⊕X₂⊕X₃⊕P₃ = 1⊕1⊕1⊕0 = 1 (成り立たない)
3 つの式 全てに含まれるビットは X₁ だけ なので、X₁ が誤りです。X₁ を反転して 0110011 になります。