CYCLIC REDUNDANCY CHECK

CRC (Cyclic Redundancy Check) 

The error checks on telecomunication systems use two methods: 

1)      Character Mode which adds one redundancy bit to the sending data

2)     Block Mode which adds a redundancy block of n bit to the sending data

 In the Block mode, used in the syncronous trasmision, the most important method is the CRC (Cyclic Redundancy Check).
 This method is characterizated by the fact to add at the end of the sending data a n bit block where n is 12 or 16 ( CRC-12 o CRC-16) on the basis of the generator polynomial choosed. This added bits are the coefficient of the rest polynomial due to the divison of the sending data and the generator polynomial g. The recipient must to run the same algorithm to check the rigth of the data, so the polynomial g must be the same for the trasmiter and recipient. There are some standard polynomials: 

Below a matematical discussion about the CRC is made.

Consider a n bit word ( bn-1,….bo) and fix the polynomial g(x)  which have a degree g £ n-1

At the polynomial b(x), correspondent to the ( bn-1,….bo), is added a block of g bit which are the coefficients of the rest polynomial r(x) due to the divison between b(x) and  g(x).   
The first step is to add g bit zero to the end of the sending data. This is equivalent to multiplier b(x) with  x^g . We have the poynomial p(x): 

p(x)= x^g * b(x) 

so p(x) can be written as function of g(x) where q(x) and r(x) are the quozient and the rest of the division between p(x) and g(x). 

            p(x)=q(x)*g(x)+r(x); 

Then, the sending block  is the merge between ( bn-1,….bo) and a block of g bit ( rg-1, r0).  This is equivalent to substitute in p(x) the g bit with the bit of the ( rg-1, r0).Using the binary mathematic, this operation is equal to the XOR function. The data to send can be written:  

            m(x) = p(x) + r(x) = q(x)*g(x)+r(x) +r(x) = q(x)*g(x) 

being  r(x) +r(x) = 0 ( xor  property) 

m(x) is perfectly divisible for g(x). This means that the recipient, excuting the division between m(x) and g(x),  have a rest r(x)=0 if there are not error. 
The success of this technique is due to its efficiency but to the easy implemetation hardware.  
It needs XOR logic gate and shift register for hardware implementation.  

It is possible to write CRC routines for micro as described at the  link