CRC突发错误检测校验和结果的证明

Question

据说CRC（循环冗余校验和）可以检测到小于r +1位的突发错误，其中r是多项式的次数。此外，以1 – 2 ^-r的概率检测到长度大于r + 1位的突发。

有人可以指导我提供相同的证明吗？

Answer 1

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.

您的另一个主张是任何r位散列的属性，该散列以相等的概率在散列的所有可能的r位值上分布消息，而CRC则这样做。2 ^-r只是应用错误恰好导致相同CRC的概率，对于它，存在2 ^r的可能性。就像说在6面骰子上滚动相同数字的机会是1/6。