0

I have read some papers that the probability of a CRC code being undetected is not depended on the message size and it is only related to CRC bits. 2^(-32) for 32bit CRC

My questions are:

  1. why we need wider CRCs? even if we plan to use a 16-bit CRC over the entire file, the probability of having an undetected error is almost zero and we can detect all the errors in the file.
  2. What is the need that when using 32bit CRC, we need to have a file size smaller than 2 ^ 32 (512 MB) does it mean that if we have a burst error causes more than 512 MB of file changes, the CRC can't detect it?
Arash
  • 225
  • 1
  • 11

1 Answers1

2

  1. The probability of detecting a random pattern of errors for a 16 bit CRC is about 2^(-16) (1/65536). A 32 bit CRC reduces this to 2^(-32) (1 / 4 billion).

  2. All CRCs will detect a single bit error no matter how large the file is. If the goal is a 32 bit CRC that is guaranteed to detect any 2 bit error pattern, the maximum file size + CRC is 2^32-1 bits. If the size including CRC is >= 2^32 bits, then if a 2 bit error occurs at bit[i+0] and bit[i+2^32-1], the error will not be detected. If the goal is a CRC that detects all 3 bit errors, which is normally done by having at least 2 prime polynomial factors in the CRC, one of them being (x+1), which will detect any odd number of bit errors, and a 31 bit factor which will detect any 2 bit error if file size + CRC is <= 2^31-1 bits. As the number of errors that a CRC is guaranteed to correct increases, the maximum file size + CRC decrease. Take a look at the table in "CRC Zoo". It is a list of CRC polynomials, followed by the maximum number of data bits (not including the CRC) for detecting all 2, 3, 4, 5, ... bit errors (Hamming distance 3, 4, 5, 6, ...).

https://users.ece.cmu.edu/~koopman/crc/crc32.html

Although not asked, another issue is the probability of transmitted or written data having no errors. This depends on the error rate and the size of the data. If the error rate for a byte is e, then the probability of zero errors is having no errors in all bytes, or (1 - e)^n, where n is the number of bytes. To deal with situations where the probability of errors is significant, then some type of error correction code is used to reduce the probability of an uncorrectable error.

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • If all CRCs will detect a single bit error, Why do we have the undetected error probability? – Arash Sep 26 '20 at 00:19
  • 1
    @Arash - undetected error probability is for 2 or more bit errors. – rcgldr Sep 26 '20 at 02:51
  • I have a quick question, How does the probability of undetected error vary as a function of link type? – Arash Nov 02 '20 at 00:25
  • @Arash - I don't understand what you mean by "link type". – rcgldr Nov 02 '20 at 04:19
  • 1
    @Arash - Other than the relatively short message lengths mentioned in the "CRC Zoo" link, the probability of undetected error is about 1/(2^c), where *c* is the number of CRC bits. – rcgldr Nov 02 '20 at 07:40
  • I'm aware that 64-bit-CRC polynomials are scarce and difficult to find. I was wondering if you were aware of any papers or studies that discussed why this is the case. (Why is it so difficult to find one?) – Arash Mar 17 '21 at 07:16
  • As a result, there are a limited number of polynomials (even with the ability to detect less than 2-bit errors), am I right? There are only 5 polynomials in the link, `0xd6c9e91aca649ad4, 0x800000000000000d, 0x800000000000002b, 0xa17870f5d4f51b49, 0x8000000000000078` . – Arash Mar 18 '21 at 00:00
  • 1
    @Arash - you should probably post this as a separate question, since it is a different topic than the question above. – rcgldr Mar 18 '21 at 07:51
  • 1
    @Arash - short version of answer, it's not feasible to run 2^64 loops on a computer, so they start with some initial value and do checks that can take millions to billions of loops. Also those CRC values are Koopman's format, look at the 2nd value in each row for the actual CRC polynomial. This should be posted as a separate question, since it is not related to this undetected error probability question. – rcgldr Mar 18 '21 at 16:41