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

To detect transmission errors using CRC, the transmitter appends a remainder (the Frame Check Sequence) obtained by dividing the data bits, padded with zeros equal to the degree of the generator, by the generator using modulo-2 (XOR) division.

Step 1: Identify the degree of the generator. Generator = 1001 has 4 bits, so its degree is \(r = 3\). Append \(r = 3\) zeros to the data before dividing.

Data = 110001011, Padded data = 110001011000 (12 bits)

Step 2: Perform modulo-2 (XOR) division of 110001011000 by 1001. XOR is applied whenever the leading bit of the current window is 1.

1100 XOR 1001 = 0101
bring next bit -> 1010, XOR 1001 = 0011
bring next bit -> 0111, leading bit 0, no XOR
bring next bit -> 1110, XOR 1001 = 0111
bring next bit -> 1111, XOR 1001 = 0110
bring next bit -> 1101, XOR 1001 = 0100
bring next bit -> 1000, XOR 1001 = 0001
bring next bit -> 0010, leading bit 0, no XOR
bring next bit -> 0100, leading bit 0, no XOR

Step 3: After all 12 bits are processed, the last 3 bits of the final result give the remainder: \(100\).

Step 4: This 3-bit remainder is appended to the data before transmission, giving the transmitted frame 110001011100.

Hence the correct remainder bit pattern is \(\boxed{100}\), which is option (D).