ハミング符号とは、データに冗長ビットを付加して、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
(ア)になります。
【キーワード】
・ハミング符号
・排他的論理和
- ハミング符号
データの誤り検出と訂正を行うための付加情報。
ハミング符号では2ビットの誤り検出と、1ビットの誤り訂正を行うことが可能です。 - 排他的論理和
与えられた複数の命題(条件)のうち真となる命題の個数が奇数個のとき真となり、偶数個のとき偽となる論理演算です。
命題が2つのときの排他的論理和の真理値表は下のようになります。命題1 真 偽 命題2 真 偽 真 偽 真 偽
もっと、「排他的論理和」について調べてみよう。
戻る
一覧へ
次へ