GATE CS 2021 Set 2 Q34 — Data Link Layer: Framing, Error Detection, MAC, Ethernet Bridging

To find the CRC check bits $c_2c_1c_0$, we perform modulo-2 division of the appended message by the generator polynomial.

Step 1: Represent the Generator Polynomial in Binary

The generator polynomial is given by: $$G(X) = X^3 + X + 1 = 1\cdot X^3 + 0\cdot X^2 + 1\cdot X^1 + 1\cdot X^0$$ In binary, this corresponds to the divisor: $1011$ (degree $n = 3$).

Step 2: Append Zeros to the Message

The message is $M = 11000$. Since the degree of the generator polynomial is $3$, we append $3$ zeros to the message: $$\text{Appended Message} = 11000000$$

Step 3: Perform Modulo-2 Division

We divide $11000000$ by $1011$ using modulo-2 division (XOR operation):

      111100  (Quotient)
    -----------
1011 | 11000000
       1011
       ----
        1110
        1011
        ----
         1010
         1011
         ----
          0010
          0000
          ----
           0100
           0000
           ----
            100  (Remainder)

The remainder of the division is $100$.

Conclusion

The check bits $c_2c_1c_0$ are the remainder, which is $100$.

Thus, the correct option is C.