GATE CS Mastery
Cheat sheets

GATE CS 2026 Set 2 · Computer Networks

Question 43

MCQ2 marksWrong answer: −2/3Easy (estimate)

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?

Choose one option
Official answer and solution
Official answer
D
From
Official GATE 2026 answer key

Solution

Append 3 zeros to the data bits 110001011 (making 110001011000) and divide by generator 1001 using modulo-2 (XOR) polynomial division.

The generator polynomial is G(x)=x3+1G(x) = x^3 + 1 (1001, degree r=3r = 3). Appending 3 zeros to 110001011 gives 110001011000, or in polynomial form:

M(x)⋅x3=x11+x10+x6+x4+x3M(x) \cdot x^3 = x^{11} + x^{10} + x^6 + x^4 + x^3

Since x3≡1(modx3+1)x^3 \equiv 1 \pmod{x^3 + 1}, we reduce each power of xx modulo 33:

  • x11=(x3)3x2≡x2x^{11} = (x^3)^3 x^2 \equiv x^2
  • x10=(x3)3x≡xx^{10} = (x^3)^3 x \equiv x
  • x6=(x3)2≡1x^6 = (x^3)^2 \equiv 1
  • x4=x3⋅x≡xx^4 = x^3 \cdot x \equiv x
  • x3≡1x^3 \equiv 1

Summing over GF(2)\text{GF}(2) (XOR):

R(x)=x2+(x⊕x)+(1⊕1)=x2R(x) = x^2 + (x \oplus x) + (1 \oplus 1) = x^2

In 3-bit binary, x2=1⋅x2+0⋅x+0⋅1=100x^2 = 1 \cdot x^2 + 0 \cdot x + 0 \cdot 1 = \texttt{100}.

Final answer

Option (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question
43 of 65
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.