Let G(x) be the generator polynomial used for CRC checking. The necessary and…
2017
Let G(x) be the generator polynomial used for CRC checking. The necessary and sufficient condition for G(x) to detect all odd-numbered bit errors is:
- A.
\((1 + x)\)is factor of\(G(x)\) - B.
\((1 + 2x)\)is factor of\(G(x)\) - C.
\((1 + x^2)\)is factor of\(G(x)\) - D.
\(x\)is factor of\(G(x)\)
Attempted by 361 students.
Show answer & explanation
Correct answer: A
Answer: (1 + x) is a factor of G(x).
Reason: Represent an error pattern by its error polynomial E(x). Evaluating at x = 1 gives E(1) as the sum of the error bits modulo 2, so E(1) = 1 when there is an odd number of bit errors. If G(x) has (1 + x) as a factor, then G(1) = 0. Any polynomial divisible by G(x) is also divisible by (1 + x), and therefore evaluates to 0 at x = 1. Hence an odd-weight error polynomial cannot be divisible by G(x), so CRC division leaves a nonzero remainder and detects the error.
Option C is stronger than required, not the necessary-and-sufficient condition: over GF(2), 1 + x^2 = (1 + x)^2, so it implies the correct factor but adds an unnecessary extra requirement. Option D, x as a factor, relates to G(0) = 0 and does not ensure odd-error detection.