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

Question

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

有人可以指导我进行相同的证明吗？

Answer 1

不完全正确。r位 CRC 将检测长度为r+1的所有突发模式，除了一个模式，即多项式本身。请参阅这些讲义以获得证明。

很简单，对于不检测错误的消息，CRC 多项式必须除以错误多项式。如果误差多项式的长度为r位，则不以x作为因子（即具有 1 项）的 r+1 次多项式不能除以r次多项式，并且它只能除以r+1次多项式是它本身。所有 CRC 多项式都有 1 项。

您的另一个主张是任何r位散列的属性，它以相等的概率在散列的所有可能的r位值上分配消息，CRC 就是这样做的。2 ^-r只是一个应用错误恰好导致相同 CRC 的概率，对此有2 ^r种可能性。这就像说在 6 面骰子上掷出的相同数字的几率是 1/6。