Error Detection

Cyclic Redundancy Check (CRC)

Method for checking the accuracy of a digital transmission over a communication link. The sending computer performs a calculation on the data and attaches the resulting value; the receiving computer performs the same calculation and compares its result to the original value. If they do not match, a transmission error has occurred and the receiving computer requests retransmission of the data.

In CRC, instead of adding bits together to achieve a desired parity, a sequence of redundant bits, called CRC or the CRC remainder, is appended to the end of a data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number.

At its destination, the incoming data unit is divided by the same number. If at this step there is no remainder, the data unit is assumed to be intact and is therefore accepted. A remainder indicates that the data unit has been damaged in transit and therefore must be rejected.

Application of theory error detection are straightforward. The only complexity is in deriving the CRC.

First, a string of n 0s is appended to the data unit. The number n is one less than the number of bits in the predetermined divisor, which is n + 1 bits.
Second, the newly elongated data unit is divided by the divisor using a process called binary division. The remainder resulting from this division is CRC.
Third, the CRC of n bits derived in step 2 replaces the appended 0s at the end of the data unit. Note that the CRC may consist of all 0s.
The data unit arrives at the receiver data, first followed by the CRC. The receiver treat the whole string as a unit divides it by the same divisor that was used to find the CRC remainder
If the string arrives without error, the CRC checker yields a remainder of zero and the data unit passes. If the string has been change in transit, the division yields a nonzero remainder and the data unit does not pass.

The CRC Generator

A CRC generator uses modulo-2 division. In the first step, the four-bit divisor is subtracted from the first four bits of the dividend. Each bit of the divisor is subtracted from the corresponding bit of the dividend without disturbing the next higher bit.

In the process, the divisor always begins with a 1; divisor is subtracted from a portion of the previous dividend/remainder that is equal to it length; the divisor can only be subtracted from a dividend/remainder whose leftmost bit is 1. Anytime the leftmost bit of the dividend/remainders is 0, a string of 0s, of the same length as the divisor, replaces the divisor in the step process. This restriction means that, at any step, the leftmost subtracted will be either 0-0 or 1-1, both of which equal 0. So, after subtracted, the leftmost bit of the remainder will always be a leading zero, which is drop off, and the next unused bit of the divided is pulled down to fill out the remainder. Note that only the first bit of the remainder is drop, if the second bit is 0, it is retained, and the dividend/remainder for the next step will begin with 0. This process repeats until the entire dividend has been used.

The CRC Checker

A CRC checker functions exactly like the generator. After receiving the data appended with the CRC, it does the same module-2 division. If the remainder is all 0s, the CRC is dropped and the data is accepted; otherwise, the received stream of bits is discarded and data are resent.

Polynomials

The CRC generator (the divisor) is most often represent not a string of 1s and 0s, but as an algebraic polynomials. the polynomials format is useful for 2 reasons:
1)  It is short.
2)  It can used to prove the concept mathematically.

A polynomials should be selected to have at least the following properties:

• It should not divisible by x.
• it should be divisible by (x+1).
The first condition guarantees that all burst errors of a length equal to the degree of the polynomials are detected. The second condition guarantees that all burst errors affecting an odd number of bits are detected.

Performance

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

 1) CRC can detect all burst errors that affect an odd number of bits. 2) CRC can detect all burst errors of length less than or equal to the degree of the polynomials. 3) CRC can detect with a very high probability burst errors of length greater than the degree of the polynomials.