crc - 了解使用 LFSR 实现 CRC 生成的两种不同方法

Question

使用线性反馈移位寄存器(LFSR)实现CRC生成有两种方法，如图所示。图中生成多项式的系数为100111，红色“+”圆圈为异或运算符。两者的初始化寄存器值都是 00000。

例如，如果输入数据比特流是10010011，则A和B都会给出1010的CRC校验和。不同之处在于A完成了8次移位，而B由于附加了5个零而完成了8+5=13次移位到输入数据。我可以很容易地理解 B，因为它非常模仿模 2 除法。然而，我无法从数学上理解 A 如何在少 5 个类次的情况下给出相同的结果。我听说人们在谈论 A 利用了预先附加的零，但我没有明白。谁能给我解释一下吗？谢谢!

Answer 1

这是我的快速理解。

令 M(x) 为 m 阶输入消息(即具有 m+1 位)，G(x) 为 n 阶 CRC 多项式。此类消息的 CRC 结果由下式给出:

C(x) = (M(x) * xⁿ) % G(x)

这就是电路 B 正在实现的。额外需要 5 个周期是因为 xⁿ 操作。

电路 A 没有遵循这种方法，而是尝试做一些更聪明的事情。它试图解决这个问题

If C(x) is the CRC of M(x), what would be the CRC for message {M(x), D}

其中 D 是新位。因此它试图一次解决一位而不是像电路 b 那样解决整个消息。因此，对于 8 位消息，电路 A 仅需要 8 个周期。

现在，既然您已经了解了为什么电路 B 看起来像它那样，那么让我们看看电路 A。专门针对您的情况的数学，将位 D 添加到消息 M(x) 对 CRC 的影响如下

Let current CRC C(x) be {c4, c3, c2, c1, c0} and new bit that is shifted in be D
NewCRC = {M(x), D}*x⁵) % G(x) = (({M(x), 0} * x⁵) % G(x)) XOR ((D * x⁵) % G(x))
which is ({c3, c2, c1, c0, 0} XOR {0, 0, c4, c4, c4}) XOR ({0, 0, D, D, D})
which is {c3, c2, c1^c4^D, c0^c4^D, c4^D}

即LFSR电路A。