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: Set up the padded message.
CRC works by treating both the message and the generator as bit patterns and dividing one by the other using XOR instead of ordinary subtraction. The generator $1001$ has $4$ bits, so we need $3$ check bits, which means padding the message with $3$ zeros before dividing:
$110001011000$

Step 2: Slide a 4-bit window across the padded message, XOR-ing with the generator whenever the front bit is 1.
Start with the first 4 bits, $1100$. The front bit is $1$, so XOR with $1001$:
$1100 \to 0101$
Shift in the next bit ($0$): window becomes $1010$; front bit $1$, so XOR: $1010\to0011$
Shift in the next bit ($1$): window becomes $0111$; front bit $0$, so no XOR
Shift in the next bit ($0$): window becomes $1110$; front bit $1$, so XOR: $1110\to0111$
Shift in the next bit ($1$): window becomes $1111$; front bit $1$, so XOR: $1111\to0110$
Shift in the next bit ($1$): window becomes $1101$; front bit $1$, so XOR: $1101\to0100$
Shift in the next bit ($0$): window becomes $1000$; front bit $1$, so XOR: $1000\to0001$
Shift in the next bit ($0$): window becomes $0010$; front bit $0$, so no XOR
Shift in the last bit ($0$): window becomes $0100$; front bit $0$, so no XOR, and no bits remain

Step 3: Read the remainder.
All $9$ message bits plus the $3$ padding zeros have now been fed through the window, and this window always ends up $4$ bits wide, one bit wider than the true remainder. The last $3$ bits of the final window are the CRC remainder, since a $4$-bit generator always leaves exactly a $3$-bit remainder:
\[ \boxed{100} \]
This 3-bit pattern, $100$, is what gets tacked onto the end of the original 9-bit message before it is sent over the link.