CRC 16-CCITT with lookup table

Question

So what I know about CRC, and also did a Java implementation is this:

Having an initial message as a 16-bit polynomial, for instance

0x0617
65
0000.0110.0001.0111

this one gets another 16 of 0 bits

0000.0110.0001.0111|0000.0000.0000.0000

Then, having the divisor,

0x1021
0001.0000.0010.0001 (0, 5, 12)

We allign it at the start of each "1" in our initial message, and do XOR between the bits, until there are no more 1s in the initial message. In total, there will be 6 XORs in our example.

The CRC will be the last 16 bits of our message, or the remainder of the division. In this case, 101011110110000.

My question is, how can I implement this with a look-up table? Can someone show me a numerical example on my polynomial on how it is calculated?

It doesn't follow the exact same algorithm that I used, though. — George Irimiciuc
Well, if you want an implementation for your CRC handed to you on a silver platter, then you're in the wrong place. If you want to understand how to implement CRCs in general and then apply your new knowledge to your specific polynomial (x1021), then you should read and understand the linked document. — Mark Adler
Not implementation, but at least a concrete example on a polynomial. I already implemented the calculations that I showed, just don't understand the principle of lookup tables. I can go just fine from there, it's just that I'd like an example, for instance on the same polynomial I showed in my OP(0x0617). — George Irimiciuc
The linked document not only describes (very well) how to build and use CRC lookup tables, it provides C code to do it for you. When using a table, your 0x06 is exclusive-ored with the CRC (which end depends on whether your polynomial is reflected or not), and then that byte is used to lookup a 16-bit value in a table. The CRC is shifted by eight (direction dependent on reflection), and then exclusive-ored with the table value. That is then repeated for 0x17. — Mark Adler

user1368116 user1368116 · Accepted Answer · 2014-03-29T23:58:38

I have been today working on this Issue and have created a code that works for any CRC, you will find many different CRCs in the crc.h file, some of them tested and working. The code is done in C, so you should not have many problems to use it in Java.

To be able to use any kind of CRC, the lookup table is generated dynamically, you can put the A_crcLookupTable array in the watch window and copy the values from the array if you want to include it as a constant.

I hope it helps you: https://sourceforge.net/projects/crccalculator/files/CRC/?

CRC 16-CCITT with lookup table

1 Answers