Why does the CRC of "1" yield the generator polynomial itself?

4
votes

While testing a CRC implementation, I noticed that the CRC of 0x01 usually (?) seems to be the polynomial itself. When trying to manually do the binary long division however, I keep ending up losing the leading "1" of the polynomial, e.g. with a message of "0x01" and the polynomial "0x1021", I would get

      1 0000 0000 0000 (zero padded value)
(XOR) 1 0000 0010 0001
-----------------
      0 0000 0010 0001 = 0x0021

But any sample implementation (I'm dealing with XMODEM-CRC here) results in 0x1021 for the given input.

Looking at https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks, I can see how the XOR step of the upper bit leaving the shift register with the generator polynomial will cause this result. What I don't get is why this step is performed in that manner at all, seeing as it clearly alters the result of a true polynomial division?

1
algorithmcrccalculationcrc16
You are forgetting that the polynomial also has an implicit 1 bit, just to the left of the bit width. You should actually be calculating with 1 0001 0000 0010 0001. – jasonharper
I just noticed that too, see my post below.. Is there a place that might have made this more obvious? en.wikipedia.org/wiki/… lists every CRC-n with a length of n+1 and I now understand why, but there's no explicit mention of the reason. – David Schneider

1 Answers

0
votes

I just read http://www.ross.net/crc/download/crc_v3.txt and noticed that in section 9, there is mention of an implicitly prepended 1 to enforce the desired polynomial width.

In my example case, this means that the actual polynomial used as divisor would not be 0x1021, but 0x11021. This results in the leading "1" being dropped, and the remainder being the "intended" 16-bit polynomial:

      1 0000 0000 0000 0000 (zero padded value)
(XOR) 1 0001 0000 0010 0001
-----------------
      0 0001 0000 0010 0001 = 0x1021