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:
Detection of a single bit error: All CRCs can do this since this only requires a CRC width >= 1.
Detection of burst errors: All CRCs can detect burst errors up to a size that equals their width.
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.
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:
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?
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.
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.
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).
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.
A CRC of n-bit for g(x) = (x+l)*p(x) can detect:
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 (2^(n-1) − l)/2^n − 1
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]
With regard to the above question, l refers to the length of the burst error
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With