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

In Cyclic Redundancy Check (CRC), the number of redundant bits (zeros) appended to the data bits before division is $n = k - 1$, where $k$ is the length of the generator bit pattern.

Given:

• Data bits: $110001011$
• Generator bit pattern: $1001$ (length $k = 4$)
• Number of redundant bits to append: $4 - 1 = 3$

Appending three $0$s to the data bits gives the dividend: $110001011000$. We now perform modulo-2 division (using XOR operations) by the generator $1001$:

       1101011100  (Quotient)
     _____________
1001 | 110001011000
       1001
       ----
       01010
        1001
        ----
        00111
         0000
         ----
         01110
          1001
          ----
          01111
           1001
           ----
           01101
            1001
            ----
            01000
             1001
             ----
             00010
              0000
              ----
              00100  <-- Remainder (3 bits)

The 3-bit remainder obtained is $100$. Therefore, the bit pattern appended to the data bits is $100$.