6

There are two ways of implementing CRC generation with linear feedback shift registers (LFSR), as shown in this figure CRC LFSR. 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.

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!

shva
  • 529
  • 2
  • 7
  • 13

2 Answers2

6

Here is my quick understanding.

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) * xn) % G(x)

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

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

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

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.

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

Let current CRC C(x) be {c4, c3, c2, c1, c0} and new bit that is shifted in be D
NewCRC = {M(x), D}*x5) % G(x) = (({M(x), 0} * x5) % G(x)) XOR ((D * x5) % 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}

i.e. the LFSR circuit A.

Kanad
  • 61
  • 1
  • 3
  • 1
    The explanation could be a bit more detailed. The trick is that since G(x) is a divisor or M(x) * x^n + C(x), then G(x) is also a divisor of (M(x) * x^n + C(x)) * x = M(x) * x ^(n+1) + C(x) * x. Therefore (M(x) * x^(n+1)) % G(x) = (C(x) * x) % G(x). This is what is calculated in the two first terms of the third line of the explanation above. The third term is (D * X^n) % G(x). – Adrian W Dec 14 '19 at 22:19
0

You can say that architecture (A) is implementing the modulo division by aligning MSB of the polyn with MSB of Message, so it is implementing something like the following (in my example I have another crc polyn actually):

enter image description here

But in Architecture (B), you can say we try to predict the MSB of the Message, so we align MSB of CRC polyn with MSB-1 of the message, something like the following:

enter image description here

I can recommend details about this operation in this tutorial

moibrahim
  • 89
  • 7