本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成18年度 技術士第一次試験問題【専門科目】

W−11

4ビットのデータに3ビットのチェックビットを追加して、1ビットの符号誤り訂正を行いたい。追加する1ビット目はデータの先頭3ビット (ビット1、2、3) の排他的論理和、2ビット目はデータの末尾の3ビット (ビット2、3、4) の排他的論理和とした。 3ビット目として最も適切なものを次の中から選べ。

@ ビット1、4の排他的論理和

A ビット2、4の排他的論理和

B ビット1、2、4の排他的論理和

C ビット1、2、3、4すべての排他的論理和

D どのようにしても、誤り訂正ができない


正解

B


解説

排他的論理和 (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ビットの符号誤り訂正が可能である。

W−10 目次 W−12