了解使用LFSR实现CRC生成的两种不同方式 [英] Understanding two different ways of implementing CRC generation with LFSR

问题描述

有两种通过线性反馈移位寄存器（LFSR）实现CRC生成的方法，如下图所示：。该图片中生成多项式的系数为100111，红色的 +圆圈为异或运算符。两者的初始化寄存器值为00000。

There are two ways of implementing CRC generation with linear feedback shift registers (LFSR), as shown in this figure . The coefficients of generator polynomial in this picture are 100111, and the red "+" circles are exclusive-or operators. The initialization register values are 00000 for both.

例如，如果输入数据位流是10010011，则A和B都将给出CRC校验和1010。不同之处是A以8个移位结束，而B以由于将5个零附加到输入数据中，因此8 + 5 = 13个移位。我很容易理解B，因为它非常类似于2模除法。但是，我无法从数学上理解A如何在减少5个移位的情况下给出相同的结果。我听说有人在说A利用了预先添加的零，但我没有听懂。谁能向我解释？谢谢！

For example, if the input data bit stream is 10010011, both A and B will give CRC checksum of 1010. The difference is A finishes with 8 shifts, while B with 8+5=13 shifts because of the 5 zeros appended to the input data. I can understand B very easily since it closely mimics the modulo-2 division. However, I can not understand mathematically how A can give the same result with 5 less shifts. I heard people were talking A took advantage of the pre-appending zeros, but I didn't get it. Can anyone explain it to me? Thanks!

推荐答案

这是我的快速理解。

让我（x）是阶数为m的输入消息（即具有m + 1位），G（x）是阶数为n的CRC多项式。这样的消息的CRC结果由

Let M(x) be the input message of order m (i.e. has m+1 bits) and G(x) be the CRC polynomial of order n. CRC result for such a message is given by

C（x）=（M（x）* x ^{n ）％G（x）}

这是电路B所实现的。花费额外的5个周期是由于x ⁿ 操作。

This is what the circuit B is implementing. The additional 5 cycles it takes is because of the xⁿ operation.

电路A尝试采用更智能的方法，而不是遵循这种方法。它试图解决问题

Instead of following this approach, circuit A tries to do something smarter. Its trying to solve the question

如果C（x）是M（x）的CRC，则消息{ M（x），D}

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

其中D是新位。因此，它试图一次解决一位问题，而不是像电路b那样解决整个消息问题。因此，电路A将只需要8个周期来生成8位消息。

where D is the new bit. So its trying to solve one bit at a time instead of entire message as in case of circuit b. Hence circuit A will take just 8 cycles for a 8 bit message.

现在，由于您已经了解了电路B的工作方式，因此让我们看一下电路A。数学，特别是针对您的情况，因为在消息M（x）上对CRC添加位D的效果如下

Now since you already understand why circuit B looks the way it does, lets look at circuit A. The math, specifically for your case, for the effect of adding bit D to message M(x) on CRC is as below

让当前CRC C（x）为{c4，c3，c2，c1，c0}，而要移入的新位为D

NewCRC = {M（x），D} * x ⁵ ）％G（x）=（（{M（x），0} * x ⁵ ）％G（x））XOR（（D * x ⁵ ）％G（x））

，即（{c3，c2，c1，c0，0} XOR {0，0，c4，c4，c4}）XOR（{0，0， D，D，D}）

，即{c3，c2，c1 ^ c4 ^ D，c0 ^ c4 ^ D，c4 ^ D}

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。

这篇关于了解使用LFSR实现CRC生成的两种不同方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！