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

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

　ア 　0110011
　イ 　1010011
　ウ 　1100011
　エ 　1110111

答え　ア

【解説】
問題となるハミング符号
　X1 X2 X3 P3 X4 P2 P1=1 1 1 0 0 1 1
について、3つの条件式を計算します。
　X1 2 X3 2 X4 2 P1=1 2 1 2 0 2 1=1　…　不成立
　X1 2 X2 2 X4 2 P2=1 2 1 2 0 2 1=1　…　不成立
　X1 2 X2 2 X3 2 P3=1 2 1 2 1 2 0=1　…　不成立
3つの条件式がすべて不成立だったので、このハミング符号にはエラーがあり、エラーの箇所は3つの条件式のすべてで使われているX1であるのがわかり、訂正内容はX1の値を1から0になります。
したがって、訂正したハミング符号は
　X1 X2 X3 P3 X4 P2 P1=0 1 1 0 0 1 1
(ア)になります。

【キーワード】
・ハミング符号
・排他的論理和

【キーワードの解説】

戻る 一覧へ 次へ