Let G(x) be the generator polynomial used for CRC checking. What is the…
2009
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
- A.
G(x) contains more than two terms
- B.
G(x) does not divide 1+x^k, for any k not exceeding the frame length
- C.
1+x is a factor of G(x)
- D.
G(x) has an odd number of terms.
Attempted by 216 students.
Show answer & explanation
Correct answer: C
Correct answer: 1+x is a factor of G(x).
Key idea: An error pattern with an odd number of bit flips corresponds to an error polynomial E(x) whose evaluation at x=1 equals 1 (the sum of its coefficients is odd). If the generator polynomial G(x) has (1+x) as a factor, then G(1)=0. For an error to go undetected the error polynomial must be divisible by G(x), which would imply E(1)=0. Because E(1)=1 for odd-weight errors, such an E(x) cannot be divisible by G(x), so every odd number of bit errors will be detected.
Step 1: Evaluate polynomials at x=1. For any polynomial P(x) over GF(2), P(1) is the parity (sum modulo 2) of its coefficients.
Step 2: If G(x) has (1+x) as a factor, then G(1)=0 (even parity of coefficients). Any odd-weight error polynomial E(x) has E(1)=1, so E(x) cannot be a multiple of G(x).
Equivalent check: G(x) being divisible by 1+x is equivalent to G(x) having an even number of nonzero coefficients (even parity).
Therefore, the required condition to detect every odd number of bit errors is that 1+x is a factor of the generator polynomial G(x).