Cyclic Redundancy Check (CRC)
One of the most common, and one of the most powerful of the redundancy checking technique is the Cyclic Redundancy Check (CRC). Parity check and Longitudinal redundancy check are based on addition, while CRC is based on binary division. CRC can be described as follows. Given a data or message (k-bit block of bits), the transmitter generates an n-bit sequence, so that the sender can transmit the k + n bits, which is exactly divisible by some predetermined number. The receiver checks the data unit (k + n bits). The data unit is divided by a predetermined number, and if there is no remainder, then there is no error.

An illustration of the process is given below:
Step 1:  A string of n Os is appended to the data unit. The number n is less than the number of bits in the predetermined divisior, which is n + 1 bits.
Step 2: The newly elongated data unit is divided by the divisor using a process called binary division. The remainder resulting from this division is the CRC.
Step 3: The CRC of n bits derived in Step 2 replaces the appended Os at the end of the data unit. Note that the CRC may consist of all Os.
Step 4: The data unit arrives at the receiver data first, followed by the CRC. The receiver treats the whole string as a unit and divides it by the same divisor that was used to find the CRC remainder.
Step 5:  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 non-zero remainder and the data unit does not pass.

In the first step, the four-bit divisior (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 bits in the divisor. The next step, 1000 - 1101, yields 101, and so on.

In this process, the divisor can only be subtracted from a dividend/remainder whose leftmost bit is one. Anytime the leftmost bit of the dividend/remainder is 0, we must use 0000 instead of the original divisor. This restriction implies that at any
step, the leftmost subtraction will be either 0 - 0 or 1 - 1 both of which equal 0. This process repeats until the entire dividend has been used. Here, the CRC is 001. Figure 3.13 illustrates the CRC checker like CRC generator. The sender sends the data plus CRC to the receiver, after receiving the data appended with CRC (see Figure 3.11). Here, the bit-divisor (1101) is the same as in CRC generator. If the remainder is all Os, the CRC is dropped and the data accepted; otherwise the data will be rejected.

BACK