GATE CS 2007 Q68 — Data Link Layer: Framing, Error Detection, MAC, Ethernet Bridging

To find the transmitted message, we use Cyclic Redundancy Check (CRC) modulo-2 division:

1. Identify the Divisor: The generator polynomial is $G(x) = x^3 + 1$, which corresponds to the binary divisor $1001$ (since $1\cdot x^3 + 0\cdot x^2 + 0\cdot x^1 + 1\cdot x^0$).
2. Append Zeros: Since the degree of the polynomial is $3$, we append three $0$s to the message $11001001$, giving the dividend $11001001000$.
3. Perform Modulo-2 Division:

               11010011
            ___________
      1001 | 11001001000
             1001
             ----
              1011
              1001
              ----
               0100
               0000
               ----
                1000
                1001
                ----
                 0011
                 0000
                 ----
                  0110
                  0000
                  ----
                   1100
                   1001
                   ----
                    1010
                    1001
                    ----
                     011  <-- Remainder
       

The remainder is $011$. Replacing the three appended zeros with this remainder gives the transmitted message: $11001001011$.