CRC Generating and Checking - Microchip Technology

1 2000 Microchip Technology 1AN730 INTRODUCTIONThis application note describes the Cyclic RedundancyCheck (CRC) theory and implementation. The CRCcheck is used to detect errors in a message. Two imple-mentations are shown: Table driven CRC calculation Loop driven CRC calculationThis application describes the implementation of theCRC-16 polynomial. However, there are several for-mats for the implementation of CRC such asCRC-CCITT, CRC-32 or other is a common method for detecting errors in trans-mitted messages or stored data. The CRC is a verypowerful, but easily implemented technique to obtaindata reliability. THEORY OF OPERATIONThe theory of a CRC calculation is straight forward. Thedata is treated by the CRC algorithm as a binary num-ber. This number is divided by another binary numbercalled the polynomial.

2 The rest of the division is theCRC checksum, which is appended to the transmittedmessage. The receiver divides the message (includingthe calculated CRC), by the same polynomial the trans-mitter used. If the result of this division is zero, then thetransmission was successful. However, if the result isnot equal to zero, an error occurred during the CRC-16 polynomial is shown in Equation 1. Thepolynomial can be translated into a binary value,because the divisor is viewed as a polynomial withbinary coefficients. For example, the CRC-16 poly-nomial translates to 1000000000000101b. All coeffi-cients, like x2 or x15, are represented by a logical 1 inthe binary division uses the Modulo-2 arithmetic. Modulo-2calculation is simply realized by XOR ing two numbers. EXAMPLE 1: MODULO-2 CALCULATIONEQUATION 1: THE CRC-16 POLYNOMIALE xample CalculationIn this example calculation, the message is two byteslong.

3 In general, the message can have any length inbytes. Before we can start calculating the CRC value 1,the message has to be augmented by n-bits, where nis the length of the polynomial. The CRC-16 polynomialhas a length of 16-bits, therefore, 16-bits have to beaugmented to the original message. In this examplecalculation, the polynomial has a length of 3-bits, there-fore, the message has to be extended by three zeros atthe end. An example calculation for a CRC is shown inExample 1. The reverse calculation is shown inExample 2. Authors: Thomas Schmidt Microchip Technology 0 0 1 1 0 0 1 0 10 1 0 0 1 1 0 1 1 11 1 0 1 0 1 0 0 1 0 XOR=XOR-FunctionX1 X2 Y0 0 00 1 11 0 11 1 0P(x) = x16+x15+x2+1 CRC Generating and CheckingAN730DS00730A-page 2 Preliminary 2000 Microchip Technology 2: CALCULATION FOR Generating A CRCEXAMPLE 3: Checking A MESSAGE FOR A CRC ERRORM essage = 110101 Polynomial = 1011 1 0 1 0 1 0 0 : 1 0 1 = 1 1 1 0 11 0 1 1 1 11 0 11 0 0 Remainder = CRC checksumMessage with CRC = 1 1 0 1 0 1 1 11 0 11 1 01 0 11 1 01 0 11 1 Quotient (has no function in CRC calculation)Message with CRC = 11010111 Polynomial = 1011 1 0 1 0 1 1 1.

4 1 0 1 = 1 1 1 0 11 0 1 1 1 11 0 11 0 0 Checksum is zero, therefore, no transmission error1 0 11 1 11 0 11 0 11 0 10 0 Quotient 2000 Microchip Technology 3AN730 FIGURE 1:HARDWARE CRC-16 GENERATORFIGURE 2:LOOP DRIVEN CRC IMPLEMENTATION CRC Hardware ImplementationThe CRC calculation is realized with a shift register andXOR gates. Figure 1 shows a CRC generator for theCRC-16 polynomial. Each bit of the data is shifted intothe CRC shift register (Flip-Flops) after being XOR edwith the CRC s most significant bit. Software ImplementationsThere are two different techniques for implementing aCRC in software. One is a loop driven implementationand the other is a table driven implementation. The loop driven implementation works like the calcula-tion shown in Figure 2. The data is fed through a shiftregister. If a one pops out at the MSb, the content isXORed with the polynomial.

5 In the other, the registersare shifted by one position to the method to calculate a CRC is to use precalcu-lated values and XOR them to the shift register.+++Datax0x2x15x16 Flip-FlopsCRC_HIGHCRC_LOWCRC_BUFFC077007 Note:The mathematical details are not givenwithin this application note. The interestedreader may refer to the material shown inthe Reference 4 Preliminary 2000 Microchip Technology DRIVEN CRC IMPLEMENTATIONThis section describes the loop driven CRC implemen-tation. This implementation is derived from the hard-ware implementation shown in Figure 1. The programfor the loop driven CRC generation and CRC checkingis shown in Appendix GenerationThe implementation of a loop driven CRC generation isshown in Figure 2. In the first step the registers,CRC_HIGH and CRC_LOW, are initialized with the firsttwo bytes of data.

6 CRC_BUFF is loaded with the thirdbyte of data. After that, the MSb of CRC_BUFF isshifted into the LSb of CRC_LOW and the MSb ofCRC_LOW is shifted into the LSb of CRC_HIGH. TheMSb of CRC_HIGH, which is now stored in the Carryflag, is tested to see if it is set. If the bit is set, the reg-isters, CRC_HIGH and CRC_LOW, will be XORed withthe CRC-16 polynomial. If the bit is not set, the next bitfrom CRC_BUFF will be shifted into the LSb ofCRC_LOW. This process is repeated until all data from CRC_BUFFis shifted into CRC_LOW. After this, CRC_BUFF isloaded with the next data byte. Then all data bytes areprocessed, and 16 zeros are appended to the mes-sage. The registers, CRC_HIGH and CRC_LOW, con-tain the calculated CRC value. The message can haveany length. In this application note, the CRC value for8 data bytes is calculated.

7 CRC CheckingThe CRC check uses the same technique as the CRCgeneration, with the only difference being that zerosare not appended to the DRIVEN CRC IMPLEMENTATIONA table driven CRC routine uses a different techniquethan a loop driven CRC routine. The idea behind atable driven CRC implementation is that instead of cal-culating the CRC bit by bit, precomputed bytes areXORed to the data. The source code for the tabledriven implementation is given in Appendix advantage of the table driven implementation isthat it is faster than the loop driven solution. The draw-back is that it consumes more program memorybecause of the size of the look-up GenerationThe CRC at the table driven implementation is gener-ated by reading a precomputed value out of a table andXOR, the result with the low and high byte of the CRCshift registers.

8 In the first step, the registers, CRC_BUFF, CRC_HIGHand CRC_LOW, are initialized with the first three bytesof data. After that, the value in CRC_BUFF is used asan offset to get the value for the precomputed CRCvalue out of the look-up table. Since the CRC-16 is 16bits long, the look-up table is split up into two separatelook-up tables. One for the high byte of the CRC regis-ter and one for the low byte of the CRC register (seeFigure 3). The result from the look-up table of the highbyte is XORed to the content of the CRC_HIGH regis-ter. The result for the low byte is XORed to the contentof CRC_LOW. The results are stored back next step is that the content from CRC_HIGH isshifted into CRC_BUFF and the content fromCRC_LOW is shifted into the register, the register, CRC_LOW, is loaded with the newdata byte.

9 This process repeats for all data bytes. At the end of theCRC generation, the message has to be appended by16 zeros. The 16 zeros are treated like the data the calculation is done, the content of the regis-ters, CRC_HIGH and CRC_LOW, are appended to CheckingThe CRC check uses the same technique as the CRCgeneration, with the difference being that zeros are notappended to the 1 shows a comparison between the loop drivenimplementation and the table driven the calculation, 8 data bytes were used. TABLE 1:CRC-16 COMPARISON TABLEI mplementationCRC Generation (in cycles)CRC Check (in cycles)Program Memory Usage (words)Data BytesLoop Driven 865870856 Table Driven 3483596125 2000 Microchip Technology 5AN730 ADVANTAGES OF CRC VS. SIMPLE SUM TECHNIQUESThe CRC generation has many advantages over sim-ple sum techniques or parity check.

10 CRC error correc-tion allows detection bit bit bit errors (bits next to each other)A parity bit check detects only single bit errors. TheCRC error correction is mostly used where large datapackages are transmitted, for example, in local areanetworks such as N. Williams - A Painless Guide to CRC ErrorDetection AlgorithmsDonald E. Knuth - The Art of Computer Programming,Volume 2, Addisson WesleyAN730DS00730A-page 6 Preliminary 2000 Microchip Technology 3:TABLE DRIVEN CRC CALCULATION IMPLEMENTATIONCRC_BUFFCRC_HIGHCRC_LOW070 077 TABLE_HIGH00xFF07 TABLE_LOW00xFF07++ 2000 Microchip Technology 7AN730 APPENDIX A: SOURCE CODE FOR LOOP DRIVEN CRC IMPLEMENATIONMPASM Intermediate 3-9-2000 13:00:00 PAGE 1 LOC OBJECT CODE LINE SOURCE TEXT VALUE 00001 ; ** 00002 ; * Title : CRC16 calculation * 00003 ; * Author : Thomas Schmidt * 00004.