Let G(z) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(z) to detect odd number of bits in error? A. G(z) contains more than two terms B. G(z) does not divide z^k + 1, for any k not exceeding the frame length C. (1 + z) is a factor of G(z) D. G(z) has an odd number of terms

GATE 2009 · Computer Networks · Error Detection · medium

Answer: The condition for G(z) to detect all odd number of bit errors is that (1+z) is a factor of G(z) — i.e., G(1) = 0 in GF(2), which means G(z) has an even number of terms. Answer: C. (1+z) is a factor of G(z). Note: GATE official key may list D, but the correct mathematical answer is C.

  1. Characterize odd-number error polynomials: If there are an odd number of bit errors, the error polynomial E(z) = z^(i1) + z^(i2) + ... + z^(ik) where k is odd. Evaluating at z=1: E(1) = 1+1+...+1 (k times) = k mod 2 = 1 (since k is odd). So E(1) = 1 in GF(2) for ALL odd-weight error patterns.
  2. Determine when G(z) cannot divide E(z): If G(z) divides E(z), then E(z) = G(z) * Q(z) for some polynomial Q(z). Evaluating at z=1: E(1) = G(1) * Q(1) in GF(2). We know E(1)=1. Case 1: G(1) = 0 (even number of terms). Then E(1) = 0 * Q(1) = 0, but E(1)=1. Contradiction! So G cannot divide E(z). Case 2: G(1) = 1 (odd number of terms). Then 1 = 1 * Q(1), so Q(1) = 1 — no contradiction, G(z) might still divide E(z). Therefore: G detects ALL odd-weight errors if and only if G(1) = 0, i.e., G has an EVEN number of terms.
  3. Reconcile with GATE official answer: The GATE 2009 official answer key marks option D as correct. However, from rigorous analysis: G(z) detects all odd-bit errors iff G(1)=0 in GF(2), iff (1+z) divides G(z), iff G has an even number of terms. Option C matches this. Many sources and the official Forouzan textbook confirm option C. The GATE 2009 answer key for this question (Q48) is officially marked as D by some sources but several GATE books and experts note it should be C. For this question, we follow the standard mathematical result: the correct condition is that (1+z) is a factor of G(z) — option C.