応用情報技術者試験 応用情報技術者試験 令和4年度春期 午前 問4: ハミング符号とは，データに冗長ビットを付加して，1ビットの誤りを訂正できるようにしたものである。ここでは，X1，X2，X3，X4の4ビットから成るデータに，3ビ

問題本文

ハミング符号とは，データに冗長ビットを付加して，1ビットの誤りを訂正できるようにしたものである。ここでは，X1，X2，X3，X4の4ビットから成るデータに，3ビットの冗長ビットP3，P2，P1を付加したハミング符号X1 X2 X3 P3 X4 P2 P1を考える。付加したビットP1，P2，P3は，それぞれ X1 ⊕ X3 ⊕ X4 ⊕ P1 ＝ 0 X1 ⊕ X2 ⊕ X4 ⊕ P2 ＝ 0 X1 ⊕ X2 ⊕ X3 ⊕ P3 ＝ 0 となるように決める。ここで，⊕ は排他的論理和を表す。 ハミング符号1110011には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

選択肢

• ア.0110011
• イ.1010011
• ウ.1100011
• エ.1110111

正解

ア. 0110011

解説

ハミング符号は、複数の検査式(排他的論理和=XORで0になるべき式)のうちどれが成立しないかの組合せで、誤っているビットの位置を一意に特定できる仕組みです。受信した1110011はX1=1,X2=1,X3=1,P3=0,X4=0,P2=1,P1=1で、3つの検査式に代入するとX1⊕X3⊕X4⊕P1=1、X1⊕X2⊕X4⊕P2=1、X1⊕X2⊕X3⊕P3=1とすべて0になりません。3式すべてに共通して現れるビットはX1だけなので、誤りはX1にあると分かり、X1を1から0に訂正して0110011を得ます。これは3式すべてが0になることで検算でき、正解はアです。

選択肢ごとの解説

• ア.X1を訂正した0110011。3つの検査式に代入するとすべて0になり、ハミング符号の条件を満たすため正解。
• イ.X2を訂正した形だが、X2は3式すべてには含まれないため誤り位置の特定結果と合わず、代入すると第1検査式が1のまま成立しない。
• ウ.X3を訂正した形だが、第2検査式が1のまま成立せず、3式すべてが不成立だった事実と矛盾するため誤り。
• エ.P2を訂正した形だが、P2は第2式のみに関与し、第3式が1のまま成立しないため、3式すべて不成立という症状を説明できず誤り。