GATE 2026 CS2 Q.43: solution and answer

GATE 2026 · CS2Q.43 · 2 marks · MCQ

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The CRC remainder appended to the data is 100, which is option (D).

Official answer: DSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

The generator $1001$ is $x^{3} + 1$ , of degree 3, so append 3 zeros to the data: $110001011000$ (12 bits).
Divide $110001011000$ by $1001$ using modulo-2 (XOR) division. Take the first four bits: $1100 \oplus 1001 = 0101$ , partial remainder $101$ .
Bring down bit 5 (0): $1010 \oplus 1001 = 0011$ , partial remainder $011$ .
Bring down bit 6 (1): $0111$ has leading bit 0, so no XOR; partial remainder $111$ . Bring down bit 7 (0): $1110 \oplus 1001 = 0111$ , partial remainder $111$ .
Bring down bit 8 (1): $1111 \oplus 1001 = 0110$ , partial remainder $110$ . Bring down bit 9 (1): $1101 \oplus 1001 = 0100$ , partial remainder $100$ .
Bring down bit 10 (0): $1000 \oplus 1001 = 0001$ , partial remainder $001$ . Bring down bit 11 (0): $0010$ has leading bit 0, partial remainder $010$ .
Bring down bit 12 (0): $0100$ has leading bit 0, so the final remainder is $100$ .
Cross-check with polynomials: the shifted data is $x^{11} + x^{10} + x^{6} + x^{4} + x^{3}$ . Since $x^{3} \equiv 1 (mod x^{3} + 1)$ , this reduces to $x^{2} + x + 1 + x + 1 = x^{2}$ , which is $100$ .
The remainder $100$ is appended, so the transmitted frame is $110001011100$ . This is option (D).

KEY IDEA

A generator of degree r gives an r-bit remainder. Append r zeros to the data, divide by the generator using modulo-2 (XOR) division, and the remainder is the CRC. With $1001 = x^{3} + 1$ you can also use $x^{3} \equiv 1$ to reduce the shifted data polynomial directly.

WATCH OUT FOR

Forgetting to append 3 zeros before dividing, or skipping a bit while bringing bits down. Another slip is XOR-ing when the leading bit of the partial remainder is 0, when it should be shifted with no XOR.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 3 Data link & MAC questions, with notes

GATE 2026 CS2 Q.43: solution and answer

Answer and solution

More Data link & MAC questions