GATE CS 2017 Set 1 Q.32 (CS Q.32): Data Link Layer: Framing, Error Detection and Sliding Window

A computer network uses polynomials over $\text{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

01011011010

01011011011

01011011101

01011011100

Official answer and solution

Official answer: C
From: Official GATE 2017 answer key

Solution

Perform modulo-2 polynomial division on the zero-padded message using the generator polynomial to determine the transmitted codeword.

The generator polynomial is $G(x) = x^3 + x + 1$ , which corresponds to the binary divisor $1011$ (degree $r = 3$ ).

The information message is $M = 01011011$ (8 bits). To generate the CRC check bits, append $r = 3$ zeros to $M$ :

M \cdot 2^3 = 01011011000

Dropping the leading zero gives the 10-bit sequence $1011011000$ to be divided by $1011$ using modulo-2 division (bitwise XOR).

Perform modulo-2 division step by step:

Dividend: 1011011000
XOR with 1011 aligned at bit 1:
1011011000 $\oplus$ 1011000000 = 0000011000
Bring down remaining bits to align with the first non-zero bit:
Align 1011 at bit 6: 1100 $\oplus$ 1011 = 0111
Bring down next bit: 1110 $\oplus$ 1011 = 0101

The 3-bit remainder is $101$ . Appending this remainder to the original 8-bit message yields the transmitted codeword:

01011011101

This matches Option C.

Final answer

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

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 32 of 65, printed as CS Q.32
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.

Question

Solution

Source