ハミング符号の誤り訂正
出典: 平成30年度 春期 応用情報技術者試験 午前 問3 (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 つの式が全て不成立なので、全ての式に含まれる X₁ が誤りです。X₁ を反転した 0110011 は正しい答えです。
- イ: X₂ を反転したものです。X₂ は P₁ の式に含まれないので、X₂ の誤りなら P₁ の式は成立するはずです。
- ウ: X₃ を反転したものです。X₃ は P₂ の式に含まれないので、X₃ の誤りなら P₂ の式は成立するはずです。
- エ: X₄ を反転したものです。X₄ は P₃ の式に含まれないので、X₄ の誤りなら P₃ の式は成立するはずです。
ポイント
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 になります。