GATE CS 2009 Q48 — Data Link Layer: Framing, Error Detection, MAC, Ethernet Bridging

To detect an odd number of bit errors, the generator polynomial $G(x)$ must not divide any error polynomial $E(x)$ that has an odd number of terms.

Let $E(x)$ be the error polynomial representing the bit errors. An error is undetected if and only if $E(x)$ is divisible by $G(x)$.

In modulo-2 arithmetic (GF(2)):

• Evaluating any polynomial $E(x)$ at $x = 1$ yields the sum of its coefficients modulo 2.
• Since each non-zero term in $E(x)$ corresponds to a bit in error, a polynomial with an odd number of terms will satisfy: $$E(1) = 1 \pmod 2$$

If we choose $G(x)$ such that $(1 + x)$ is a factor of $G(x)$, then any polynomial $E(x)$ divisible by $G(x)$ must also be divisible by $(1 + x)$.

By the Factor Theorem, a polynomial $E(x)$ is divisible by $(1 + x)$ if and only if: $$E(1) = 0 \pmod 2$$

Since $E(1) = 1 \neq 0$ for any odd number of errors, $E(x)$ can never be divisible by $(1 + x)$, and consequently, it can never be divisible by $G(x)$. Thus, all odd number of bit errors are guaranteed to be detected.

Therefore, the correct option is C.