What is the CRC remainder for data 110001011 with generator 1001 in GATE CS 2026 Set-2 Q43?

The remainder is 100 (Option D). Appending 3 zeros gives 110001011000. Performing modulo-2 XOR division by 1001 through 8 steps yields a final register value of 0100, making the 3-bit remainder 100. This is appended to the original data before transmission.

How does CRC error detection work?

CRC works by treating data as a polynomial and dividing it by a generator polynomial using modulo-2 arithmetic (XOR, no carries). The sender appends (degree of generator) zeros to the data, divides by the generator, and appends the remainder to the original data. The receiver divides the received message by the same generator — if remainder is zero, no error is detected.

Why are 3 zeros appended to the data before CRC division?

The number of zeros appended equals the degree of the generator polynomial. Generator 1001 has degree 3 (highest power of x is x^3), so 3 zeros are appended. This ensures the remainder after division is exactly 3 bits long, which is then substituted for the appended zeros before transmission.

CRC Remainder 110001011 Generator 1001 | GATE CS 2026 Set-2 Q43

Computer Sciences > GATE 2026 SET-2 > Computer Networks

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?

011

101

000

100

Correct : d

The correct answer is Option D — 100.
CRC setup: Generator = 1001 (degree 3), so append 3 zeros to the data. Message with zeros = 110001011000 (12 bits). Divide this by 1001 using modulo-2 (XOR) division.
XOR division step by step (each step: if MSB=1 XOR with 1001, else XOR with 0000, bring down next bit):
1100 XOR 1001 = 0101, bring down 0 → 1010
1010 XOR 1001 = 0011, bring down 1 → 0111
0111 XOR 0000 = 0111, bring down 0 → 1110
1110 XOR 1001 = 0111, bring down 1 → 1111
1111 XOR 1001 = 0110, bring down 1 → 1101
1101 XOR 1001 = 0100, bring down 0 → 1000
1000 XOR 1001 = 0001, bring down 0 → 0010
0010 XOR 0000 = 0010, bring down 0 → 0100
Final remainder = 100. This 3-bit remainder is appended to the original data before transmission.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev