問題プレビューID: a9f1fc7b応用情報技術者試験 2022年(令和4年度)春期 午前

問 4
応用情報技術者試験 2022年(令和4年度)春期 午前

ハミング符号とは,データに冗長ビットを付加して,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 ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

解説

正解は「ア」です。

受信したハミング符号 11100111110011 を 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=1≠0X_1 \oplus X_3 \oplus X_4 \oplus P_1 = 1 \oplus 1 \oplus 0 \oplus 1 = 1 \neq 0
  • X1⊕X2⊕X4⊕P2=1⊕1⊕0⊕1=1≠0X_1 \oplus X_2 \oplus X_4 \oplus P_2 = 1 \oplus 1 \oplus 0 \oplus 1 = 1 \neq 0
  • X1⊕X2⊕X3⊕P3=1⊕1⊕1⊕0=1≠0X_1 \oplus X_2 \oplus X_3 \oplus P_3 = 1 \oplus 1 \oplus 1 \oplus 0 = 1 \neq 0

3 式すべてが 0 にならないので,共通して含まれるビット X1X_1 が誤っていると判定できます。X1X_1 を反転させると 01100110110011 となり,これが誤りを訂正したハミング符号です。

  • イ・ウ・エ: いずれも X1X_1 以外のビットを反転したものであり,訂正後の符号として正しくありません。

関連問題

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