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. 001
• B. 100
• C. 111
• D. 011

Hint:

In CRC XOR division, you only perform the XOR operation if the leftmost bit of the current dividend is 1. If it is 0, you simply shift to the next bit.

Answer 1

The Correct Option is B

Step 1: Understanding the Concept:
CRC uses polynomial division where bits are treated as coefficients. To find the CRC remainder, we append $(n-1)$ zeros to the data (where $n$ is the length of the generator) and perform binary (XOR) division.
Step 2: Key Formula or Approach:
Generator = 1001 (length 4).
Append $4-1 = 3$ zeros to the data bits: 110001011000.
Step 3: Detailed Explanation:
Perform binary division (XOR subtraction):
\[ \begin{array}{l} 110001011000 \div 1001
1100 \oplus 1001 = 0101 \rightarrow \text{bring down } 0: 1010
1010 \oplus 1001 = 0011 \rightarrow \text{bring down } 1: 0111 \text{ (skip leading 0)} \rightarrow \text{bring down } 0: 1110
1110 \oplus 1001 = 0111 \rightarrow \text{bring down } 1: 1111
1111 \oplus 1001 = 0110 \rightarrow \text{bring down } 1: 1101
1101 \oplus 1001 = 0100 \rightarrow \text{bring down } 0: 1000
1000 \oplus 1001 = 0001 \rightarrow \text{bring down } 0: 0010 \rightarrow \text{bring down } 0: 0100 \text{ (no more bits)}
\text{Remainder } = 100 \end{array} \] Step 4: Final Answer:
The remainder is 100, which is option (B).