Better to know some
... than all
No physical medium can guarantee error-free transmission of data. Errors occur because of interference from the environment surrounding the transmission medium or because of artifacts introduced by the equipment or the medium itself. In case of copper wires, for example, thermal noise, electrical noise, and impulse noise are some of the most common causes.
The most important role of the data link layer is to provide error-free transmission. To do this, it uses an error checking scheme to detect errors, and overcomes them by retransmitting corrupted frames. Many different error detection methods have been devised. We will discuss two popular methods in this section: parity checking and cyclic redundancy code.
Parity checking is a simple error detection method used with characteroriented protocols. One bit in every character bit sequence is reserved for parity. This bit is set by the transmitter to 0 or 1 so that the total number of 1 bits in the character is always even (in case of even parity checking) or always odd (in case of odd parity checking). The receiver checks the parity bit of each character to see if it is as expected. Parity checking is effective in detecting an odd number of bit errors in a character (single bit errors represent the most common case). If an even number of bits in a character are corrupted then this will go unnoticed, because the parity bit will seem correct.
Cyclic Redundancy Check (CRC) is a more sophisticated method used with bit-oriented protocols. It is also called the polynomial code - so named because it treats the single bits in a bit sequence as the coefficients of an imaginary polynomial. For example, the bit sequence 101001 represents the polynomial: 1x5 + 0x4 + 1x3 + 0x2 + 0x1 + 1x0 = x5 + x3 + x0
This polynomial is said to be of order 5, because its highest-order term is x5. CRC relies on the use of a generator polynomial, the choice of which is fairly arbitrary, except that the high and low order bits of its bit sequence must be 1 (e.g., 10111 is acceptable, but 0101 and 10110 are not) and that the transmitter and the receiver must use exactly the same generator polynomial. CRC works as follows. Given a message (bit sequence) m represented by the polynomial m(x), and a generator polynomial g(x) of order k, m is appended with exactly k zero bits. The result is equivalent to the polynomial p(x) = xkm(x). p(x) is divided by g(x) and the remainder is added to p(x) to produce the final polynomial q(x): q(x) = p(x) + (p(x) rem g(x))
It follows that q(x) is divisible by g(x). The transmitter calculates q using m and g and then transmits q instead of m. If any of the bits in q are changed due to transmission errors, q(x) has a very high probability of no longer being divisible by g(x). This is checked by the receiver to detect transmission errors. If there are no errors, the receiver extracts m from q (by discarding the k low-order bits) and this will be identical to the original message. The polynomial calculation procedures described above serve only as a conceptual model. In practice, equivalent binary operations are used instead. The binary operations are surprisingly simple, to the point that the whole process is usually implemented in hardware. Calculating q involves the following steps:
1. Given a bit sequence m and a generator polynomial bit sequence g of order k, append m with exactly k zero bits to produce bit sequence p. For example: m = 100101110101 g = 10111 (k = 4) p = 1001011101010000
2. Divide p by g, using modulo 2 arithmetic, to produce a remainder r. Modulo 2 arithmetic operations are similar to binary operations, except that there are no borrows or carries. Addition and subtraction in modulo 2 are identical to the binary exclusive or operation.
The effectiveness of CRC depends to a large extent on the choice of the generator polynomial. In practice, polynomials of order 16 are widely used. Hence 16 bits (two octets3) are needed for storing the remainder, which appears as the checksum field in the frame. Such polynomials are more than 99% effective in catching a variety of errors.