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 message with (generator length minus 1) zeros, then perform modulo-2 (XOR) division by the generator; the final remainder, of that same length, is the CRC bits appended before transmission.

Answer 1

The Correct Option is D

Step 1: Understanding the Question.
We are given a 9-bit message, 110001011, and a 4-bit generator (divisor), 1001. In CRC, we first append \(r\) zero bits to the message, where \(r\) is one less than the number of bits in the generator, then divide by the generator using modulo-2 (XOR) division. The remainder of that division, which will be \(r\) bits long, is the pattern that actually gets appended to the original message before sending it.

Step 2: Find how many zero bits to append.
The generator 1001 has 4 bits, so
\[ r = 4 - 1 = 3 \]
We append 3 zero bits to the message:
\[ 110001011 \to 110001011000 \]
This gives a 12-bit dividend.

Step 3: Perform modulo-2 division.
We divide 110001011000 by 1001 using XOR at every step instead of ordinary subtraction. Take the leftmost 4 bits, 1100, and XOR with 1001 since the leading bit is 1:
\[ 1100 \oplus 1001 = 0101 \]

Step 4: Keep bringing down the next bit and repeating.
Drop the leading 0 and bring down the next dividend bit (0), giving 1010. Leading bit is 1, so XOR with 1001:
\[ 1010 \oplus 1001 = 0011 \]
Bring down the next bit (1), giving 0111. Leading bit is 0, so no XOR, just shift: bring down the next bit (0), giving 1110. Leading bit is 1, so XOR with 1001:
\[ 1110 \oplus 1001 = 0111 \]
Bring down the next bit (1), giving 1111. Leading bit is 1, so XOR with 1001:
\[ 1111 \oplus 1001 = 0110 \]
Bring down the next bit (1), giving 1101. Leading bit is 1, so XOR with 1001:
\[ 1101 \oplus 1001 = 0100 \]
Bring down the next bit (0), giving 1000. Leading bit is 1, so XOR with 1001:
\[ 1000 \oplus 1001 = 0001 \]
Bring down the next bit (0), giving 0010. Leading bit is 0, no XOR, shift: bring down the last bit (0), giving 0100. Leading bit is 0, no XOR needed, and there are no more bits left to bring down.

Step 5: Read off the remainder.
All 12 bits of the dividend have now been used up. The final 4-bit register is 0100. Since the generator has 4 bits, the remainder always has 3 bits, namely the last 3 bits of this final register:
\[ 100 \]

Step 6: Final conclusion.
The remainder bit pattern appended to the data bits before transmission is
\[ \boxed{100} \]