The GATE Grind

GATE 2017 CS (CS1) – Question 42

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

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

  1. 01011011010
  2. 01011011011
  3. 01011011101
  4. 01011011100

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

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