The principle of the
CRC is to treat as
binary sequences of binary polynomials, that is polynomials whose
coefficients
correspond to the binary sequence.
0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0 ovveroIn 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) ...
X8 + X7 + X5 + X3 + X0 ovvero
X8 + X7 + X5 + X3 + 1
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)
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 11000000.
Below is an example on how to calculate the CRC.
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
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.
Comparation
Table
for 8bit MCU
/* 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() */
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() */
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() */
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
// 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
}
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);
}
}