情報理論と符号の基礎
データ 1101 に、生成多項式 x³ + x + 1(ビット列 1011)のCRCの検査ビット3ビットを付ける。検査ビットは、データの後ろに0を3つ付けた 1101000 を 1011 で割った余りで、割り算では引き算の代わりに排他的論理和を使う。検査ビットはどれか。
- A001
- B101
- C110
答えと解説を見る
正解：A. 001
1101000 を 1011 で割ります。先頭の 1101 と 1011 の排他的論理和は 0110、次のビットを下ろした 1100 と 1011 の排他的論理和は 0111、1110 と 1011 では 0101、最後に 1010 と 1011 では 0001 となり、余りは 001 です。送るのは 1101001 で、受信側は 1011 で割った余りが0なら、誤りがないと判断します。
- A. 正しい。排他的論理和による割り算の余りは 001 で、送る符号語は 1101001 です。
- B. 101 は、1101000 と 1011 を通常の2進数の104と11として割った余りの5です。CRCでは、繰り下がりのない、排他的論理和による割り算を使います。
- C. 110 は、0を3つ付けずに 1101 を 1011 で割った余りです。検査ビットの数だけ0を付けてから割ります。