  |
||||||||
|
CRC |
||||||||
|
Cyclic
Redundancy Check (CRC)
One of the
most common and one of the most powerful, error-detecting codes is
the cyclic redundancy check (CRC). CRC is base on binary division
and use of polynomial codes. CRC can detect any odd number of errors,
all 2-bit errors, and ‘burst error’ up to length < no. of redundancy
bits. CRC is also more complicated than parity or checksums, but can
be implemented quickly in hardware (so therefore very useful).
The redundancy bits used by CRC are derived by dividing the
data unit by a predetermined divisor; the remainder is the CRC. To
be valid, a CRC must have two qualities: it must have exactly one
less bit then the divisor, and appending it to the end of the data
string must make the resulting bit sequence exactly divisible by the
divisor.
Both the theory and the application of CRC error detection are straightforward.
The only complexity is in deriving the CRC. In order to clarify this
process, there provide an outline of the three basic steps shown on
figure 1. Figure 1: CRC generator and checker
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. If
the string arrives without error, the CRC checker yields a remainder
of zero and the data unit passes. If the string has been changed 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. Figure 2 shows this
process. 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 our example, the divisor, 1101, is subtracted
from the first four bits of the dividend, 1001, yielding 100 (the
leading 0 of the remainder is dropped off). The next unused bit from
the dividend is then pulled down to make the number of bits in the
remainder equal to the number of bits in the divisor. The next step,
therefore, is 1000-1101, which yields 101, and so on.
In this process, the divisor always begins with a 1; the divisor
is subtracted from a portion of the previous dividend/remainder that
is equal to it in length; the divisor can only be subtracted from
a dividend/remainder that’s leftmost bit is 1. Anytime the leftmost
bit of the dividend/remainder is 0, a string of 0s,
of the same length as the divisor, replaces the divisor in that step
of the process. For example, if the divisor is four bits long, it is replaced by four 0s. This restriction means that, at any step, the leftmost subtraction will be either 0 – 0 or 1 – 1, both of which equal 0. So, after subtraction, the leftmost bit of the remainder will always be a leading zero, which is dropped off, and the next unused bit of the dividend is pulled down to fill out the remainder. Note that only the first bit of the remainder is dropped – if the second bit is also 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. Figure 2: Binary division in a CRC generator
The CRC Checker A CRC checker functions exactly like the generator. After receiving the data appended with the CRC, it does the same modulo-2 division. If the remainder is all 0s, the CRC is dropped and the data accepted; otherwise, the received stream of bits is discarded and data are resent. Figure 3 shows the same process of division in the receiver. We assume that there is no error. The remainder is therefore all 0s and the data are accepted. Figure 3: Binary division in CRC checked
Polynomials
The CRC generator (the divisor) is most often represented not
as a string of 1s and 0s,
but as an algebraic polynomial (shows Figure 4). The polynomial format
is useful for two reasons: it is short, and it can be used to prove
the concept mathematically. Figure 4: A polynomial
The relationship of a polynomial to its corresponding binary
representation is shown in Figure 5. Figure 5: A polynomial representing a division
A polynomial should be selected to have at least the following properties:
(a) It should not be divisible by x. (b) It should be divisible by ( x + 1 ). CRC is a very effective error detection method. If the divisor is chosen according to the previously mentioned rules: (a) CRC can detect all burst errors that affect an odd number of bits. (b) CRC can detect all burst errors of length less than or equal to the degree of the polynomial. (c) CRC can detect with a very high probability burst errors of length greater than the degree of the polynomial. |
||||||||
