3

It is said that a CRC (Cyclic Redundancy Checksum) can detect burst errors of fewer than r + 1 bits, where r is the degree of the polynomial. Furthermore, a burst of length greater than r + 1 bits is detected with probability 1 – 2-r.

Can someone guide me to the proof of the same?

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
anuja
  • 170
  • 1
  • 2
  • 11
  • I’m voting to close this question because this is a better suited question for [cs.se], which specializes in generic algorithmic questions like this. – Machavity Aug 15 '22 at 17:26

1 Answers1

6

Not quite true. An r-bit CRC will detect all burst patterns of length r+1 except for one pattern, the polynomial itself. See these lecture notes for the proof.

It is simply that for the message to not detect the errors, the CRC polynomial has to divide the error polynomial. If the error polynomial is r bits long, then a degree r+1 polynomial that does not have x as a factor (i.e. has a 1 term) cannot divide a degree r polynomial, and the only r+1 degree polynomial that it can divide is itself. All CRC polynomials have a 1 term.

Your other claim is a property of any r-bit hash that distributes messages with equal probability over all possible r-bit values of the hash, which a CRC does. 2-r is simply the probability that an applied error just so happens to result in the same CRC, for which there are 2r possibilities. It's the same as saying that the chance of rolling the same number you just rolled on a 6-sided die is 1/6.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • Regarding the burst detection weakness... does this mean that when I merge my data at any position using XOR with a full CRC polynomial (e.g. 0x107 for an ATM-8 CRC-8), that I should get the same checksum as before the merge operation? – Silicomancer Nov 13 '18 at 22:25
  • 1
    Yes. That's exactly right. And you can do that as many times as you like, anywhere in the message. There are many other longer bit patterns, called "codewords" that also have that property. The polynomial is the shortest codeword, and there is only one of that length. – Mark Adler Nov 13 '18 at 23:53
  • Just tried it. CRC-8 with ASCII data "AAA" (0..2=0x41,0x41,0x41) gives me checksum 0x63 (see https://crccalc.com/?crc=AAA&method=crc8&datatype=ascii). XORed with 0x107 that data should be "F@A" (0..2=0x46,0x40,0x41) which gives me 0x60 (see https://crccalc.com/?crc=F@A&method=crc8&datatype=ascii). I tried the same in C++ code and got same wrong results. Did I still get something wrong? – Silicomancer Nov 14 '18 at 00:17
  • 1
    I used the normal CRC-8 poly=0x07, init=0, xorout=0, refin=false, refout=false. – Silicomancer Nov 14 '18 at 00:23
  • 1
    Yes, you did it wrong. For the non-reflected CRC (refin and refout false), the bits of the polynomial are exclusive-or'ed in the order of the bits in the message. So `01000001 01000001 01000001` could be exclusive-or'ed with the polynomial ending at the least-significant bit of the second byte to give `01000000 01000110 01000001`, or "@FA". That gives the same CRC. – Mark Adler Nov 14 '18 at 00:43
  • You say "An r-bit CRC will detect all burst patterns of length r+1". I guess "An r-bit CRC will detect all burst patterns of length up to r+1" is also correct? – Silicomancer Apr 04 '23 at 12:34