The GATE Grind

GATE 2026 CS (CS2) – Question 43

Computer Networks · Data Link Layer: Error Detection, Medium Access Control, Flow Control · 2 marks · Multiple choice

Consider the transmission of data bits `110001011000` over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is `1001`, which one of the following options shows the remainder bit pattern appended to the data bits before transmission?

  1. 011
  2. 101
  3. 000
  4. 100

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) 100

Explanation

**1. Reserve the CRC bits.** Generator 1001 has degree 3, so append three zero bits to the data before division. Divide 110001011000000 by 1001, using XOR rather than subtraction with borrowing.

**2. Interpret the polynomial division.** The data polynomial is $M(x)=x^{11}+x^{10}+x^6+x^4+x^3$ and the generator is $G(x)=x^3+1$. Modulo G over GF(2), x³ = 1. Thus the remainder of $x^3M(x)$ reduces to $x^2+x+1+x+1=x^2$, because equal terms cancel in pairs.

**3. Encode and check the remainder.** Degree-2 polynomial x² is the three-bit remainder **100**, so the answer is **D**. Appending it to the original data produces a polynomial divisible by G. The zero padding must be done before finding the transmitted CRC.

More Data Link Layer: Error Detection, Medium Access Control, Flow Control questions

All Data Link Layer: Error Detection, Medium Access Control, Flow Control questions →