Page 109 - DCAP406_DCAP_207_Computer Networks

Computer Networks/Networks

Notes First, a string of numbers 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 bit.

Second, 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.
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 treats the
whole string as a unit and 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 changed in transit, the division yields a non-zero remainder and the
data unit does not pass.

Figure 7.5

The CRC Generator

A CRC generator used modulo-2 division, Figure shows the 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, 1101. Yielding
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

102 LOVELY PROFESSIONAL UNIVERSITY