CRC CHECK
The problem : how to check that a received message is correct and it is not disturbed? (due to electronic noise.)
For example having the message 04 29 06 a first idea is to calculate the sum of all of the bytes of the message that is sum S=39 and adding the sum at the end of the message.
Message with checksum: 04 29 06 39
Reciever has to add the bytes of the message and to compare the sum with the last byte of the message simply.
But if the message was disturbed like 03 29 07 then S=39, correct!
A much more sensitive and safe methode, as mathematics proove, is to see the message as a polynomial of x modulo 2, the coeficients of the polynomial will be 0 or 1 only.
Our message is 0000 0011 0010 1001 0000 0111 so we can see it as the polynomial :
M=x^17+x^16+x^13+x^11+x^8+x^2+x+1
Now having a fix polynomial, say D= x^6+x^3+x^2+x+1 or the 0100 1111 that is known by the transmiter and reciever
and dividing M by D we find the remainder: R=x^2 or 0100.
110110010101
--------------------
1001111 ) 110010100100000111
1001111
-------
10101000100000111
1001111
-------
0110110100000111
1001111
-------
10001000000111
1001111
-------
0010110000111
1001111
-------
0101110111
1001111
-------
01001011
1001111
-------
0000100
Modulo2 addition, subtraction ,multiplication and division calculator:
http://www.ee.unb.ca/cgi-bin/tervo/calc.pl?num=0000+0011+0010+1001+0000+0111+&den=01001111&f=d&p=1&m=1
If our message was the 0000 0011 0010 1001 0000 0110 or the polynomial M=x^17+x^16+x^13+x^11+x^8+x^2+x then dividing
it by D= x^6+x^3+x^2+x+1 gives R=x^2+1 or 0101
For M=x^17+x^16+x^13+x^11+x^8+x^2+1 or
0000 0011 0010 1001 0000 0100 we have R=x^2+x+1 or 0111
for 0000 0011 0010 1001 0100 0000 we have R=1100
sensitive process !
110110010100
--------------------
1001111 ) 110010100101000000
1001111
-------
10101000101000000
1001111
-------
0110110101000000
1001111
-------
10001001000000
1001111
-------
0010111000000
1001111
-------
0100110000
1001111
-------
00001100
Now subtracting the Remainder (The CRC checksum) from the original message (subtraction and addition are the same at modulo2 arithmetic ,Modulo2 addition is a simple XORing) we have:
0000 0011 0010 1001 0100 0000 XOR 00001100 =110010100101001100
and dividing this new polynomial 110010100101001100 by
D= x^6+x^3+x^2+x+1 or the 0100 1111 we have:
R=0 Bingo!!!
It is important to know that the Arithmetic of CRC checksum is the Arithmetic of the Field of Polynomials Modulo2 and that this Arithmetic is different than the Arithmetic of the Set of Binary Numbers !
Next, watch an interesting property of CRC with an example:
Our message is the:
1100100000101101 or the x15+x14+x11+x5+x3+x2+1 =(x15+x14+x11)+ (x5+x3+x2+1)
and our divisor is 01001111 or the x6+x3+x2+x+1
THE REMAINDER OF THE DIVISION : 1100100000101101/01001111 is x^2+x or R=110 ,
THE CRC CHECKSUM WITH GENERATOR THE x6+x3+x2+x+1.
NOW,
x15+x14+x11 is the 1100100000000000
THE REMAINDER 1100100000000000/01001111 is R1=101011
x5+x3+x2+1 is the 00101101
THE REMAINDER 00101101/01001111 is R2=101101
and R1 XOR R2 = R nice !!!
(the largest power of x at the remainders R1 and R2 is less than the power of the divisor--in our case 6-- so the power of the polynomial R1 XOR R2 is less than 6)
We can proove the above result easily writting some Algebra:
Say M= x15+x14+x11+x5+x3+x2+1 and D= x6+x3+x2+x+1
M1= x15+x14+x11 and M2= x5+x3+x2+1 so,
M1= D*Q1+R1 and M2= D*Q2+R2 Q1 and Q2 are the unknown quotients (nobody gives care to them) .
M=Μ1+Μ2=D*(Q1+Q2)+(R1+R2), since GF(2) field is commutative.
Also we have:
M1+R2= D*Q1+(R2+R1)= D*Q1+R beautyfull !!!
in words: the CRC of M= the CRC of (M1 XOR (CRC of M2) )
M=1100100000101101 , M1= 1100100000000000 , M2=00101101 , D=01001111
CRC OF M2=101101
M1 XOR (CRC of M2)= 1100100000000000 XOR 101101 =1100100000101101
CRC of (M1 XOR (CRC of M2) ) =110
An other way to proove it is this:
We have CRC (MI+CRC M2)= CRC(M1+R2)= CRC M1+CRC R2 = CRC(M-M2)+CRC R2=
CRC (M+M2)+ R2= CRC M+ CRC M2 +R2= CRC M + R2+ R2= CRC M.
Since in GF(2) addition and subtraction of polynomials are idendical and F(X)+F(X)=0 polynomial.
...exotic.
Remember that our arithmetic is the arithmetic of the field of polynomials modulo 2, called Galois field of polynomials modulo 2 , GF(2), and XORing is the addition.
The equation R1 XOR R2 =R above gives to us the permition to calculate tje CRC checksum of our message byte to byte.
so our message 1100100000101101 separated to two bytes :
11001000 00101101
11001000 XOR 1111111111111111 = 1111111100110111 (1111111111111111 Is 16 bits long).
1111111100110111 XOR 1111111111111111 =0000000011001000
SIFTING LEFT 8 PLACES THE 0000000011001000 WE HAVE : 1100100000000000 that is the polynomial x15+x14+x11 .
A shift left and shift right calculator is at:
http://www.miniwebtool.com/bitwise-calculator/bit-shift/?data_type=2&number=01101&place=1&operator=Shift+Left
A "trick" that you ,may be, have seen at various pages is the following:
Our message is the:
1100100000101101 or the x15+x14+x11+x5+x3+x2+1
and our CRC generator is the 01001111 or the x6+x3+x2+x+1 ( its degree is 6 ).
Adding 6 zeros at the original message we have a new polynomial:
1100100000101101000000
dividing it by 01001111 we find the remainder R=100010 (it is not the CRC of
1100100000101101 ).
Subtracting this remainder from the 1100100000101101000000 we have:
1100100000101101000000 XOR 100010 =1100100000101101100010 (1)
The polynomial 1100100000101101100010 is our original message 1100100000101101
"appended" at its end the CRC of the different polynomial
1100100000101101000000 , and the remainder of the division
1100100000101101100010 /01001111 is ofcourse zero due to (1).
The maximun degree of x at the remainder of a division by x6+x3+x2+x+1 is 5, it will be a polynomial 6 bits long, so the minimun number of zeros that you have to append at the original message in order to save space to "append" the remainder of the new polynomial that you produced ,in our case the 100010 , is 6, but as you understand you can append more than 6 zeros making your own design. Appending n-zeros at the end of a message it is equivalent with the multiplication of the polynomial of the original message by x^n.
Danger ! Do not mixing the Arithmetic of Galois field GF(2) with the arithmetic of the set of binary numbers. If you are mixing your results will be ...so nice !
Exercise:Proove that you can calculate the CRC of the above message ...bit by bit.
It is time to exam in detail the procedure of the division modulo2, but we have to proove the following simple theorem firstly:
given: a polynomial p of degree k, a divisor d of degree l ,we are looking for two polynomials q and r such that:
p=d*q+r , where the maximun possible degree of q will be k-l and the degree of r will be less than l.
Adding the polynomial (x^(k-l)*d we have:
p+(x^(k-l))*d=d*(x^(k-l)+q)+r since GF(2) is distributive.
in words: the polynomial p+(x^(k-l))*d diveded by d gives as a remainder the same r for that we are searching for. The degree of the new polynomial p+(x^(k-l))*d will be less than k and continue the process till to find a polynomial r having degree less than of d. This r will be the final remainder. Multiplication of d by x^(k-l) it is equivalent to append k-l zeros at the end of d.
Applying the above to our example message we have:
Our message is M=1100100000101101 or the x15+x14+x11+x5+x3+x2+1
and our CRC generator is the D=01001111 or the x6+x3+x2+x+1 ( its degree is 6 ).
Using polynomial calculator and writing down the division process step by step and in detail ,using the above proven theorem , we have:
1100100000101101 Message
1001111000000000 it is D* x^(15-6)
--------------------------
0101011000101101
100111100000000 it is D*x^8 ....
----------------------------
001100100101101
1001111000000 it is the D*X^6 .
-----------------------------
0101011101101
100111100000 D*X^5 ...
--------------------------
001100001101
1001111000 D*X^3...
----------------------
0101110101
100111100 D*X^2....
------------------
001001001
1001111
-----------
110 FINISHED !
------
110
Observe , using the calculator, that all the red polynomials divided by D all give remainder 110.
The above procedure of the calculation of CRC of a message or file by sequential XORings with polynomials of degree smaller and smaller than k includes a great advantage.There is no need to have all the message or the big file in a register of the microcontroller. We have to use the l bits only (l is the degree of the generator polynomial) of a register at each one of the sequential steps. The size in bits of the registers of a microcontroller is limited.
Manufactures of microcontroller boards prefer to enclose big files inside of memory chips like an AT29C020 flash memory or an AT28HC256 EEPROM memory chip and outside of the microcontroller integrated circuit. Manunacturers are able to modify these files throught internet with the help of a bootloader included inside of the software of the board, re-calculating and a new CRC.
As you see the procedure of the calculation of a CRC is sequential XORings starting from the most significant bit (MSB) of a byte and going to the least significant bit (LSB), the MSB of the next byte is coming... (fetching next bits are simple sifts of the byte that is fetched at r1).
Using an 8 bit register r1 of a microcontoller fetching here byte by byte our file and a register r2 to save our generator polynomial to do XORings we have:
r1----->right shift
... byte of file -----------------------> bit7.....................bit0
XOR
generator poly-----------------------> bit7......................bit0
r2
Observe that bytes are inserted to the registers r1 and r2 from the left side and the content of r1 has to be sifted right to continue the procedure of calculation.
Observe also that the MSB bit will occupy the place of bit0.
How to do it? Using a ...mirror? No, but reversing the order of bits of the byte, at both of r1 and r2.
A simple way to reverse a byte is to use a table look up like:
static const unsigned char reflect [] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};
At the followings change the word "reverse" with the word "reflect" !
For example the reverse of 0000 0001 (0x01) is the 1000 0000 (0x80) .
The final calculated CRC has to be reversed.
byte 1 byte 2
Our message is M=11001000 00101101
and our CRC generator is the D= 1001111
We will calculate the checksum byte by byte in steps , using reversed bytes in r1 and r2 registers undrer the law :
' when bit0 of r1 is 0 then shift 1 bit right, if bit0 is 1 then shift 1 bit right and after it XOR ,result in r1'
we have: byte 1 reversed 00010011 , byte 2 reversed 10110100
D reversed 111100)1 in r2 we have to put only the part 111100
we will count 8-N (about N see below at C code) right shits total and finished.
r1 00010011 --- 1-->00 001001 XOR r2= 00110101--2->00 011010
XOR r2=00 100110
r2 111100
C code example is coming.
Special topics about crc. <21/March/2015>
In order to exame the reliability of crc method we have to introduce the term of the "error polynomial" e. Polynomial e is a polynomial that is added to the original message m, so the corrupted message is m+e. As you see the places of 1 in e correspond to bit changes in m. We have the following cases:
Case 1, you have bad luck and crc(e)=0. So,
Denoting crc(m)=r we have crc(m+e)=r ok!
You can find plenty of e polynomials having crc(e)=0.
Good generator poly g are selected in such a way that binomials of the form b=x^i + x^j to be not divisible by g for small i and j, b will be divisible by g for long i and j , for example for a 16 bit generator poly i and j must be greater than 2^16. Then crc(m+b) is not equal to r and the error is caught.
Case 2, you have much more bad luck, sending to the receiver m and r at two separate steps. It , may be, was happend this:
At first step receiver receives m+e. (2)
At the next following second step receiver receives the crc remainder (r+ crc e ). (3)
We have: crc(m+e)=crc m +crc e =r+ crc e ok!
As you observe it is safe to send m and crc m in only only step , sending m+r at once, in this case crc (m+r)=0 but crc (m+r+e) is not zero.
If the order of generator poly is k we can append k zeros to m , in order to bits of m and r to be not overwiten as explained.
server and my editor problems ,sorry.!!!
======================================
C code here, one byte long message.
We will calculate the checksum in steps , using reversed bytes in r1 and r2 registers undrer the law :
' when bit0 of r1 is 0 then shift 1 bit right, if bit0 is 1 then shift 1 bit right and after it XOR and the result stay in r1'
unsigned char byte = 0xfd; //you can change the divitend here!!!-
// dividend,the message, is 0xfd
// EXAMPLES:
// byte remainder | generator poly | used reversed generator poly| PAEAMETERS: j N
// 0x9f 0x03 0x1d 0x0b 3 4
// 0xaf 0x09 ' ' ' '
// 0xc9 0x06 ' ' ' '
// 0xc8 0x07 ' ' ' '
// 0x0c 0x0c ' ' ' '
// 0x0d 0x0d ' ' ' '
// 0x1d 0x1d 0x3d 0x17 2 5
// 0xf5 0x01 ' ' ' '
// 0xf4 0x00 ' ' ' '
// 0xfd 0x09 ' ' ' '
// 0xa7 0x14 ' ' ' '
// 0xa5 0x16 ' ' ' '
// 0xb7 0x04 ' ' ' '
// 0xd3 0x1a ' '
/* The program uses two parameters j and N depended upon the number of bits of the used generator polynomial exclusively,
at STAGE (1) AND STAGE (2) of the crc8() function below.
The above results agree with the results of the polynomial calculator of GF(2) of this article above*/
The C function that we will use to find the crc is the:
unsigned char crc8(unsigned char byte) {
int j=0;
unsigned char crc;
unsigned char d=0x17; // d the rversed generator poly, the reversed divisor.
/* you can change the divisor here!!!- your crc generator polynomial.
for example if the generator poly is 0x3d, we don't need the MSB that is always 1 because this '1' is always XORed with the 'first 1' of an intermediate polynomial of the procedure giving zero - 001(1 1101- so reversing it ,in the register of the generator poly we will have the 000 1011 1 = 0x17 -so we will use in the divisor's register the 0x17 . (PARAMETER N= 5 , the number of USED bits of the divisor).
Examples:
generator poly 0x1d , in register of divisor use 0x0b ,N=4
generator poly 0x3d , in register of divisor use 0x17 , N=5 */
byte=reverse[byte];
crc=byte;
// STAGE (1)
for (j = 0;j <=2;j++ )
/* Attention here if you will change the divisor!!!
PARAMETER j controls the total number of right sfifts to find a polynomial having degree less than the degree of the devisor, total number of right shifts = 8- N ( N=number of USED bits of the divisor).we need 3 right shifts total, so j=2 . */
if (CRC0) {
{
crc=crc>>1;
crc=crc^d;
}
else crc=crc>>1;
} ;
crc=reverse[crc];
// STAGE (2)
// removing unwanted appended zeros after reversing crc
crc=crc>>3;
// Attention here if you will change the divisor!!!
// to present the reversed remainder in a right way removing
// the unwanted zeros appented to it after reversing it,
// we have to right shift it , controlling the number of right shifts (RS),
//that is RS = 8- (number of N USED bits of the divisor),
// for example if N=5 then RS=3
printf ("%c ", crc); // you can watch the final crc at the watch window of your compiler.
return crc;
}
// end of function.
where CRC0 is:
#define CRC0 ((T*)(&(crc)))->bit0
and
typedef struct
{
unsigned int bit0 : 1;
unsigned int bit1 : 1;
unsigned int bit2 : 1;
unsigned int bit3 : 1;
unsigned int bit4 : 1;
unsigned int bit5 : 1;
unsigned int bit6 : 1;
unsigned int bit7 : 1;
unsigned int bit8 : 1;
unsigned int bit9 : 1;
unsigned int bit10 : 1;
unsigned int bit11 : 1;
...
unsigned in bit15 :1;
} T;
You can watch the result at the watch window of your compiler.
At the above C code The degree of the polynomial that represent our message is seven -it is an
8-bit long polynomial -and the maximum degree of our generator poly is seven (8 bit long polynomial). If you have longer messages and longer generator polynomials (for example an eight degree generator poly-9 bits long poly), then you need...more space.
You can use unsigned integers instead of unsigned characters but the philosophy of calculation remains the ...same.
For more than one byte long message we have to append next coming bits of the next reversed byte at the end of the crc previously calculated, continueing the procedure, and reversing the final crc at the end.
Exercise: Rewrite the above program without reversing the contents of r1 and r2 registers. Message and generator poly will be inserted at r1 and r2 from the right. You have to do left shifts of r1 now. Your generator poly will be the 0x3d but you have to calculate the right value that you will put in r2 (it is not 0x3d, it is 0xe8). No need to reverse the final CRC but ...
SOLUTION
#define CRC7 ((T*)(&(crc)))->bit7
and the function is:
unsigned char crc8(unsigned char byte) {
int j=0;
unsigned char crc;
unsigned char d=0xe8; // d the poly, the divisor.
crc=byte;
for (j = 0;j <=2;j++ )
{
if (CRC7) {
{
crc=crc<<1;
crc=crc^d;
}
else crc=crc<<1;
} ;
crc=crc>>3;
return crc;
}
Example using 16 bit long registers. We will use the stantard crc8 generator x8+x7+x6+x4+x2+1 or 0x1d5 . In C code the 1) 1101 0101 0000 0000 or 0xd500 (used number of bits N=8, so j=16-8-1, 8 left shits total) and try to find the CRC of 0xca07 message.
So,
1.
#define CRC15 ((T*)(&(crc)))->bit15
unsigned int message = 0xca07;
unsigned int crc;
and
unsigned int crc8(unsigned int byte) {
int j=0;
unsigned int d=0xd500; // d the poly, the divisor.
crc=byte;
for (j = 0;j <=7;j++ )
{
if (CRC15) {
{
crc=crc<<1;
crc=crc^d;
}
else crc=crc<<1;
}
crc=crc>>8;
return crc;
}
The remainder is 0x0023 in agreement to polynomial calculator.
Next, we will try a 3 byte long message, giving the triger for a look up table driven
CRC implementation.
*Professor of Informatic at the University of Athens told me on the far past to follow university career about Informatic, but I choose career about Physics!
==================================================
<2/March/2015>
CRC look up table driven impementation.
The speed of crc calculation is very important at critical application, for example at the microcontroller board that controls the engine or the ABS module of your car.
Microcontroller has to check many times per second the content of an eeprom , checking for corrupted data.
A fast algorithm is the crc look up table driven algorithm.
When you try to calculate the crc of 0xca07 with generator poly the 0x1d5 observe that:
0xca07=0xca00 xor 0x0007
we have crc (0xca00)=0x0024
and crc(0xca07)= 0x0024 xor 0x0007=0x0023
CRC of Quantities of the form XX00 can be precalculated and saved in a look up table and using the quantity XX as an offset at the look up table.
An algo that makes this 256 long table is:
2.
static unsigned char table [256];
unsigned int i ,j t;
for (i=0;i<256;i++)
{
j=i<<8;
t=crc8(j);
table[i]=(char)t;
}
Try now to calculate the crc8 of the message 0xca 0x07 0x3a
we have table[0xca]=0x24 , 0x24 xor 0x07=0x23 , table[0x23]=0x0e, 0x0e xor 0x3a= 0x34
the final crc8, it is correct in agreement to polynomial calculator.
why this?
continued with the explanation...
Help:
Prove that given two polynomials A and B ,order of B is k and crc(A)=R THEN:
crc(AB)=crc(RB).
Proof
Observe that polynomial AB=A*(X^(k+1))+B and polynomial RB=R*(X^(k+1))+B, +=xor,
...
<---- z- zeros---->
A bit of exactness: Consider the polynomial P=A0... ...0... ...0C , where A and C are polynamials, the order of C is k, C is k+1 bits long, and crc(A)=R. A polynomial begins always with a 1.
Denoting B=0... ...0... ...0C we have:
A=d*q+R---->A*x^(z+k+1)+C=d*q*x^(z+k+1)+ R*x^(z+k+1)+C=d*q*x^(z+k+1) +RB .
----> P= d*q*x^(z+k+1) +RB
So, crc(P)=crc(RB) again.
Generally speaking the quantity B is not always a polynomial but it is a quantity constructed from 0 and 1.
This is the secret encrypted under the remainders of polynomials modoulo2: connect!
We are able now to write the equation: crc(0xca073a)= table[table[0xca]xor0x07] xor 0x3a.
A function that can calculate the crc of our message m unsigned char m[3]={0xca,0x07,0x3a};
is the:
3.
unsigned char v; // v is the crc
unsigned char crc_calculation (void) {
v=m[0];
for (i=1;i<=2;i++){
v=table[v]^m[i];
}
return v;
}
result is v=0x34 in agreement to polynomial calculator.
So, what we have in our hand for the moment is:
1. A function that calculates the crc using modoulo2 division--generator poly is d=0x1d5--,as in paragraph 1 above.
2. A function that makes a crc look up table , as in paragraph 2 above.
3. A function that calculates the crc using a look up table as in paragraph 3 above , but lets go to give a general form to it in order to be able to accept strings. The general form is:
unsigned char v; // v is the crc
unsigned char crc_calculation (unsigned char* x) {
v= *x;
for (i=1; i<= strlen(x)-1 ; i++) {
v=table[v] ^ *(x+i);
}
return v;
}
calling this function for the string unsigned char *st ="12345";
we have: crc_calculation(st)=0xbf in agreement to polynomial calculator.
Remember that the end of a string is denoted by the NULL character \0, hexadecimal 0x00,
so if you write : for (i=1; i<=strlen(x) ; i++) then the crc= 0x64, again in agreement to polynomial calculator.
...And take out your fear about CRC checksum, it is much more easier than the
Monte Carlo Statistics of Nuclear Physics ...
Searching various pages in web about crc I remembered a mistake that I had done driving my car:
Following the wrong way, a way that after some hundred of meters was ended. Astonished, I observed many cars that followed me !
Initial value in crc register. <21/March/2015>
Given the message unsigned char a[6]={0x00,0x31,0x32,0x33,0x34,0x35} it is in the form of an array. Writing a function to calculate the crc we will have:
unsigned char crc_calculation (unsigned char* m, unsigned int k) {
unsigned int i;
unsigned char v=0x00 ; // v is the crc register;
for (i=0; i<k; i++)
{
v=table[v] ^ *(m+i);
}
return v;
}
and calling this function crc_calculation (a,6);
we find crc(a)= 0xbf as above. As you see the initial value in crc register is 0x00 and the first term 0x00 of the message a does not contribute to the calculation of crc.
To overcome it, sender and receiver agree for an initial value in crc register different than 0x00, for example unsigned char v=0xff;
Doing it we have crc(a)=0x08 .
So, crc is encrypted under Mathematics. "People that don't understand how simple are Mathematics , they can't understand how complicated is the life." Von Neumann.
Books that I love, N. Piscunov , L. Elsgolts .
To admire the glory of the human thought have a look in Quantum Mechanics
A property of crc : Given a polynomial having crc(A)=r , with a generator poly d of degree eight and R is the complement of r then: crc (A+R)= crc (0xff). r and R are 8 bits long.
Proof
A= d*q+r ---> A+R=d*q+r+R -----> crc (A+R)= crc (0xff) =0xff .
Also crc ((A+R)*x^8)=crc(0xff00) . Magic, may be,...
Have in your mind that the polynomial A+R is different than the polynomial AR.
conttinued ...
Controlling the value of the crc <12/April/2015>
Given the message unsigned char a[5]={0x31,0x32,0x33,0x34,0x35} as you saw (generator poly 0x1d5) we have:
crc (a)= table[table[table[table[0x31] xor 0x32] xor 0x33] xor 0x34]xor 0x35 =0xbf
We want to calculate a new byte 0xYY such that the crc of the new message
crc b[6]={0x31,0x32,0x33,0x34,0x35, 0xYY} to be a new known value, say 0xff,
crc b[6]={0x31,0x32,0x33,0x34,0x35, 0xYY}= 0xff
we have crc b[6]= table[ crc a[5] ] xor 0xYY , so we can calculate 0xYY...
0xYY=table [0xbf] xor 0xff
Exercise : Given the message unsigned char a[5]={0x31,0x32,0x33,0x34,0x35} calculate the byte
0xYY such that the new message b[6]=]={0x31,0x32,0xYY,0x33,0x34,0x35} has a new known crc, say 0xff
crc b= 0xff , so 0xYY ?
Motivation
The solution is so simple and it will be published on the next...
If you will give the Good at the End then the End will be Good...
Solution
As you observe having a look at the elrments of the array unsigned char table[256] the function that calculates the remainders of the polynomials of the form 0xYY00 is a one to one correspondence function and therefor there is and the reverse function. We can constuct the reverse look up table unsigned char rt [256].
For example table[0x18]=0x7b, 0x18=24 decimal
and
rt[0x7b]=0x18 , 0x7b=123 decimal.
A function that can built the rt[256] look up table is the:
void reverse_table (void) {
unsigned int i,j;
unsigned char r;
for(i=0;i<256;i++)
j=i<<8;
r=(unsigned char) crc8(j);
rt [r] =(unsigned char)i;
}
And 0xff=table[table[table[table[table[0x31]^0x32] ^0xYY]^0x33]^0x34]^0x35
Observing this equation from left to right and from right to left we can see easily that:
0xYY= (rt [rt [rt[0xff^0x35]^0x34]^0x33]) ^(table[table[0x31]^0x32])
and the end: 0xYY=0xfb
The fact that the only polynomial of the form 0xYY00 that divided by the generator poly 0x1d5 gives as remainder the zero polynomial is the 0x0000 polynomial ,it is a pointer to the quality of 0x1d5. Using this fact you can prove easily that there are not two different polynomials of the form 0xYY00 having the same crc.
It is continued...
CRC16-CCITT CRC <13/April/2015>
Today I present a function that calculates a CRC16-CCITT crc. We will use unsigned long integers (32 bit long objects). Our generator polynomial is the 0x1021 , in C code we need only the 0x021 as explained above for crc8.
Since our message is 32 bit long and our divisor d=0x021 uses 12 bits the total number of left shifts is 32-12=20.
so,
#define CRC31 ((T*)(&(test)))-->bit15 //T the stucture as above
unsigned long int crc;
unsigned int test; // test is used for testing for 0 or 1 the #31 bit of the crc, it is exlpained later.
//you can use bitwise operator instead.
unsigned int crc16(unsigned long int message ) {
unsigned int j=0;
unsigned long int d=0x021
d=d<<20; // we don't want the 20 zeros in front
crc=message;
for (j=0;j<=19;j++)
{
test=crc>>16; // to test the #31 bit of crc. see the #define above.
//A warning about value truncated here but ignore it
if (CRC31)
{
crc=crc<<1;
crc=crc^d ;
}
else crc= crc<<1;
}
crc=crc>>20;
return crc;
}
We used the test variable because the T structure above accepts unsigned characters or unsigned integers only. It does not accepts unsigned long integers. So I used the "trick" of test.
Calling this function for the message 0x31323334 we have:
crc16(0x31323334)= 0x010c
This result is in agreement to polynomial calculator above.
It needs a bit of modification!
CRC16-CCITT generator poly is 0x11021 so in C code use 0x1021, left shifts are 32-16=16 and
crc=crc>>16;
and crc16(0x31323334)=0x1381 in agreement to calculator.
Continued...
CRC16-CCITT table driven implementation <19/April/2015>
So,our crc16 function is the:
unsigned int crc16(unsigned long int message ) {
unsigned int j=0;
unsigned long int d=0x1021
d=d<<16; // we don't want the 16 zeros in front
crc=message;
for (j=0;j<=15;j++)
{
test=crc>>16; // to test the #31 bit of crc. see the #define above.
//A warning about value truncated here but ignore it
if (CRC31)
{
crc=crc<<1;
crc=crc^d ;
}
else crc= crc<<1;
}
crc=crc>>16;
return crc;
}
Coming back to our message unsigned char message [4]={0x31,0x32,0x33,0x34} we can see it as a composition of two polynomial 0x(313233)0x(34) .
Remember: crc(AB)=crc(RB), where crc(A)=R.
Denoting crc (0x313233)=R we have crc (0x31323334)= crc (R 0x34)
R is a 16 bit long polynomial and (R 0x34) is a 24 bit long polynomial.
crc of quantities of the form 0xYY0000 can be precalculated and saved in a look up table.
For exampe crc (0x310000)=0x2672 and R=crc(0x313233)=crc(0x310000)+crc (0x3200)+crc(0x33)=( 0x2600+0x3200) + (0x72+ 0x33)=0x1441
Repeating the procedure for the polynomial 0x 144134 we find that the crc16 is 0x1381.
As you observe the quantity 0x26 (MSB of crc 0x310000) does an action on the 0x32 and the 0x72( LSB of crc 0x310000) on 0x33.
We can constuct one look up table t1 for the MSB and one look up tabe t2 for the LSB.
static unsigned char t1[256] and static unsigned char t2[256]
A fuction that is doing it is the:
void crc16_table (void){
unsigned int t ;
unsigned int long i;
for (i=0;i<256;i++)
{
t=crc16(i<<16);
t1[(unsigned char)i]=(unsigned char)(t>>8);
t2[(unsigned char)i]=(unsigned char) t;
}
}
A function that can calculate the crc16 using the tables t1 and t2 is the:
unsigned int crc16_table_calculator (unsigned char *m, unsigned int k) {
unsigned char a=0;
unsigned int v=0; // v the crc
unsigned int j;
for(j=0; j<=k;j++) {
v=( (unsigned int ) (t1[a]^(unsigned char) v ) ) <<8 ^( t2[a] ^ *(m+j) );
a= (unsigned char) (v>>8) ;
}
return v;
}
Calling it we have : crc16_table_calculator (message, 3)= 0x1381 as above.
for the message unsigned char message [9]={ 0x31, 0x32,0x33,0x34, 0x35,0x36,0x37,0x38,0x39}
we have : crc16_table_calculator (message ,8)= 0xbeef in agreement to calculator.
for the message unsigned char message [11]={ 0x31, 0x32,0x33,0x34, 0x35,0x36,0x37,0x38,0x39,0x00, 0x00}
we have : crc16_table_calculator (message ,10)= 0x31c3 in agreement to calculator.
A crc16 function that accepts strings is the :
unsigned int crc16_table_calculator_string (unsigned char *s) {
unsigned char a=0;
unsigned int v=0; // v the crc
unsigned int j;
for(j=0; j<=strlen(s) -1 ;j++) {
v=( (unsigned int ) (t1[a]^(unsigned char) v ) ) <<8 ^( t2[a] ^ *(s+j) );
a= (unsigned char) (v>>8) ;
}
return v;
}
Given the string unsigned char *st="1234";
we have: crc16_table_calculator_string (st)=0x1381
You can observe the performance of crc16 table driven implementation using the performance analyzer of your compiler.
Controlling the value of CRC16-CCITT <25/April/2015>
Exercise 1 : Given the message unsigned char message [4]={0x31,0x32,0x33,0x34} find the bytes 0xYY and 0xZZ such that the new message unsigned char b [6]= {0x31,0x32,0x33,0x34,0xYY,0xZZ} has a given crc16, say 0xffff.
crc16(b)= 0xffff, so 0xYY and 0xZZ ?
Solution
crcb= crc(crc(message)0xYYZZ)=crc ((0x1381YY)(0xZZ))
denoting p= (t1[0x13]^0x81)<<8^(t2[0x13]^0xYY) =0xa300^(0x52^0xYY)=
=0x a3(0x52^0xYY)
we have: crc (b)= (t1[0xa3]^0x52^0xYY)<<8 ^ (t2[0xa3]^0xZZ)=(0xd7^0xYY)<<8 ^ (0x89^0xZZ)
so 0xff=0xd7^0xYY and 0xff =0x89^0xZZ These are because in Galois field XOR's are permited only, addition with carry is forbiten and it is meaningless.
and the end : 0xYY= 0x28 and 0xZZ=0x76
and
unsigned char b [6]= {0x31,0x32,0x33,0x34,0x28,0x76}
verification : crc16_table_calculator (b, 5)= 0xffff
Exercise 2 : Modify the function crc16_table_calculator in such a way that it shall calculate the crc of a piece of the unsigned char message[9].
My experience! Studying various files that are included in memory integrated circuits mounted on microcontroller boards I found that there is no need to know the generator polynomial in order to recalculate a new crc afrer the modifications that you have done in the file. You can recalculate the new crc using SHIFT's and XOR's only.
Initial value in CRC16-CCITT register. <28/April/2015>
A bit of modification :
A function that can calculate the crc16 using the tables t1 and t2 is the:
unsigned int v;
unsigned int crc16_table_calculator (unsigned char *m, unsigned int k) {
unsigned char a=0x00;
unsigned int v=0xffff ; // v the crc
unsigned int j;
for(j=0; j<=k;j++) {
a= (unsigned char) (v>>8) ;
v=( (unsigned int ) (t1[a]^(unsigned char) v ) ) <<8 ^( t2[a] ^ *(m+j) );
}
return v;
}
The initial value in crc16 register is 0xffff .
For the message : unsigned char message [6]={0x00,0x00, 0x31,0x32,0x33,0x34}
We have :
unsigned int crc16_table_calculator (message,5)=0x1d91
For initial value in crc16 register the 0x0000 we have :
unsigned int crc16_table_calculator (message,5)=0x1381 as previous.
Performance Analyzer crc16 example <3/May/2015>
Example : Constucting a message unsigned char message [100] ; like
do{
message [j]=(char)j;
j++;
}while (j<100);
we have :
unsigned int crc16_table_calculator (message,99)=0xc5d2 , initial value 0x0000.
The passed time t of calculation is about 63 μsec with a clock running at 40MHZ.
For the message:
do{
message [j]=(unsigned char)j;
j++;
}while (j<200);
and initial crc16 value the 0xffff
we have: unsigned int crc16_table_calculator (message,199)=0xc440 and t=125 μsec .
A faster CRC16-CCITT look up table driven implementetion <29/May/2015>
Avoiding intermediate SHIFT's we can use the following faster function:
unsigned char v1, v2;
unsigned int crc16_table_calculator_faster (unsigned char *m , unsigned int k) {
unsigned int v; // v the crc
unsigned int j;
unsigned char z=0x00;
v1=0xff; //initial value in crc register
v2=0xff; // initial value in crc register
for(j=0;j<=k;j++){
v2=t1[v1]^v2;
z=t2[v1]^*(m+J);
v1=v2;
v2=z;
}
return v=v1<<8^v2;
}
As you saw using your performance analyzer for the message:
do{
message [j]=(unsigned char)j;
j++;
}while (j<200);
and initial crc16 value the 0xffff
we have: crc16_table_calculator (message,199)=0xc440 and t=125 μsec .
for the same message we have now:
crc16_table_calculator_faster (message,199)= 0xc440 and t= 90 μsec.
It is possible an UART (ASC0 for xc164cm ) to transmit a message starting from bit 0 and finishing at bit 7 for each one of the bytes of the message. We say that the transmitted message has been reflected. For example the reflect of 0x01 is 0x80, for the 0x02 is 0x40 and so on. You can find above an array with the reflected bytes from 0x00 to 0xff.
An example of a reflected message is the:
do{
r_message [j]= reflect [(unsigned char)j];
j++;
}while (j<200);
The procedure of the calculation of the crc of this message is exactly the same as the one described already. Simply, close your eyes and imagine that you are living in a reflected world.
So, our two look up tables rt1 and rt2 will be:
unsigned int t;
void crc16_reflect_table (void) {
unsigned int long i;
for (i=0;i<256;i++){
t=crc16(i<<16);
rt1[ reflect[(unsigned char)i] ] =reflect [(unsigned char)(t>>8)];
rt2[ reflect[(unsigned char)i] ] =reflect [(unsigned char)(t)];
}
}
Where the crc16 function is ,as previus, the:
unsigned int crc16(unsigned long int message ) {
unsigned int j=0;
unsigned long int d=0x1021
d=d<<16; // we don't want the 16 zeros in front
for (j=0;j<=15;j++)
{
test=crc>>16; // to test the #31 bit of crc. see the #define above.
//A warning about value truncated here but ignore it
if (CRC31)
{
crc=crc<<1;
crc=crc^d ;
}
else crc= crc<<1;
}
crc=crc>>16;
return crc;
}
The function that calculates the crc of the r_message using the tables rt1 and rt2 is the :
unsigned int v;
unsigned int crc16_r_table_calculator (unsigned char *m, unsigned int k) {
unsigned char a=0x00;
unsigned int v=0xffff ; // v the crc, initial value 0xffff
unsigned int j;
for(j=0; j<=k;j++) {
a= (unsigned char) (v>>8) ;
v=( (unsigned int ) (rt1[a]^(unsigned char) v ) ) <<8 ^( rt2[a] ^ *(m+j) );
}
return v;
}
Calling it we have:
crc16_r_table_calculator (r_message,199)=0x2302
Coming back to the real world reflecting each one of the two bytes by hand we have:
The crc of the original message (with no reflection ) is 0xc440 .
crc32 ...
Now I am sure that you already know that you need four look up tables for a crc32 look up table driven implementation ...
A nice place for Summer holidays, the Greek historical island Samos, the island that born Mathematics 2.500 years ago , the place of my birth,
Pythagoreon of Samos
CRC32 <10/AUGUST/2015>
Today I am presenting a crc32 modulo2 division algorithm, selecting as divisor the polynomial
d=0x0104c11db7.
In C code we need the 0x04c11db7.
I start with a five bytes long message and using one r1 register- unsigned long int r1- to save the first four bytes of the message and an r2 register -unsigned char r2-to save the LSB of the message.
The laws of computation of crc32 are:
"when the bit31 of r1 is 1 shift r1 one place left, after it equate bit0 of r1 to bit7 of r2,after it XOR r1 with d and the crc32 is the content of r1"
"when the bit31 of r1 is 0 shift r1 one place left, after it equate bit0 of r1 to bit7 of r2, and the crc32 is the content of r1"
We use a 40 bits long place (r1 and r2 together) to save the message and 32 bits used by the divisor so the total number of left shifts is 40-32=8.
To equate bit0 of r1 to bit7 of r2 we need the help of an unsigned int transfer, ORing transfer with crc32.
To test bit31 of r1 we need the help of an unsigned int test as for crc16 above.
The C code is :
#define crc32_bit31 ((T*)(&(test)))->bit15
#define transfer_bit0 ((T*)(&(transfer)))->bit0
#define r2_bit7 ((T*)(&(r2)))->bit7
unsigned long int r1;
unsigned char r2;
unsigned long int d=0x04c11db7; //the crc32 divisor
unsigned long int crc32;
unsigned int test;
unsigned int transfer;
unsigned long int crc_32 (unsigned long int r1, unsigned char r2);
unsigned long int crc_32 (unsigned long int r1 , unsigned char r2 ) {
crc32=r1;
for (j=0;j<=7;j++)
{
test=crc32>>16
if (crc32_bit31)
{
crc32=crc32<<1;
transfer=0x0000;
transfer_bit0=r2_bit7;
crc32=crc32|transfer;
crc32=crc32^d;
r2=r2<<1;
}
else {
crc32=crc32<<1;
transfer=0x0000;
transfer_bit0=r2_bit7;
crc32=crc32|transfer;
r2=r2<<1;
}
}
return crc32;
}
Example: For the message 0x3132333435 we have r1=0x31323334 and r2=0x35 .
crc32 (0x3132333435)=crc_32 (unsigned long int r1 , unsigned char r2 ).
The result is : crc32=0xE2C04412 in agreement to polynamial calculator above.
continued...at nice Greek sea..swimming...
CRC32 TABLE DRIVEN IMPLEMENTATION <16/AUGUST/2015>
Following the philosophy of table driven implementation about crc16 above we have to construct four look up tables calculating the crc of polynomials of the form 0xYY00000000 .
A function that is doing it is the:
void table_crc32 (void);
unsigned char t1[256]
unsigned char t2[256]
unsigned char t3[256]
unsigned char t4[256];
void table_crc32 (void){
unsigned long int j;
unsigned long int tt;
r2=0x00;
for (j=0;j<256;j++){
tt=crc_32(j<<24,r2);
t1[ (unsigned char) j]=(unsigned char)(tt>>24);
t2[ (unsigned char) j]=(unsigned char)(tt>>16);
t3[ (unsigned char) j]=(unsigned char)(tt>>8);
t4[ (unsigned char) j]=(unsigned char)(tt);
}
}
Example: We will use tables t1,t2,t3 and t4 to calculate the crc32 of the message 0x3132333435 .
A funtion that is doing it is the:
void __crc32(void);
unsigned long int _crc32;
void __crc32(void) {
unsigned char a ;
a=0x31;
_crc32= (((unsigned long int)(t1[a]^0x32))<<24) ^ (((unsigned long int)(t2[a]^0x33))<<16)\
^(((unsigned long int)(t3[a]^0x34))<<8)^ (t4[a]^0x35);
}
Calling it as __crc32(); we have:
crc32(0x3132333435)=0xE2C04412 as previus.
Continued at the beach under the sun with juice...
more CRC32 functions comming soon...
CRC8 ERROR CORRECTION. <29/AUGUST/2015>
Today I start to show you the power of crc check in the field of the error correction. For simplicity we begin with a crc8 and an error that occured at one bit only.
So , suppose that the sender sent a message a and crc8(a)=v1.
The receiver receives an error message e, the error is at one bit only.
What the reciever received are: the e and v1.
Now the receiver calculates the crc8 and finds crc8(e)=v2, v2 is different than v1.
Writing down some simple mathematics we have:
a=d*q1+v1 , e=d*q2+v2 .
Adding these equations by parts we have:
a+e=d*(q1+q2)+ (v1+v2), order of the polynomial v1+v2 is lower than the order of d.
so, crc8(a+e)=v1+v2, v1+v2 is known.
Since the error occured at one bit only The polynomial a+e is a polynomial of the form : 1 or 10... with unknown number of zeros, the number of bytes of the message a+e will be equal to the number of bytes of message e .
But knowing that crc8(a+e)=v1+v2 and knowing and the form of the polynomial a+e it is easy to write C code to construct the polynomial a+e. Knowing a+e and e we can calculate the a.
An example is ready...
Example: The sender sent the message
unsigned char a [5]={ 0x31,0x32,0x33,0x34,0x35} having v1=0xbf and the receiver receives the message
unsigned char e [5]={ 0x31,0x12,0x33,0x34,0x35} having crc8(e)=v2.
The program calculates the polynomial a+e denoting it by x and having crc8(x)=v1+v2 and after it calculates the original message.
the program is:
unsigned char v1, v2, er;
unsigned char e [5]={ 0x31,0x12,0x33,0x34,0x35} ;
unsigned char x [5]={ 0x00,0x00,0x00,0x00,0x00} ;
unsigned char original [5];
void correct (void);
void main(void)
{
// USER CODE BEGIN (Main,2)
// USER CODE END
MAIN_vInit();
//make the crc8 table
for (i=0;i<256;i++)
{
j=((unsigned int)i)<<8;
t=crc8(j);
table[i]=(char)t;
}
correct (); // find the difference
//calculate the original message
for (i=0;i<5;i++) {
*(original+i)=*(e+i)^*(x+i);
}
while(1);
}
The used functions are the:
1)
Make crc8 modoulo2 division
unsigned int crc8(unsigned int byte) {
int j=0;
unsigned int d=0xd500; // you can change the divisor here!!!- your crc generator polynomial.
crc=byte;
for (j = 0;j <=7;j++ )
{
if (CRC15)
{
crc=crc<<1;
crc=crc^d;
}
else crc=crc<<1;
}
crc=crc>>8;
return crc;
}
2)
Calculate crc8 using table
unsigned char crc_calculation (unsigned char * m, unsigned int k)
{
unsigned char v ;
v=0x00;
for (i=0; i< k ;i++)
{
v=table[v]^*(m+i);
}
return v;
}
3)
Calculate the difference
void correct (void){
unsigned char i ,j, v3;
i=0;
j=0;
v1= 0xbf ; // v1 the crc8 of the right message
// v1= crc_calculation (a,5);
v2= crc_calculation (e,5) ; //v2 the crc8 of the wrong message
er=v1^v2; // er is the difference of crc8
for (i=0;i<5;i++) {
*(x+i)= (*(x+i)) +1;
for (j=0;j<8;j++){
v3=crc_calculation (x,5); // v3 the crc8 of an intermediate polynomial
// for comparison to er
if ( !(v3^er)) {
break;
}
else
*(x+i)= (*(x+i)) <<1;
}
if ( !(v3^er))
break; // finished
}
}
continued...
|
