CRC
Cyclic Redundancy Check


Home Page







 Premi qui per la versione Italiana




The CRC is used to ensure the integrity of packets transferred between two MCUs or between MCU and PC connected through an interface such as UART, SPI, I2C ETC.

Some latest MCUs include hardware generation of CRC for the I2C, USART etc.

What we do here is to implement the CRC by software.




INTRODUCTION

The principle of the CRC is to treat as binary sequences of binary polynomials, that is polynomials whose coefficients correspond to the binary sequence.

The binary sequence 0110101001 can be represented with the following polynomial form:
0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0 ovvero
X8 + X7 + X5 + X3 + X0 ovvero
X8 + X7 + X5 + X3 + 1
In this way, the bit of weight less of the sequence (the rightmost bit) represents the degree 0 of the polynomial  (X0= 1), the fourth bit from the right represents the degree of the polynomial 3 (X3) ...

A sequence of n bits is therefore a polynomial of maximum degree n-1.
All polynomial expressions are subsequently manipulated by modulo 2.




Generator Polynomial G normally as you choose a prime number that begins and ends with 1, some examples are:
1001 - 11101 - 1100000001111 (CRC12) - 11000000000000101 (CRC16)


APPLICATION

Let M be the message to be transmitted, the value is: 1010 0011 1010 1100
It is assumed that G is 11010
We call M' the message with the CRC
The CRC isM / G.
The CRCcode is the result of the division M / Gwhere to M are attached nbits null (0) corresponding to the degree of G.
We assume that G = 11010this means that its grade is 4; this means G(bit)=4so we attach 4null bits (0) to M.
Now Mis:
M = 1010 0011 1010 1100
0000.
Below is an example on how to calculate the CRC.

1010 0011 1010 1100 0000
1101 0||| since the leftmost bit is 1 we do the subtraction
0111 0||| here's the result after the XOR
111 00|| bring down the next digit, an since the leftmost bit is 1 we again subtract
110 10|| perform the subtraction
001 10|| here's the result after the XOR
01 101| bring down the next digit, and since the leftmost bit is 0 not do the subtraction and bring down another bit
1 1011 as the leftmost bit is 1 we again subtract
 1 1010
0 0001 here's the result after the XOR
zzzzz

Repeating these steps till the end, we will get:

xxxx

1010 0011 1010 1100 0000
1101 0
0111 00
110 10
001 101
01 1011
1 1010
0 0001 1
0001 10
001 101
01 1010
1 1010
0 0000 1
0000 11
000 110
00 1100
0 1100 0
1101 0
0001 00
001 000
01 0000
1 1010
0 1010 == CRC

To create M' it is sufficient to concatenate the CRC obtained to the M (message) to be transmitted:
M' = 1010 0011 1010 1100 + 1010
M'
= 1010 0011 1010 1100 1010

In general, the algorithm used can be represented as below.
Input there is:
M' = M + G(bit)
The loop is repeated until the last bit of M'







0 == CRC che essendo zero
If the receiver makes the division of M' with G and gets 0 (zero) it means that there were no errors during transmission.

Below there is an example where the CRC is concatenated to message during Tx and Rx that receive the message and recalculate the CRC (must be 0).





Main Polynomials






MCU Implementation 

There are two different techniques for implementing a CRC in software.


Loop driven implementation works like the calculation showed in Figure 1 (for 8bit MCU).
Data is entered into shift register and shifted to the left in sequence one at a time.

If one pops out at the MSb, the content is XORed with the polynomial.
In the other case, the registers are shifted by one position to the left.





Table driven implementation
Another method to calculate a CRC is to use precalculated values and XOR them to the data received.
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 advantage of the table driven implementation is that it is faster than theloop driven solution.
The drawback is that it consumes more program memory because of the size of the look-up table.
The CRC at the table driven implementation is generated by reading a precomputed value out of a table and XOR.


Comparation Table for 8bit MCU



Loop driven implementation

/* bit by bit
* The width of the CRC calculation and result.
* Modify the typedef for a 16 or 32-bit CRC standard.
*/
typedef uint8_t crc;

#define WIDTH (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH - 1))

crc
crcSlow(uint8_t const message[], int nBytes)
{
crc remainder = 0;


/*
* Perform modulo-2 division, a byte at a time.
*/
for (int byte = 0; byte < nBytes; ++byte)
{
/*
* Bring the next byte into the remainder.
*/
remainder ^= (message[byte] << (WIDTH - 8));

/*
* Perform modulo-2 division, a bit at a time.
*/
for (uint8_t bit = 8; bit > 0; --bit)
{
/*
* Try to divide the current data bit.
*/
if (remainder & TOPBIT)
{
remainder = (remainder << 1) ^ POLYNOMIAL;
}
else
{
remainder = (remainder << 1);
}
}
}

/*
* The final remainder is the CRC result.
*/
return (remainder);

} /* crcSlow() */

Table driven implementation

TABLE precalculation
crc crcTable[256];

void
crcInit(void)
{
crc remainder;


/*
* Compute the remainder of each possible dividend.
*/
for (int dividend = 0; dividend < 256; ++dividend)
{
/*
* Start with the dividend followed by zeros.
*/
remainder = dividend << (WIDTH - 8);

/*
* Perform modulo-2 division, a bit at a time.
*/
for (uint8_t bit = 8; bit > 0; --bit)
{
/*
* Try to divide the current data bit.
*/
if (remainder & TOPBIT)
{
remainder = (remainder << 1) ^ POLYNOMIAL;
}
else
{
remainder = (remainder << 1);
}
}

/*
* Store the result into the table.
*/
crcTable[dividend] = remainder;
}



} /* crcInit() */

Table driven implementation
crc
crcFast(uint8_t const message[], int nBytes)
{
uint8_t data;
crc remainder = 0;


/*
* Divide the message by the polynomial, a byte at a time.
*/
for (int byte = 0; byte < nBytes; ++byte)
{
data = message[byte] ^ (remainder >> (WIDTH - 8));
remainder = crcTable[data] ^ (remainder << 8);
}

/*
* The final remainder is the CRC.
*/
return (remainder);

} /* crcFast() */

Free source code in C

The example Loop driven andTable driven ready to use on Windows developed by Dev-C++ is here.
The Dev-C++ is free and it is possible to get it here, if you need to use my version of Dev-C++ click here.

The original source code for these CRC computations is placed into the public domain and is available in electronic form at http://www.netrino.com/code/crc.zip






Other examples to be tested:



// Programma che calcola il CRC di una sequenza di caratteri
// immessi da tastiera, terminati con EOF


#include <stdio.h>

#define PG 0x11021 /* Polinomio generatre */

int crc(int oldcrc, unsigned char toadd); /* Aggiunge toadd al CRC calcolato */

main()
{
int resto=0; // CRC
int c; // Carattere letto
int i = 0; // Contatore dei caratteri

printf("Inserisci una sequenza di caratteri: ");
while((c=getchar())!=EOF)
{
resto=crc(resto,c); // Agginge il carattere letto al CRC dei precedenti
i++; // Conta i caratteri letti
}
resto=crc(resto,0); // Agginge al CRC i primi otto zeri
resto=crc(resto,0); // Agginge al CRC i secondi otto zeri in fondo

printf("\nLetti %d caratteri, CRC calcolato: %x\n", i, resto);
}

/* Aggiunge i bit del codice oldcrc al dividendo, per
* calcolare il nuovo CRC
*/
int crc(int oldcrc, unsigned char toadd)
{
int i; // Indice del bit

// I bit del carattere vanno trattati dal piu' significativo al meno
for(i=0;i<8;i++) // Per ogni bit del byte
{
oldcrc= (oldcrc<<1) | (toadd>>7); // Aggiunge il bit piu' significativo
// del codice in fondo al CRC,
// spostando a sinistra i bit del CRC
toadd <<= 1; // Toglie il bit gestito dal codice
if((oldcrc & 0x10000) != 0) // Se il divisore ci sta' (alla sua maniera)
{
oldcrc=oldcrc^PG; // Allora lo toglie (sottrazione senza riporti,
// quindi XOR
}
}
return oldcrc; // Restituisce il CRC ricalcolato
}



CRC16 Calculation Algorithm

Polynomial: x16 + x12 + x5 + 1
Start Value: 0xFFFF

CRC_POLYNOM = 0x8408;
CRC_PRESET = 0xFFFF;

C-Example:

unsigned internal CRC = CRC_PRESET;
for (i = 0; i < cnt; i++) /* cnt = number of protocol bytes without CRC */
{
    crc ^= DATA[i];
    for (j = 0; j < 8; j++)
    {
        if (crc & 0x0001)
            crc = (crc >> 1) ^ CRC_POLYNOM;
        else
            crc = (crc >> 1);
    }
}






References
Web page that calculates the CRC:
http://www.zorc.breitbandkatze.de/crc.html
Articles on the theory of the CRC:
http://en.wikipedia.org/wiki/Cyclic_redundancy_check(EN)
http://it.wikipedia.org/wiki/Cyclic_redundancy_check(IT)
A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHM
http://www.geocities.com/SiliconValley/Pines/8659/crc.htm
http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
A Table-Driven implementation for speed up the CRC calculation (Chaper 10)
http://www.repairfaq.org/filipg/LINK/F_crc_v33.html#CRCV_001
http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
http://it.kioskea.net/contents/base/control.php3
http://www.microst.it/Progetti/CRC_2.html

EXAMPLEs
http://www.codeproject.com/KB/cs/csRedundancyChckAlgorithm.aspx
http://www.relisoft.com/science/CrcOptim.html
http://www.experts-exchange.com/Programming/Editors_IDEs/C_CPP_CS/CPP_Builder/Q_21192644.html
http://www.faqs.org/faqs/compression-faq/part1/section-26.html



Home Page