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

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

这个问题似乎与 help center 中定义的范围内的编程无关。 .

去年关闭。

Improve this question

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

有人可以指导我证明这一点吗？

Answer 1

不完全正确。 r 位 CRC 将检测长度为 r+1 的所有突发模式，除了一个模式(即多项式本身)。请参阅these lecture notes为证。

简单地说，为了使消息无法检测到错误，CRC 多项式必须除以错误多项式。如果误差多项式的长度为 r 位，则为不以 x 作为因子的 r+1 次多项式(即具有 1 term) 不能整除 r 次多项式，并且它唯一能整除的 r+1 次多项式就是它本身。所有 CRC 多项式都有 1 项。

您的另一个声明是任何 r 位散列的属性，它以相等的概率在散列的所有可能的 r 位值上分发消息，CRC 就是这样做的。 2^-r 只是应用错误恰好导致相同 CRC 的概率，其中有 2^r 的可能性。这相当于在 6 面骰子上掷出与您刚刚掷出的数字相同的概率是 1/6。