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)=x16 +x15+x 2+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 x2 or x15, 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
;CRC16 calculation - loop driven mode

#define PolynomLow 0b00000101 ; low byte of polynome

#define PolynomHigh 0b10000000 ; high byte of polynome

#define PolynomLength 0x10 ; 16-bit polynome length

#define DataLength 0x09 ; Data length in Bytes

#define Iterations 0x08 ; number of iterations for CRC calculation


.def CRC_HIGH=r18 ; CRC shift registers
.def CRC_LOW=r17 ; second CRC shift register
.def CRC_BUFF=r19 ; CRC buffer register
.def BITS=r21 ; number of data bits
.def DATABYTES=r20 ; number of bytes of data
.def W=r22

;.def r16=TEMP   already defined
.dseg
CRC16Buffer: .byte DataLength+2
.cseg

#if DataLength
.error "Data length must be bigger then 2 bytes"
#endif

CRC16:
   rcall CRC16Generate
; append CRC to message
   st Y+,CRC_HIGH
   st Y,CRC_LOW
ret
;***********************LOOP driven CRC16********************************

; *******************************************************************************
; * Title: CRC16 calculation
; * INPUT: Y Pointer to first data byte                 
; * USAGE: number of data bytes stored in register DATABYTES
; * OUTPUT: CRC result stored in CRC_HIGH and CRC_LOW
; *******************************************************************************

CRC16Generate:
   rcall CRC16Init
   ldi temp, 0x03 ; initialize TEMP register with 2

NextCRC16:    
   rcall CRC16Engine

    tst DATABYTES
   breq finalize  
   dec DATABYTES ; Decrement the number of data bytes by one
   rjmp Reload ; reload CRC_BUFF register with new data byte

finalize:
    dec temp
   brne AppendZeros ; Append zeros to message
    ret

AppendZeros:
    clr CRC_BUFF ; append data with zeros
   ldi BITS,Iterations ; with 0x08
   ;inc DATABYTES ; increment data bytes
   rjmp NextCRC16 ; last iteration

; Reload CRC buffer register with new data word.
Reload:
   ld CRC_BUFF,Y+ ; move data into CRC_BUFF register
   ldi BITS,Iterations ; initialize register BITS with 8
   rjmp NextCRC16 ; calculate next CRC





; *******************************************************************************
; * Titel: CRC16 Initialization
; * INPUT: Pointer to first data byte in Y
; * OUTPUT: none
; *******************************************************************************

CRC16Init:
   ld CRC_HIGH,Y+
   ld CRC_LOW,Y+
   ld CRC_BUFF,Y+

    ldi BITS,Iterations
   ldi DATABYTES,DataLength

    subi DATABYTES,3       ;we ve already loaded 3 bytes
ret

; *******************************************************************************
; * INPUT: Pointer to first data byte in register
; * OUTPUT: none
; *******************************************************************************
CRC16Engine:
   clc
    rol CRC_BUFF
   rol CRC_LOW
   rol CRC_HIGH

   brcc NextBitEngine ;is carry flag set? carry flag is clear there next rotation

   ldi W,PolynomHigh  ; carry flag is set therefore XOR CRCSHIFT registers
    eor CRC_HIGH, W ; XOR CRC_HIGH register
    ldi W,PolynomLow ; load w-register with low byte of polynom
    eor CRC_LOW, W ; XOR CRC_LOW register

NextBitEngine:
   
   dec BITS ;do for all bits
    brne CRC16Engine ; calculate CRC for next bit

ret


; *******************************************************************************
; * Input: Pointer to first data byte *
; * Output: t=0 CRC was restore sucessfull *
; *         t=1 CRC was not restored sucessfull *
; *******************************************************************************
CRC16Restore:
   rcall CRC16Init  ; initialize CRC registers
   subi  DATABYTES,-3 ; add offset to register DATABYTES

NextCRCRestore:
    rcall CRC16Engine
   dec DATABYTES ; Decrement the number of data bytes by one
   brne ReloadRestore ; reload CRC_BUFF register with new data byte
   
   tst CRC_HIGH
   brne  CRCError
    tst CRC_LOW
   brne CRCError
    clt
ret

CRCError:
    set
ret

; Reload CRC buffer register with new data word.
ReloadRestore:
   ld CRC_BUFF,Y+ ; move data into CRC_BUFF register
   ldi BITS,Iterations ; initialize register BITS with 8
   rjmp NextCRCRestore ; calculate next CRC

 

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
; *******************************************************************************
; * Title:              CRC16 Table driven calculation                         
; * Input parameter:    Pointer to first data byte                             
; *                     Number of data bytes stored in register DATABYTES      
; * Usage:              Z register
; * Output:             CRC result stored in CRC_HIGH and CRC_LOW              
; *******************************************************************************
FastCRC16:
   rcall FastCRC16Generate
; append CRC to message
   st Y+,CRC_HIGH
   st Y,CRC_LOW
ret
FastCRC16Generate:
   rcall    FastCRC16Init               ; initialize CRC registers
   ldi temp, 0x03 ; initialize TEMP register with 2

CalculateCRC:
   ldi        ZL,low(2 * CRC16Tab1)
   ldi        ZH,high(2 * CRC16Tab1)   ;get value for high byte
   clr     W
   add        ZL,CRC_BUFF              
   adc        ZH,W
    lpm     W,Z                      
    eor     CRC_HIGH,W    ; XOR table element with high byte

   ldi        ZL,low(2 * CRC16Tab2)
   ldi        ZH,high(2 * CRC16Tab2)   ;get value for low byte
   clr     W
   add        ZL,CRC_BUFF              
   adc        ZH,W
    lpm     W,Z                      
    eor     CRC_LOW,W    ; XOR table element with low byte    

    tst DATABYTES
   breq fastfinalize  
   dec DATABYTES ; Decrement the number of data bytes by one
   rcall FastReload ; reload CRC_BUFF register with new data byte
    rjmp CalculateCRC
      
fastfinalize:
    dec temp
   brne fastappendzeros ; Append zeros to message
    ret

fastappendzeros:
    mov    CRC_BUFF,CRC_HIGH             ; copy high byte  to CRC_BUFF
    mov    CRC_HIGH,CRC_LOW               ; Copy low byte into CRC_HIGH
    clr    CRC_LOW                 ; and from there into CRC_LOW
    rjmp    CalculateCRC            ; calculate CRC for next byte                  

; *******************************************************************************
; * Titel: CRC16 Initialization                                                
; * Input: Pointer to first data byte  in Y                                        
; * Output: none                                                               
; *******************************************************************************

FastCRC16Init:
   ld CRC_BUFF,Y+
   ld CRC_HIGH,Y+
   ld CRC_LOW,Y+

   ldi DATABYTES,DataLength

    subi DATABYTES,3       ;we ve already loaded 3 bytes
ret



; *******************************************************************************
; * Titel: Reload CRC_HIGH, CRC_LOW and CRC_BUFF register                      
; * Input: Pointer to next data byte in Y register                           
; * Output:                                                                    
; *******************************************************************************
FastReload:
   mov CRC_BUFF,CRC_HIGH       ;move high byte to buffer
   mov CRC_HIGH,CRC_LOW        ;move low to high byte
   ld CRC_LOW,Y+                ;load low byte with next data byte
ret


CRC16Tab1:
   .db 0x00,0x00,0x10,0x21,0x20,0x42,0x30,0x63,0x40,0x84,0x50,0xA5,0x60,0xC6,0x70,0xE7
   .db 0x81,0x08,0x91,0x29,0xA1,0x4A,0xB1,0x6B,0xC1,0x8C,0xD1,0xAD,0xE1,0xCE,0xF1,0xEF
   .db 0x12,0x31,0x02,0x10,0x32,0x73,0x22,0x52,0x52,0xB5,0x42,0x94,0x72,0xF7,0x62,0xD6
   .db 0x93,0x39,0x83,0x18,0xB3,0x7B,0xA3,0x5A,0xD3,0xBD,0xC3,0x9C,0xF3,0xFF,0xE3,0xDE
   .db 0x24,0x62,0x34,0x43,0x04,0x20,0x14,0x01,0x64,0xE6,0x74,0xC7,0x44,0xA4,0x54,0x85
   .db 0xA5,0x6A,0xB5,0x4B,0x85,0x28,0x95,0x09,0xE5,0xEE,0xF5,0xCF,0xC5,0xAC,0xD5,0x8D
   .db 0x36,0x53,0x26,0x72,0x16,0x11,0x06,0x30,0x76,0xD7,0x66,0xF6,0x56,0x95,0x46,0xB4
   .db 0xB7,0x5B,0xA7,0x7A,0x97,0x19,0x87,0x38,0xF7,0xDF,0xE7,0xFE,0xD7,0x9D,0xC7,0xBC
   .db 0x48,0xC4,0x58,0xE5,0x68,0x86,0x78,0xA7,0x08,0x40,0x18,0x61,0x28,0x02,0x38,0x23
   .db 0xC9,0xCC,0xD9,0xED,0xE9,0x8E,0xF9,0xAF,0x89,0x48,0x99,0x69,0xA9,0x0A,0xB9,0x2B
   .db 0x5A,0xF5,0x4A,0xD4,0x7A,0xB7,0x6A,0x96,0x1A,0x71,0x0A,0x50,0x3A,0x33,0x2A,0x12
   .db 0xDB,0xFD,0xCB,0xDC,0xFB,0xBF,0xEB,0x9E,0x9B,0x79,0x8B,0x58,0xBB,0x3B,0xAB,0x1A
   .db 0x6C,0xA6,0x7C,0x87,0x4C,0xE4,0x5C,0xC5,0x2C,0x22,0x3C,0x03,0x0C,0x60,0x1C,0x41
   .db 0xED,0xAE,0xFD,0x8F,0xCD,0xEC,0xDD,0xCD,0xAD,0x2A,0xBD,0x0B,0x8D,0x68,0x9D,0x49
   .db 0x7E,0x97,0x6E,0xB6,0x5E,0xD5,0x4E,0xF4,0x3E,0x13,0x2E,0x32,0x1E,0x51,0x0E,0x70
   .db 0xFF,0x9F,0xEF,0xBE,0xDF,0xDD,0xCF,0xFC,0xBF,0x1B,0xAF,0x3A,0x9F,0x59,0x8F,0x78

CRC16Tab2:
   .db 0x91,0x88,0x81,0xA9,0xB1,0xCA,0xA1,0xEB,0xD1,0x0C,0xC1,0x2D,0xF1,0x4E,0xE1,0x6F
   .db 0x10,0x80,0x00,0xA1,0x30,0xC2,0x20,0xE3,0x50,0x04,0x40,0x25,0x70,0x46,0x60,0x67
   .db 0x83,0xB9,0x93,0x98,0xA3,0xFB,0xB3,0xDA,0xC3,0x3D,0xD3,0x1C,0xE3,0x7F,0xF3,0x5E
   .db 0x02,0xB1,0x12,0x90,0x22,0xF3,0x32,0xD2,0x42,0x35,0x52,0x14,0x62,0x77,0x72,0x56
   .db 0xB5,0xEA,0xA5,0xCB,0x95,0xA8,0x85,0x89,0xF5,0x6E,0xE5,0x4F,0xD5,0x2C,0xC5,0x0D
   .db 0x34,0xE2,0x24,0xC3,0x14,0xA0,0x04,0x81,0x74,0x66,0x64,0x47,0x54,0x24,0x44,0x05
   .db 0xA7,0xDB,0xB7,0xFA,0x87,0x99,0x97,0xB8,0xE7,0x5F,0xF7,0x7E,0xC7,0x1D,0xD7,0x3C
   .db 0x26,0xD3,0x36,0xF2,0x06,0x91,0x16,0xB0,0x66,0x57,0x76,0x76,0x46,0x15,0x56,0x34
   .db 0xD9,0x4C,0xC9,0x6D,0xF9,0x0E,0xE9,0x2F,0x99,0xC8,0x89,0xE9,0xB9,0x8A,0xA9,0xAB
   .db 0x58,0x44,0x48,0x65,0x78,0x06,0x68,0x27,0x18,0xC0,0x08,0xE1,0x38,0x82,0x28,0xA3
   .db 0xCB,0x7D,0xDB,0x5C,0xEB,0x3F,0xFB,0x1E,0x8B,0xF9,0x9B,0xD8,0xAB,0xBB,0xBB,0x9A
   .db 0x4A,0x75,0x5A,0x54,0x6A,0x37,0x7A,0x16,0x0A,0xF1,0x1A,0xD0,0x2A,0xB3,0x3A,0x92
   .db 0xFD,0x2E,0xED,0x0F,0xDD,0x6C,0xCD,0x4D,0xBD,0xAA,0xAD,0x8B,0x9D,0xE8,0x8D,0xC9
   .db 0x7C,0x26,0x6C,0x07,0x5C,0x64,0x4C,0x45,0x3C,0xA2,0x2C,0x83,0x1C,0xE0,0x0C,0xC1
   .db 0xEF,0x1F,0xFF,0x3E,0xCF,0x5D,0xDF,0x7C,0xAF,0x9B,0xBF,0xBA,0x8F,0xD9,0x9F,0xF8
   .db 0x6E,0x17,0x7E,0x36,0x4E,0x55,0x5E,0x74,0x2E,0x93,0x3E,0xB2,0x0E,0xD1,0x1E,0xF
  • 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.

void make_crc_table( void ) {
   int i, j;
   unsigned long poly, c;
   /* terms of polynomial defining this crc (except x^16): */
   static const byte p[] = {0,5,12};

   /* make exclusive-or pattern from polynomial (0x1021) */
   poly = 0L;
   for ( i = 0; i < sizeof( p ) / sizeof( byte ); i++ ) {
       poly |= 1L << p[i];
   }

   for ( i = 0; i < 256; i++ ) {
       c = i << 8;
       for ( j = 0; j < 8; j++ ) {
           c = ( c & 0x8000 ) ? poly ^ ( c << 1 ) : ( c << 1 );
       }
       crctable[i] = (unsigned short) c;
       printf( " %d:%x", i, crctable[i]);
   }


}


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.

Comments

p=polinomial       Reply

By Serge on Mon Oct 01 11:21:41 UTC 2012

p array serves to help construct the polinomial,which is accumulated in poly variable:
for ( i = 0; i < sizeof( p ) / sizeof( byte ); i ) {
poly |= 1L << p[i];
}
Each value in p array stands for the 1 in the polinomial!

p = array of 3 bytes       Reply

By Anonymous on Mon Sep 24 12:43:35 UTC 2012

Hi p only has 3 bytes and yet it is reference in the for loop upto array 256?

Am I miising something?

Many thanks for your example code

p=polinomial

By Serge on Mon Oct 01 11:28:05 UTC 2012

In the for loop it is referenced 3 times sizeof(p)/sizeof(byte)=3
Variable poly accumulates the polinomial:
0b1000000100001/0x1021/4129

crc       Reply

By Jaarholm on Sat Jun 23 21:54:00 UTC 2012

Hi.

Thanks for a nice and understandable article.
and very nice to find some assembly examples.

jimmi.



 Add Comment

  Comments 1 - 4 of 4  

Screen Name
Subject
Comment