CRC mistery

Cyclic redundancy check (CRC) is widely used  in computer and communication systems. There are a lot of articles about the theory and examples of  how to generate the CRC on the net. I'll go briefly trough the theory. 

CRC theory in short
CRC code is a fixed length binary sequence. It's used to detect errors in a set of data. The way it works is:

• CRC is calculated for each block of data. 
• The data and the CRC code are then send or stored both together. 
• When the block is read or received the CRC is calculated again and both CRCs compared. If they doesn't match there are errors in the data.

CRC Computation
To generate n-bit CRC we need input data and a binary representation of the CRC polynomial (n+1 bits). 
The polynomial is something like
x⁴ + x + 1
This can be represented in a binary format like 
1*x⁴ + 0*x³ + 0*x² + 1*x¹ + 1*x⁰
1        0         0        1        1
or
0x13 (CRC4 = >(n+1) = 5bit)

In order to calculate the CRC4 for the 8bit data 0x4A with the polynomial 0x13 we have to align the data in a row with the polynomial underneath. Also we have to add n-zeros (depends on the CRC, for CRC4 n=4) at the end of the data.
01001010000 -> 0x4A0
10011
----------------

If the most left bit of the data is '0' we only left shift the data, if it is '1' we xor the data with the polynomial. We repeat that until there are no any remaining bits on the data.
1001010000
10011
----------------
0000110000
        10011
----------------
        010110

          10011
----------------
          00101 -> 0x05 CRC

CRC Computation with lookup table

The calculation of the CRC could be very slow process as we have to do it bit-by-bit. It would be faster if we can do it for larger amount of data at once. And we can - with a precomputed lookup table. The idea behind the lookup table is to calculate the CRC for each byte from 0x00 to 0xFF and put them into a table. Then we can make our CRC calculation over the data per byte basis instead of per-bit.

CRCalc
I've tried to create a small GUI application which calculates the CRC (CRC calculator).

The source code is available at:
svn co https://crcalc.svn.sourceforge.net/svnroot/crcalc crcalc


Links 

• http://en.wikipedia.org/wiki/Cyclic_redundancy_check 
• http://www.ross.net/crc/download/crc_v3.txt 
• http://www.jonelo.de/java/jacksum/ 
• http://www.easics.com/webtools/crctool