基本情報技術者試験 ap-2018h30h-a 午前 問3: ハミング符号とは，データに冗長ビットを付加して，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

解説

ハミング符号は、データに冗長ビットを付加し、検査式(排他的論理和)が成り立つかどうかで1ビットの誤り位置を特定して訂正する仕組み。受信符号 1110011 は並びが X1X2X3 P3 X4 P2 P1 なので、X1=1，X2=1，X3=1，P3=0，X4=0，P2=1，P1=1 となる。3つの検査式に代入すると、X1⊕X3⊕X4⊕P1 ＝ 1⊕1⊕0⊕1 ＝ 1(≠0で不成立)、X1⊕X2⊕X4⊕P2 ＝ 1⊕1⊕0⊕1 ＝ 1(不成立)、X1⊕X2⊕X3⊕P3 ＝ 1⊕1⊕1⊕0 ＝ 1(不成立)。3式すべてに共通して現れるビットは X1 だけであり、X1 を 1→0 に反転すると3式すべてが0になる。よって誤りは先頭ビットで、訂正後は 0110011 となり、アが正解。

選択肢ごとの解説

• ア.先頭の X1 を 1 から 0 に訂正した符号。3つの検査式すべてが0になり整合するので正しい。
• イ.X2(2ビット目)を反転した符号。X2 を含む2式は直るが X1⊕X3⊕X4⊕P1 の式が0にならず、誤り位置の特定結果と一致しない。
• ウ.X3(3ビット目)を反転した符号。X3 を含まない式の不成立が残り、訂正位置として不適切。
• エ.P2(6ビット目)を反転した符号。1式しか直らず、3式すべてが不成立だった状況を説明できない。