平成18年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
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で表すと、
以下の通りとなる。
 O XOR 0 = 0
 1 XOR 1 = 0
 O 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ビット目が誤って
101100となったとき、
・追加する3ビットの1ビット目が1であるため、ビット1、2、3のうちどれか
 1つが誤りであることが判る。
・追加する3ビットの2ビット目が0であるため、2、3、4には誤りがない
 ことが判る。
・追加する3ビットの3ビット目が0であるため、1、2、4のうちどれか
 1つが誤りであることが判る。
つまり誤りは1ビット目であることが判る。

次に2ビット目が誤って
01100となった時、
・追加する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ビット目が誤って
010100となった場合、
・追加する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ビットの符号誤り訂正が可能である。


EXCELのマクロのご相談なら ファーストマクロ 



W−10 目次 W−12
ファーストマクロ TOPページ