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

Return to the vbCrC Homepage...