Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Checking the error detection capabilities of CRC polynomials

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?

like image 240
Silicomancer Avatar asked Aug 19 '16 22:08

Silicomancer


People also ask

How CRC will detect error in a program?

CRC or Cyclic Redundancy Check is a method of detecting accidental changes/errors in the communication channel. CRC uses Generator Polynomial which is available on both sender and receiver side. An example generator polynomial is of the form like x3 + x + 1. This generator polynomial represents key 1011.

What type of errors can CRC detect?

In this case, CRC detects the following errors: All burst errors of length less than or equal to n. All burst errors affecting an odd number of bits. All burst errors of length equal to n + 1 with probability (2n-1 − l)/2.

Which error detection is using polynomials?

CRC is a very effective and popular error detection technique. The error detection capabilities of CRC depend on the chosen generator polynomial. CRC has capacity to detect all single-bit errors. CRC has capacity to detect all double-bit errors (three 1's).


3 Answers

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.

like image 51
Mark Adler Avatar answered Sep 28 '22 15:09

Mark Adler


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]

like image 39
Burhanuddin Avatar answered Sep 28 '22 15:09

Burhanuddin


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

like image 20
henry sneed Avatar answered Sep 28 '22 17:09

henry sneed