In the previous tutorial, we have studied about checksum through examples and its performance. In this tutorial, we will study the final error detection technique – Cyclic Redundancy Check (CRC).

What is Cyclic Redundancy Check?

Cyclic Redundancy Check (CRC) is another error detection technique to detect errors in data that has been transmitted on a communications link. A sending device applies a 16 or 32 bit polynomial to a block of data that is to be transmitted and appends the resulting cyclic redundancy check (CRC) to the block. The receiving end applies the same polynomial to the data and compares its result with the result appended by the sender. If they agree, the data has been received successfully. If not, the sender can be notified to resend the block of data.

At Sender Side

• Sender has a generator G(x) polynomial.
• Sender appends (n-1) zero bits to the data.
  Where n= no of bits in generator
• Dividend appends the data with generator G(x) using modulo 2 division (arithmetic).
• Remainder of (n-1) bits will be CRC.

Codeword: It is combined form of Data bits and CRC bits i.e. Codeword = Data bits + CRC bits

Example

Assume that –
(a) data is 10110.
(b) code generator is 1101. (Code generator can also be mentioned in polynomial : $ x^3+x^2+1 $)

Note – Code generator is always mentioned in the question.

Calculate CRC Bits:

Now, we will see how to calculate CRC bits using above data.

While calculating the CRC bits, we pad (n-1) 0’s to the message bits, where ‘n’ = no of bits in the code generator.

In the above code, code generator is 1101. So, there is total 4 bits. So, we will append 000 with the data.

Finally, Cyclic Redundancy check will be generated as shown below –

CRC calculation by sender

Cyclic redundancy check is 101. Thus, the sender sends 10110101 to the receiver.

At Receiver Side

• Receiver has same generator G(x).
• Receiver divides received data (data + CRC) with generator.
• If remainder is zero, data is correctly received.
• Else, there is error.

Assume the received message is 10110110.

Calculate CRC Bits:

It does not add any padding bits, rather calculates from the entire received code word.

CRC calculation by receiver

The CRC bits are calculated to be different. Thus, there is an error detected.

CRC Rules:

• CRC generator should not contain ‘x’.
• If (x+1) is generator, it can detect odd no of error.
• If generator is xn, then last n bit errors can be detected.

Performance of Cyclic Redundancy Check

CRC is a very effective error detection method. If the divisor is chosen according to the above mentioned rules,

• CRC can detect all burst errors that affect an odd number of bits.
• CRC can detect all burst errors of length less than or equal to the degree of the polynomial.
• CRC can detect with a very high probability, burst errors of length greater than the degree of the polynomial.

Thus, we are now acquainted with all the error detection and correction techniques. We have read about the hamming code, parity check, Checksum method and cyclic redundancy check method. In the next tutorials, we will study about the various switching methods used for communication and data transmission in computer networks.

[latexpage]