Implement CRC algorithm from equation

Question

I'm dealing with a device which say to use this 16 bit cyclic redundancy check:

CCITT CRC-16 with polynomial x^16 + x^12 + x^5 + x^1

I looked for an implementation of such algorithm, but I did find only ones with the last term of the equation equal to 1 (i.e. x^0) instead of x^1, like this one or this.

I was going to implement the algorithm by myself, when I realized I don't know how to start. How is it supposed to develop a CRC calculation starting from an equation?

Answer 1

You are correct and the polynomial is wrong. A proper CRC polynomial must always have a 1 term. The CCITT CRC-16 polynomial is x^16 + x^12 + x^5 + 1 as noted by @guga, or 0x1021 in bit form (which leaves off the x^16). See this catalog of 16-bit CRCs.

The information there also provides the other key information you need besides the polynomial. Specifically:

width=16 poly=0x1021 init=0x1d0f refin=false refout=false xorout=0x0000 check=0xe5cc

which means that the CRC is not bit-reflected, it is initialized with 0x1d0f, and the result is not excusive-ored with anything. So the CCITT CRC of no bytes is 0x1d0f. It also provides a check value on the nine-byte string of ASCII digits "123456789", 0xe5cc. You should use that to check your implementation.

Ross Williams guide will tell you all you need to know about implementing CRCs.

Answer 2

This PDF file explains the subject: hackersdelight.org/crc.pdf.

I also recommend Computer Networks by Andrew Tanenbaum, as it has a chapter on the CRC algorithm.

Finally, I would double-check to see that your device does in fact implement that form of CRC as opposed to the standard one. It might just be a typo.