GATE 2026 CS (CS2) – Question 43
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?
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
- GATE 2024 CS (CS2) Q23
- GATE 2024 CS (CS2) Q55
- GATE 2021 CS (CS1) Q18
- GATE 2021 CS (CS1) Q39
- GATE 2019 CS Q39
- GATE 2018 CS Q65
All Data Link Layer: Error Detection, Medium Access Control, Flow Control questions →