Mathematics of CRC - Error Detection Strength

Error Detection Strength

The error-detection ability of a CRC depends on the degree of its key polynomial and on the specific key polynomial used. The "error polynomial" is the symmetric difference of the received message codeword and the correct message codeword. An error will go undetected by a CRC algorithm if and only if the error polynomial is divisible by the CRC polynomial.

• Because a CRC is based on division, no polynomial can detect errors consisting of a string of zeroes prepended to the data, or of missing leading zeroes. However, see Variations.
• All single bit errors will be detected by any polynomial with at least two terms with non-zero coefficients. The error polynomial is, and is divisible only by polynomials where .
• All two bit errors separated by a distance less than the order of the primitive polynomial which is a factor of the generator polynomial will be detected. The error polynomial in the two bit case is . As noted above, the term will not be divisible by the CRC polynomial, which leaves the term. By definition, the smallest value of such that a polynomial divides is the polynomial's order or exponent. The polynomials with the largest order are called primitive polynomials, and for polynomials of degree with binary coefficients, have order .
• All errors in an odd number of bits will be detected by a polynomial which is a multiple of . This is equivalent to the polynomial having an even number of terms with non-zero coefficients. This capacity assumes that the generator polynomial is the product of and a primitive polynomial of degree since all primitive polynomials except have an odd number of non-zero coefficients.
• All burst errors of length will be detected by any polynomial of degree or greater which has a non-zero term.

(As an aside, there is never reason to use a polynomial with a zero term. Recall that a CRC is the remainder of the message polynomial times x^n divided by the CRC polynomial. A polynomial with a zero term always has as a factor. So if is the original CRC polynomial and, then

That is, the CRC of any message with the polynomial is the same as that of the same message with the polynomial with a zero appended. It is just a waste of a bit.)

The combination of these factors means that good CRC polynomials are often primitive polynomials (which have the best 2-bit error detection) or primitive polynomials of degree, multiplied by (which detects all odd numbers of bit errors, and has half the two-bit error detection ability of a primitive polynomial of degree ).