ハミング符号とは、データに冗長ビットを付加して、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
(ア)になります。
【キーワード】
・ハミング符号
・排他的論理和
命題1 | |||
---|---|---|---|
真 | 偽 | ||
命題2 | 真 | 偽 | 真 |
偽 | 真 | 偽 |