平成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
(ア)になります。


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

キーワードの解説

戻る 一覧へ 次へ