4ビットから成る情報ビット ｘ1ｘ2ｘ3ｘ4 に対して、
(ｘ1 ＋ ｘ2 ＋ ｘ3 ＋ ｘ5) mod 2 ＝ 0
(ｘ1 ＋ ｘ2 ＋ ｘ4 ＋ ｘ6) mod 2 ＝ 0
(ｘ2 ＋ ｘ3 ＋ ｘ4 ＋ ｘ7) mod 2 ＝ 0
を満たす冗長ビット ｘ5ｘ6ｘ7 を付加した符号ｘ1ｘ2ｘ3ｘ4ｘ5ｘ6ｘ7を送信する。
受信符号ｙ1ｙ2ｙ3ｙ4ｙ5ｙ6ｙ7が、送信符号と高々1ビットしか異ならないとき、
(ｙ1 ＋ ｙ2 ＋ ｙ3 ＋ ｙ5) mod 2
(ｙ1 ＋ ｙ2 ＋ ｙ4 ＋ ｙ6) mod 2
(ｙ2 ＋ ｙ3 ＋ ｙ4 ＋ ｙ7) mod 2
がそれぞれ0になるかどうかによって、正しい情報ビット ｘ1ｘ2ｘ3ｘ4 を求めることが可能である。ｙ1ｙ2ｙ3ｙ4ｙ5ｙ6ｙ7 ＝ 1100010 であるとき、正しい情報ビットはどれか。ここで、ａ mod ｂ は、ａ を ｂ で割った余りを表す。
ア 0100
イ 1000
ウ 1100
エ 1101
エ
ハミング符号に関する問題である。ハミング符号は、データに冗長ビットを付加して、1ビットの誤りを訂正できるようにしたものである。
(ｙ1＋ｙ2＋ｙ3＋ｙ5) mod 2 ＝ (1＋1＋0＋0) mod 2 ＝ 0
(ｙ1＋ｙ2＋ｙ4＋ｙ6) mod 2 ＝ (1＋1＋0＋1) mod 2 ＝ 1
(ｙ2＋ｙ3＋ｙ4＋ｙ7) mod 2 ＝ (1＋0＋0＋0) mod 2 ＝ 1
であるから、1つ目の式に含まれず、2つ目と、3つ目の式に含まれるビットを発見すればよい。この条件に合うのは、ｙ4であるから、ｙ4のビットが誤っていることが分かる。
従って正しい情報ビットは、1101である。
| 問２ | 目次 | 問４ |