证明 CRC 的线性

use*_*098 5 crc

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

有人有什么主意吗?

多谢!

Mar*_*ler 4

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

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