問題プレビューID: 5b1993d7応用情報技術者試験 2013年(平成25年度)春期 午前

問 4
応用情報技術者試験 2013年(平成25年度)春期 午前

ハミング符号とは,データに冗長ビットを付加して,1 ビットの誤りを訂正できるようにしたものである。ここでは,X1X_1,X2X_2,X3X_3,X4X_4 の 4 ビットから成るデータに,3 ビットの冗長ビット P3P_3,P2P_2,P1P_1 を付加したハミング符号 X1X2X3P3X4P2P1X_1 X_2 X_3 P_3 X_4 P_2 P_1 を考える。付加ビット P1P_1,P2P_2,P3P_3 は,それぞれ

X1⊕X3⊕X4⊕P1=0X_1 \oplus X_3 \oplus X_4 \oplus P_1 = 0 X1⊕X2⊕X4⊕P2=0X_1 \oplus X_2 \oplus X_4 \oplus P_2 = 0 X1⊕X2⊕X3⊕P3=0X_1 \oplus X_2 \oplus X_3 \oplus P_3 = 0

となるように決める。ここで,⊕\oplus は排他的論理和を表す。

ハミング符号 1110011 には 1 ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

解説

正解は「ア」です。

受信した符号語 1110011 を X1X2X3P3X4P2P1X_1 X_2 X_3 P_3 X_4 P_2 P_1 に当てはめると,X1=1X_1 = 1,X2=1X_2 = 1,X3=1X_3 = 1,P3=0P_3 = 0,X4=0X_4 = 0,P2=1P_2 = 1,P1=1P_1 = 1 です。各パリティ検査式を計算すると,

  • X1⊕X3⊕X4⊕P1=1⊕1⊕0⊕1=1X_1 \oplus X_3 \oplus X_4 \oplus P_1 = 1 \oplus 1 \oplus 0 \oplus 1 = 1
  • X1⊕X2⊕X4⊕P2=1⊕1⊕0⊕1=1X_1 \oplus X_2 \oplus X_4 \oplus P_2 = 1 \oplus 1 \oplus 0 \oplus 1 = 1
  • X1⊕X2⊕X3⊕P3=1⊕1⊕1⊕0=1X_1 \oplus X_2 \oplus X_3 \oplus P_3 = 1 \oplus 1 \oplus 1 \oplus 0 = 1

となり,3 式すべてが 0 と一致しません。3 式すべてに共通して現れるビットは X1X_1 だけなので,誤っているビットは X1X_1 です。X1X_1 を反転すると 0110011 となり,正解は「ア」です。

  • イ・ウ・エ: それぞれ X2X_2,X3X_3,P3P_3 を反転したもので,3 式の検査結果と一致しません。

関連問題

本文が同じ・似ている問題を表示しています