Cyclic Redundancy Check (CRC)
Cyclic Redundancy Check (CRC) is one of the most powerful errors detecting codes. It is based on binary division. In this technique, a set of redundant bits that are known as CRC Remainder.
Given a k-bit block of data the transmitter generates an n-bit sequence that is known as Frame Check Sequence (FCS), the resulting frame consisting of (k+n) number of bits is exactly divisible by some predetermined number (divisor). The receiver divides the incoming bits by the same predetermined number and if there is no remainder then it is assumed to be error free, otherwise, there is an error in the data.
Steps of CRC generation :
1. M = k-bit message
F = n-bit FCS
P = (n+1)-bit pattern or Predetermined Number
2. M is multiplied by 2n to form 2nM
3. 2nM is divided by P to get the remainder R
4. R is added to 2nM to form T, T=2nM+R .
5. T is transmitted.
Steps of CRC Checking :
1. P = (n+1)-bit Predetermined Number
2. Incoming data (T) is divisible by P to get the remainder R
3. If R=0 then there is no error, otherwise there must be error in the data.