/    /  CDCS – Cyclic Redundancy Checking

Cyclic Redundancy Checking

CRC stands for cyclic redundancy checking and is one of the error detection techniques. It is based on binary division. The CRC generator is an algebraic polynomial represented as a bit pattern, the bit pattern is obtained using the following rule:

The power of each term gives the position of the bit and the coefficient gives the value of the bit.

 

Properties of the CRC Generator:

The algebraic polynomial should have the following properties:

  1. It should not be divisible by x, this helps guarantee that all the burst errors of length equal to the length of the polynomial are detected.
  2. It should be divisible by x+1, this guarantees that all the burst errors affecting an odd number of bits are detected. 

 

If it follows all the rules then:

  1. It will be able to detect all single-bit errors.
  2. It will be able to detect double-bit errors provided the divisor contains at least three logic 1s.
  3. It will be able to detect most of the larger burst errors with a high probability.
  4. It will be able to detect all burst errors of length less than the degree of the polynomial.
  5. It will be able to detect any odd number of errors provided the divisor is a factor of x+1.

 

The steps involved:

Step 1: At the sender’s side, a string of n 0’s is appended to the data unit to be transmitted. The n will be one less than the number of bits in the CRC generator. After that the binary division is performed of the resultant string with the CRC generator. After the division, the remainder is obtained called CRC. 

 

Step 2: As the CRC has been obtained the string of 0s is appended to the data unit earlier is replaced by the CRC remainder. 

 

Step 3: The codeword is transmitted to the receiver. 

 

Step 4: At the receiver’s end the transmitted codeword is received, which is then divided with the same CRC generator. Then a remainder is observed.

There can be two causes for the remainder:

Case1: Remainder=0

If the remainder is zero, then the receiver assumes that there is no error.

 

Case2: Remainder \= 0

If the remainder is not equal to zero, then the receiver assumes that some error has occurred during the transmission. 

 

Reference