A Brief Explanation of CRC computation...
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 (&).
To compute the CRC for a string containing more than one character you would repeat the same process for each
succeeding character, each time using the computed CRC as the Seed for the next successive character instead of
0xFFFF.
The only difference between the forward and reversed algorithm is that in the forward algorithm we always compare the
MSB(leftmost bit) of both the character and the CRC and the shift operations are to the left instead of to the right. The
normal Polynomial used in the forward CCITT algorithm is 0x1021. You can obtain the same results from the forward and
reverse CRC algorithms by XOR the final result of the reversed algorithm with 0xFFFF.
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