Checking the error detection capabilities of CRC polynomials

Question

I tried to find out how to calculate the error detection capabilities of arbitrary CRC polynomials.

I know that there are various error detection capabilities that may (or may not) apply to an arbitrary polynomial:

1. Detection of a single bit error: All CRCs can do this since this only requires a CRC width >= 1.

2. Detection of burst errors: All CRCs can detect burst errors up to a size that equals their width.

3. Detection of odd numbers of bit errors: CRC with polynomials with an even number of terms (which means an even number of 1-bits in the full binary polynomial) can do this.

4. Detection of random bit errors (depending from frame size): I have a ready-to-use C algorithm that allows calculating the maximum frame size for given HD and poylnomial. I didn't understood it completely but it works.

Lets assume a 16 bit CRC polynomial x¹⁶+x¹²+x⁵+1 = 0x11021. That polynomial can:

• detect all single bit errors (data size independent).
• detect all burst errors up to 16 bit width (data size independent).
• detect all odd numbers of bit errors (since it has 4 polynomial terms; data size independent).
• detect 3 bit errors (HD4) up to 32571 bit data size.

Is the above correct?

Are there additional CRC error detection capabilities? If yes, how can I check (without deep math knowledge) if an arbitrary CRC polynomial supports them?

Keene

This question is pretty interesting. It might be better for cs.stackexchange.com – Persuader

@Nayuki: You are probably right. First lets see what happens here... – Keene

Answer 1

This paper by Koopman and Chakravarty looks at several measures of CRC performance, describing the measures and the results for many polynomials. In short, the definition of a "good" polynomial depends on the length of the message it is being applied to, which varies by application. The main measures are the Hamming distance, which is the minimum number of bits in the message that you would have to change to get back to the same CRC, and the performance at a prescribed low bit error rate.

Manwell

Answer 2

A CRC of n-bit for g(x) = (x+l)*p(x) can detect:

1. All burst errors of length less than or equal to n.

2. All burst errors affecting an odd number of bits.

3. All burst errors of length equal to n + 1 with probability (2^(n-1) − l)/2^n − 1

4. All burst errors of length greater than n + 1 with probability (2^(n-1) − l)/2^n [the CRC-32 polynomial will detect all burst errors of length greater than 33 with probability (2^32 − l)/2^32; This is equivalent to a 99.99999998% accuracy rate]

Forseti

What is l used in g(x) and probability formulas? Is it maximum or actual message length or something other? – Selfness

Answer 3

With regard to the above question, l refers to the length of the burst error

Staub