Question

Consider the transmission of data bits 110001011 over a link that uses Cyclic
Redundancy Check (CRC) code for error detection. If the generator bit pattern is
given to be 1001, which one of the following options shows the remainder bit
pattern appended to the data bits before transmission?

• A. 011
• B. 101
• C. 000
• D. 100

Hint:

Pad the data with (generator length minus 1) zeros, then divide by the generator using modulo-2 (XOR) division; the last few bits of the final result form the CRC remainder.

Answer 1

The Correct Option is D

An alternate way to see this is through polynomial representation over GF(2), instead of doing the XOR division bit by bit.

Step 1: Write the data bits 110001011 as a polynomial: \(M(x) = x^8 + x^7 + x^3 + x + 1\).

Step 2: The generator 1001 corresponds to \(G(x) = x^3 + 1\), which has degree 3. Multiply the data polynomial by \(x^3\) to make room for the remainder bits: \(x^3 M(x) = x^{11} + x^{10} + x^6 + x^4 + x^3\).

Step 3: Divide \(x^3 M(x)\) by \(G(x)\) using modulo-2 polynomial division, where subtraction of coefficients behaves exactly like XOR since we work over GF(2).

Carrying out the successive term-by-term reductions (dividing the highest remaining power each time and cancelling using \(G(x)\)) leaves a final remainder polynomial of degree less than 3. Working through the full reduction gives a remainder of \(x^2\), which corresponds to the 3-bit pattern \(100\).

Step 4: This agrees exactly with the direct bit-wise XOR division method, confirming that the CRC remainder to be appended is \(100\).

So the transmitted remainder bits are \(100\), matching option (D).