CRC implementation explained

Cyclic Redundancy Check   (CRC) .

CRC is a common method for detecting errors in transmitted messages or  stored data. All packets sent over a network connection(I2C/SPI/1Wire/..) are checked with a CRC.The CRC is   a very  powerful, yet easily implemented technique to obtain data reliability.

Two implementations are shown:

• Table driven CRC calculation                                                                          
• Loop driven CRC calculation    
  

There   are   several   formats for  the   implementation  of   CRC     such    as CRC-CCITT, CRC-32 or other polynomials.This   article  describes   the   implementation  of  the CRC-16   polynomial. 

 

Theory of operation

The data is treated by the CRC algorithm as a binary number. This number is divided by another binary number called   the   polynomial. The   rest   of   the   division   is   the CRC checksum, which is appended to the transmitted message. The receiver divides the message (including
the calculated CRC), by the same polynomial the transmitter used. If the result of this division is zero, then the transmission was successful. However, if the result is not equal to zero, an error occurred during the transmission.
The CRC-16 polynomial is of the form:

P(x)=x¹⁶ +x¹⁵+x ²+1

The polynomial can   be   translated   into  a  binary  value, because   the   divisor   is viewed   as  a  polynomial   with binary   coefficients.   For  example,   the   CRC-16     polynomial  translates   to 1000000000000101b.   All  coefficients, like x² or x¹⁵, are represented by a logical 1 in the binary value. The highest coefficient is dropped.

The division   uses the   Modulo-2   arithmetic.   Modulo-2 calculation is simply realized by XOR’ing two numbers.

 

 

Example Calculation

In this example calculation, the message is two bytes long. In general, the message can have any length in bytes. Before we can start calculating the CRC value 1, the message has to be augmented by n-bits, where n is the length of the polynomial.The CRC-16 polynomial has a length of 16-bits, therefore, 16-bits have to be augmented to the original message. In this example calculation, the polynomial has a length of 3-bits, therefore, the message has to be extended by three zeros at the end. An example calculation for a CRC is shown in Fig 1.

 

 

The reverse calculation is shown in Fig 2.

Software Implementations

There are two different techniques for implementing a CRC in software. One is a loop driven implementation and the other is a table driven implementation. Both implementations are realized in AVR assembler.
The loop driven implementation works like the calculation shown in Figure 3. The data is fed through a shift register. If a one pops out at the MSb, the content is XORed with the polynomial. In the other, the registers are shifted by one position to the left.
Another method to calculate a CRC is to use precalculated values and XOR them to the shift register.

 

Loop Driven CRC implementation

What follows is an explanation and assembler code implementation of the loop driven CRC

• CRC Generation

The implementation of a loop driven CRC generation is shown in Figure 3. In the first step the registers, CRC_HIGH and CRC_LOW, are initialized with the first two bytes of data. CRC_BUFF is loaded with the third byte of data. After that, the MSb of CRC_BUFF is shifted into the LSb of CRC_LOW and the MSb of CRC_LOW is shifted into the LSb of CRC_HIGH. The MSb of CRC_HIGH, which is now stored in the Carry flag, is tested to see if it is set. If the bit is set, the registers, CRC_HIGH and CRC_LOW, will be XORed with the CRC-16 polynomial. If the bit is not set, the next bit from CRC_BUFF will be shifted into the LSb of CRC_LOW.

This process is repeated until all data from CRC_BUFF is shifted into CRC_LOW. After this, CRC_BUFF is loaded with the next data byte. Then all data bytes are processed, and 16 zeros are appended to the message. The registers, CRC_HIGH and CRC_LOW, contain the calculated CRC value. The message can have any length. In this application note, the CRC value for 9 data bytes is calculated.

 

• CRC Checking

The CRC check uses the same technique as the CRC generation, with the only difference being that zeros are not appended to the message.

 

• AVR Assembler CRC16 loop driven implementation

 

Table Driven CRC implementation

A table driven CRC routine uses a different technique than a loop driven CRC routine. The idea behind a table driven CRC implementation is that instead of calculating the CRC bit by bit, precomputed bytes are XORed to the data. The source code for the table driven implementation is given below. The advantage of the table driven implementation is that it is faster than the loop driven solution. The drawback is that it consumes more program memory because of the size of the look-up table.

• CRC Generation

The CRC at the table driven implementation is generated by reading a precomputed value out of a table and XOR, the result with the low and high byte of the CRC shift registers.
In the first step, the registers, CRC_BUFF, CRC_HIGH and CRC_LOW, are initialized with the first three bytes of data. After that, the value in CRC_BUFF is used as an offset to get the value for the precomputed CRC value out of the look-up table. Since the CRC-16 is 16 bits long, the look-up table is split up into two separate look-up tables. One for the high byte of the CRC register and one for the low byte of the CRC register (Fig. 4).

The result from the look-up table of the high byte is XORed to the content of the CRC_HIGH register. The result for the low byte is XORed to the content of CRC_LOW. The results are stored back in CRC_LOW.

 

The next step is that the content from CRC_HIGH is shifted into CRC_BUFF and the content from CRC_LOW is shifted into the register, CRC_HIGH. Then the register, CRC_LOW, is loaded with the new data byte.
This process repeats for all data bytes. At the end of the CRC generation, the message has to be appended by 16 zeros. The 16 zeros are treated like the data bytes.
After the calculation is done, the content of the registers, CRC_HIGH and CRC_LOW, are appended to the message.

• CRC Checking

The CRC check uses the same technique as the CRC generation, with the difference being that zeros are not appended to the message.

• AVR Assembler CRC16 table driven implementation

• CRC16 Table genartion

The 2 tables above were generated by the following C code by splitting the first 128 words(2 bytes) values for the first table and the following 128 words(2 bytes) value for the second table.

Advantages of CRC vs. simple Sum Techniques
The CRC generation has many advantages over simple sum techniques or parity check. CRC error correction allows detection of:

• single bit errors
• double bit errors
• bundled bit errors (bits next to each other)

A parity bit check detects only single bit errors. The CRC error correction is mostly used where large data packages are transmitted, for example, in local area networks such as Ethernet.