4ビットのデータに3ビットのチェックビットを追加して、1ビットの符号誤り訂正を行いたい。追加する1ビット目はデータの先頭3ビット (ビット1、2、3) の排他的論理和、2ビット目はデータの末尾の3ビット (ビット2、3、4) の排他的論理和とした。 3ビット目として最も適切なものを次の中から選べ。
① ビット1、4の排他的論理和
② ビット2、4の排他的論理和
③ ビット1、2、4の排他的論理和
④ ビット1、2、3、4すべての排他的論理和
⑤ どのようにしても、誤り訂正ができない
③
排他的論理和 (XOR) は、真を1、偽を0で表すと、
以下の通りとなる。
0 XOR 0 ＝ 0
1 XOR 1 ＝ 0
0 XOR 1 ＝ 1
1 XOR 0 ＝ 1
2ビットの排他的論理和でも、3ビットの排他的論理和でも、4以上の排他的論理和でも、1の個数が
奇数の時:1
偶数の時:0
となる。
これらを踏まえて、
追加する3ビットの3ビット目にビット1、2、4の排他的論理和とすると
4ビットのデータが例えば、0101の時、
追加する3ビットの1ビット目は 0,1,0の排他的論理和だから 1
追加する3ビットの2ビット目は 1,0,1の排他的論理和だから 0
追加する3ビットの3ビット目は 0,1,1の排他的論理和だから 0
となる。つまり
0101100
である。
さてこの例の場合、1ビット目が誤って
1101100となったとき、
・追加する3ビットの1ビット目が1であるため、ビット1、2、3のうちどれか1つが誤りであることが判る。
・追加する3ビットの2ビット目が0であるため、2、3、4には誤りがないことが判る。
・追加する3ビットの3ビット目が0であるため、1、2、4のうちどれか1つが誤りであることが判る。
つまり誤りは1ビット目であることが判る。
次に2ビット目が誤って
0001100となった時、
・追加する3ビットの1ビット目が1であるため、ビット1、2、3のうちどれか1つが誤りであることが判る。
・追加する3ビットの2ビット目が0であるため、2、3、4のうちどれか1つが誤りであることが判り、その誤りは2ビット目か3ビット目に絞られる。
・追加する3ビットの3ビット目が0であるため、1、2、4のうちどれか1つが誤りであることが判り、その誤りは2ビット目に絞られる。
つまり誤りは2ビット目であることが判る。
5ビット目が誤って
0101000となった場合、
・追加する3ビットの1ビット目が0であるため、ビット1、2、3のうちどれか1つが誤りであることが判る。
・追加する3ビットの2ビット目が0であるため、2、3、4には誤りがないことが判る。
・追加する3ビットの3ビット目が0であるため、1、2、4には誤りがないことが判る。
つまり、上記は矛盾し、ビット1、2、3、4いずれにも誤りがないため、5ビット目自身が誤りと判る。
【別解】
難しく考えなくても、
1ビット目はデータの先頭3ビット (ビット1、2、3) の排他的論理和
2ビット目はデータの末尾の3ビット (ビット2、3、4) の排他的論理和
とくれば、
3ビット目はビット1、2、4もしくは、ビット1、3、4の排他的論理和ではないかと予想はつくと考えられる。
現に、3ビット目はビット1、3、4の排他的論理和でも1ビットの符号誤り訂正が可能である。
| Ⅳ－１０ | 目次 | Ⅳ－１２ |