GATE CS 2021 Set 2 Q.44 (CS Q.34): Data Link Layer: Framing, Error Detection and Sliding Window

Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial $X^3 + X + 1$ . Suppose the message $m_4 m_3 m_2 m_1 m_0 = 11000$ is to be transmitted. Check bits $c_2 c_1 c_0$ are appended at the end of the message by the transmitter using the above CRC scheme. The transmitted bit string is denoted by $m_4 m_3 m_2 m_1 m_0 c_2 c_1 c_0$ . The value of the checkbit sequence $c_2 c_1 c_0$ is

101

110

100

111

Official answer and solution

Official answer: C
From: Official GATE 2021 answer key

Solution

Perform polynomial division using modulo-2 arithmetic (XOR) to determine the CRC check bits.

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

The message is $M = 11000$ . To determine $k = 3$ check bits, append 3 zeros to the message:

\text{Dividend} = 11000000

Perform modulo-2 long division:

        11111
1011 ) 11000000
       1011
       ----
        1110
        1011
        ----
         1010
         1011
         ----
          00100 (bring down 0, 0)
          Remainder = 100

Detailed XOR steps:

$1100 \oplus 1011 = 0111$ , bring down $0 \to 1110$
$1110 \oplus 1011 = 0101$ , bring down $0 \to 1010$
$1010 \oplus 1011 = 0001$ , bring down $0 \to 010$
bring down $0 \to 100$

The remainder is the 3-bit check sequence $c_2 c_1 c_0 = 100$ , matching 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 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 44 of 65, printed as CS Q.34
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