GATE 2017 CS (CS1) – Question 42
A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses $x^3 + x + 1$ as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) 01011011101
Explanation
Message $m=01011011$, generator $x^3+x+1\ (=1011)$. The check bits are the remainder of $m(x)\cdot x^3$ divided by the generator, over GF(2).
$m(x)=x^6+x^4+x^3+x+1$, so $m(x)x^3=x^9+x^7+x^6+x^4+x^3$.
Reduce using $x^3\equiv x+1$:
- $x^4=x^2+x$
- $x^5=x^2+x+1$
- $x^6=x^2+1$
- $x^7=1$
- $x^9=x^2$
Sum: $x^2+1+(x^2+1)+(x^2+x)+(x+1)=x^2+1$ (adding mod 2: three $x^2$ give $x^2$, two $x$ cancel, three 1's give 1).
Remainder $=x^2+1=101$. The transmitted word is the message followed by the remainder: $01011011\,101$ = **01011011101** (option C).
More Data Link Layer: Error Detection, Medium Access Control, Flow Control questions
- GATE 2017 CS (CS1) Q55
- GATE 2014 CS (CS1) Q34
- GATE 2014 CS (CS1) Q36
- GATE 2014 CS (CS1) Q38
- GATE 2014 CS (CS3) Q34
- GATE 2016 CS (CS2) Q34
All Data Link Layer: Error Detection, Medium Access Control, Flow Control questions →