crc - 证明 CRC 的线性

Question

我知道 CRC 是一个线性函数，这意味着 CRC(x xor y) = CRC(x) xor CRC(y)，但我不知道如何证明 CRC 的这个属性。

有谁有想法吗？

非常感谢!

Answer 1

这通常不是真的。仅对于具有零串的 CRC 始终为零的属性的 CRC 才是正确的。 (该属性很容易从您的方程中推导出来。)大多数 CRC 都有预处理和后处理，预处理的目的之一是确保情况并非如此。您不希望检查算法无法区分一串零中有多少个零。类似地，对于这样的检查算法，您可以在不改变检查值的情况下为消息添加任意数量的零。

没有预处理或后处理的“纯”CRC 确实具有您定义的线性属性。这可以通过查看 CRC 寄存器实现对单个位的作用以及如果反转该位会如何变化来看出。从寄存器一端滚出的一位，由您输入另一端的位决定，决定寄存器是否与多项式字进行异或运算。如果该位被反转，则会反转该决定。所以这两个CRC的异或就是多项式字。如果您将单个一位输出到初始化为零的寄存器的那一端(这是无预处理很重要的地方)，您将得到多项式字。所以消息的异或的CRC等于CRC的异或。然后通过一次一位地应用这一发现将其扩展到所有位。