Let G(x) be the generator polynomial used for CRC checking. The condition that…

Answer: The generator polynomial must have (x+1) as a factor.

Reasoning:

• Represent any pattern of bit errors by an error polynomial E(x) whose nonzero terms correspond to bit positions flipped.

• Evaluating a polynomial at x=1 gives the sum of its coefficients modulo 2. If the error pattern has an odd number of flipped bits, then E(1)=1.

• If the generator polynomial G(x) has (x+1) as a factor, then G(1)=0 and every multiple of G(x) also evaluates to zero at x=1.

• For an error to go undetected, E(x) would have to be a multiple of G(x). But a multiple of G(x) evaluates to 0 at x=1, while an odd-weight error has E(1)=1, so E(x) cannot be a multiple of G(x). Therefore the error produces a nonzero remainder and will be detected.

Additional note on equivalent polynomials in GF(2):

• In GF(2), subtraction equals addition, so (x−1) is the same as (x+1).

• x^2+1 equals (x+1)^2 in GF(2), and 1−x^2 equals x^2+1, so these polynomials also contain (x+1) as a factor and therefore also detect odd-weight errors.