This explaination is brief summary of the Document "A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS" by Ross N. Williams, without getting into the complex mathematical explanation.
The CRC computation process basically takes a string one character at a time and uses it to modify an 16 bit or 32 bit word to be able to generate a unique word that can be duplicated to verify that the string's contents are still intact at a later time. The Generated CRC code works out so that if transmit the string appended with the CRC trasmited Least significant byte first to Most significant byte last, and then generate the CRC for the entire sequence the computed CRC will equal Zero. The actual computation process takes the string in one character at a time as mentioned before. Consider the following example...
We will take the character "T" and generate a 16 bit CRC using the CCITT reversed algorithm.
The First thing that we do is convert the Character into an integer. This is done by getting the ASCII code that relates to a character, in this case "T" is a decimal 84, or 1010100 in Binary or Base 2. In the CCITT reversed algorithm you always start with the CRC being equal to 0xFFFF or in simpler terms all 16 bits being equal to a 1. For the reversed algorithm we will be shifting the bits of the CRC and the character to the right.
A quick example of bit shifting would be the following.... 1010100 Base 2 shifted to the right by one bit would be 0101010 Base 2. You shift all of the bits to the right and add a zero to the left.
Now then the basic premise behind generating a CRC is that you work through the 8bit character one bit at a time shifting the CRC to the right, or to the left (depending on whether you are using the foward or reverse algorithm) once for each bit, and also shifting the 8bit character the same. If at any time the shift operation will shift a one out of either the CRC or the character, but not both, then you will also add the value in the CRC to the base Polynomial using binary arithmetic with no carries.
In binary arithmetic with no carries 1+1=0, 1+0=1, 0+1=1, and 0+0=0. This is the same as using the C opeartion Xor.
The base Polynomial is a standard polynomial that is dependant upon the type of CRC you are generating in this example the base polynomial is 0x8408 or 1000010000001000 in base two. Having explained all of this here is the basic formula to calculate the CCITT reversed CRC for the character "T"
All computation will be done in Base two...
The character "T" = 01010100 . Since we will be shifting to the right we look at the LSB(rightmost bit) in each of these The CRC = 1111111111111111. The LSB of the CRC is a one and the LSB of our character is not resulting in an add operation but first we shift to the right one bit. The character = 00101010 The CRC = 0111111111111111. Now we perform the addition to the Polynomial CRC 0111111111111111 POLYNOMIAL +1000010000001000 ----------------------------------------------- CRC = 1111101111110111 Once again we have a 1 in the LSB of the CRC and not in the character so ----------------------------------------------- Character = 00010101 CRC = 0111110111111011 Now add the Polynomial again. POLYNOMIAL +1000010000001000 ----------------------------------------------- CRC = 1111100111110011 Now we have a 1 in both the CRC and the Character so only the shift operation is performed ----------------------------------------------- Character = 00001010 CRC = 0111110011111001 Now there is a 1 in the CRC and not in the character so we will add again. ----------------------------------------------- Character = 00000101 CRC = 0011111001111100 POLYNOMIAL= +1000010000001000 ----------------------------------------------- CRC = 1011101001110100 Now there is a 1 in the Character and not in the CRC so we will add again. ----------------------------------------------- Character = 00000010 CRC = 0101110100111010 POLYNOMIAL= +1000010000001000 ----------------------------------------------- CRC = 1101100100110010 Now there is not a one in either the character or the crc so we only shift. ----------------------------------------------- Character = 00000001 CRC= 0110110010011001 Now there is a one in both so we will only shift right. ----------------------------------------------- Character= 00000000 CRC= 0011011001001100 Now there is not a one in either so only the sift will be performed ----------------------------------------------- CRC = 0001101100100110 This was our eighth and final shift for this character this is the computed CRC for the character "T"The resulting CRC calculation for the character "T" is 0x1B26 or a decimal 6950. If you were going to use this computed CRC to append to a transmission you would divide the number by the Decimal number 256 and assign the result to the High Byte and the remainder to the Low Byte and then transmit the CRC Low Byte first High Byte second. In this case the Exact ASCII representation of the transmission would look like this.... "T&^[" or T&(ESC). The High Byte is an ASCII(27) which is equal to the escape key or ctrl-leftbracket (^[). The Low Byte is an ASCII(38) which is the ampersand (&).
For a more detailed explaination of CRC calculation please read "A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS" by Ross Williams. This document can be obtained from the following Url.
Crc faq version 3