Section 4.5. Error Detection and Correction | Computer and Communication Networks (paperback)

4.5. Error Detection and Correction

Error sources are present when data is transmitted over a medium. Even if all possible error-reducing measures are used during the transmission, an error invariably creeps in and begins to disrupt data transmission. Any computer or communication network must deliver accurate messages.

Error detection is applied mostly in the data-link layer but is also performed in other layers . In some cases, the transport layer includes some sort of error-detection scheme. When a packet arrives at the destination, the destination may extract an error-checking code from the transport header and perform error detection. Sometimes, network-layer protocols apply an error-detection code in the network-layer header. In this case, the error detection is performed only on the IP header, not on the data field. At the application layer, some type of error check, such as detecting lost packets, may also be possible. But the most common place to have errors is still the data-link layer. Possible and common forms of errors at this level are described here and are shown in Figure 4.5.

Figure 4.5. Common forms of data errors at the data-link level

White , or Gaussian , noise is continuous and is dependent on the temperature of the medium. White noise might change the content of data, as seen in the figure. White noise can be removed by passing the noisy signal through a set of filters.
Spike noise is not continuous but may completely obliterate the data, so that it cannot be recovered.
Cross talk is a coupling action between two active links. Coupling can be electrical, as between two sets of twisted-pair wire, or electromagnetic, as when unwanted signals are picked up by an antenna.
Echo is the reflecting impact of a transmitted signal. A signal can hit the end of a cable and bounce back through the wire, interfering with the original signal. This error occurs in bus-type LANs. A one-directional filter, known as an echo canceler , can be attached to a link to eliminate echo.
Jitter is a timing irregularity that shows up at the rises and falls of a signal, causing errors. Jitter can result from electromagnetic interference or cross talk and can be reduced by proper system shielding.
Bit attenuation is the loss of a bit's strength as it travels though a medium. This type of error can be eliminated with the use of amplifiers and repeaters for digital systems.

No link is immune to errors. Twisted-pair copper -based media are plagued by many types of interference and noise. Satellite, microwave, and radio networks are also prone to noise, interference and cross talk. Fiber- optic cable too may receive errors, although the probability is very low.

4.5.1. Error Detection Methods

Most networking equipment at the data-link layer inserts some type of error-detection code. When a frame arrives at the next hop in the transmission sequence, the receiving hop extracts the error-detection code and applies it to the frame. When an error is detected , the message is normally discarded. In this case, the sender of the erroneous message is notified, and the message is sent again. However, in real-time applications, it is not possible to resend messages. The most common approaches to error detection are

Parity check
Cyclic redundancy check (CRC)

The parity check method involves counting all the 1 bits in the data and adding one extra bit, called the parity bit . This makes the total number of 1 bits even (even parity) or odd (odd parity). The parity-check method is the simplest error-detection technique but is not effective. The cyclic redundancy check (CRC) method is one of the most elaborate and practical techniques but is more complex, adding 8 to 32 check bits of error-detection code to a block of data. Our emphasis is CRC.

At this point, we need to clarify that the Internet checksum is another error-detection method, though it is used at the network and transport layers and is discussed in Chapters 7 and 8.

4.5.2. Cyclic Redundancy Check (CRC) Algorithm

The cyclic redundancy check (CRC) method provides smart error checking and has been adopted in most computer and communication systems. Figure 4.6 shows error detection and correction on links, using CRC for a transmitter.

Figure 4.6. Error detection on links using the CRC method at a transmitter

In any system, a standard and common value between transmitters and receivers is adopted for error processing. This g -bit-long value, known as a checking generator , is denoted by G . At the transmitter, a partial or entire packet or frame is treated as a block of data, and each block is processed individually. The CRC algorithm at the transmitter part can be summarized as follows .

Begin CRC Algorithm at Transmitter

A string of g - 1 zero bits is appended to the incoming data, D . We call this new block D ,0s.
D ,0s as a dividend is divided by the generator G acting as the divisor. The division is of type modulo-2 .
The quotient of this division is discarded, but the remainder is called CRC.
The CRC value is appended to the data, producing D , CRC.

At the other end point of the communication system, the receiver receives the value of D , CRC and performs the following algorithm to detect errors, as shown in Figure 4.7.

Figure 4.7. Error detection on links, using CRC at a receiver

Begin CRC Algorithm at Receiver

D , CRC, as a dividend, is divided by the same generator G acting as the divisor used by the transmitter. The division is of type modulo-2 .
The quotient of this division is discarded, but if the remainder is 0, the receiver knows that the data has no errors; otherwise , the data is not accepted, as it contains one or more errors.

The modulo-2 division arithmetic is very simple. A modulo-2 division function is done without carries in additions or borrows in subtractions . Interestingly, the module-2 division function performs exactly lke the Exclusive-OR logic. For example, with modulo-2 arithmetic, we get 1 + 1 = 0 and 0 - 1 = 1. Equivalently, with logic Exclusive-OR: 1 1 = 0, and 0 1 = 1.

Example.

Assume that 1010111 as a block of data ( D ) is going to be transmitted using the CRC error-checking method. Suppose that the common value of the generator, G , is 10010. Produce the final value that the transmitter sends on the link ( D , CRC), and show the detail of the error-detection process at the receiver.

Solution.

At the transmitter, clearly, the number of 0s needed to be appended to D is four ( g - 1 = 4), since the generator has 5 bits ( g = 5). Figure 4.8 (a) shows the details of the CRC process at the transmitter side. Since D = 1010111, D ,0s = 1010111 0000 , the dividend. The divisor is G = 10010. Using modulo-2 arithmetic, the quotient turns out to be 1011100, and the remainder is CRC = 1000. Therefore, the transmitter transmits D , CRC = 1010111,1000. At the receiver, as shown in Figure 4.8 (b), D , CRC = 1010111,1000 is treated as the dividend and is divided by the same divisor, G = 10010. Since the remainder in this case is 0, the receiver learns that there is no error in the data and can extract the data.

Figure 4.8. Modulo-2 division for the CRC process shown for a transmitter and a receiver

The CRC algorithms are fairly straightforward. Consider again the example. A fact from the modulo-2 arithmetic states that the remainder is always ( g - 1) bits long; therefore, for this example, the remainder is 4 bits long. Hence, if we make sure that g - 1 additional 0s, or four 0s in the example, are at the end of the dividend, the receiver can perform an identical arithmetic in terms of size of dividend. If the transmitter produces a remainder, let's say 1,000, the addition of this value to the same data can indeed result in 0 remainder, provided that the data is the same data used in the transmitter. Therefore, if there is any error during transmission, the remainder may not become 0 at the receiver, giving a notion of error.

Equivalent Polynomial Interpretation

The preceeding analogy can be restated such that the CRC error-detection method treats the data to be transmitted as a polynomial. In general, consider the bit string a _n _-1 a _n _-2 a _n _-3 ... a , which forms a generic polynomial:

a _n _-1 x ⁿ ^-1 + a _n _-2 x ⁿ ^-2 + a _n _-3 x ⁿ ^-3 +...+ a x ,

where a _i can be 0 or 1. In other words, when a data bit is 1, the corresponding polynomial term is included. For example, the bit string D = 1010111 produces the string a ₆ a ₅ a ₄ a ₃ a ₂ a ₁ a = 1010111, which is interpreted as

x ⁶ + x ⁴ + x ² + x ¹ + x .

The generator value, acting as the divisor, is known as the generating polynomial in this case. Some well-known and widespread industry-approved generating polynomials common divisor between transmitters and receiversused to create the cyclic checksum remainder are:

CRC-8 for ATM: x ⁸ + x ² + x + 1

CRC-12: x ¹² + x ¹¹ + x ³ + x ² + x + 1

CRC-16: x ¹⁶ + x ¹⁵ + x ² + 1

CRC-CCITT: x ¹⁶ + x ¹⁵ + x ⁵ + 1

CRC-32 used in IEEE 802:

x ³² + x ²⁶ + x ²³ + x ²² + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1

Note that the polynomial interpretation is simply a convenient method of explaining the CRC algorithm. In practice, the transmitter and the receiver perform divisions in bits, as described earlier.

Effectiveness of CRC

The CRC method is pretty goof-proof. However, an analysis is needed to answer whether the receiver is always able to detect a damaged frame. Consider the generating polynomial x ^g ^-1 + x ^g ^-2 + ... + 1 with g terms. Apparently, g - 1 is the highest power of the generating polynomial. Let n be the length of burst error occurring in a received message. If the size of the error burst is n<g , error detection is 100 percent. For all other cases, the terms between x ^g ^-1 and 1 define which bits are erroneous. Since there are g - 2 such terms, there are 2 ^g ^-2 possible combinations of erroneous bits. Considering that all combinations can occur with equal probability, there is a chance of that a combination exactly matches the terms of the polynomial. This is the probability of a damaged bit becoming undetected. The probability of catching such error bursts through CRC for all cases is

Equation 4.10

Example.

Consider a computer communication standard based on CRC-CCITT defined earlier. For this standard, the highest power of the polynomial is g - 1 = 16. If the error burst n is less than g = 17 bits in length, CRC detects it. Assuming that n = g = 17:

which is close to 1.

Implementation of the CRC Process Unit

Hardware with a combination of software performs the process of division very quickly. An example of the basic hardware used to perform the CRC calculation is shown in Figure 4.9. The hardware includes a simple register that implements the CRC process-generating polynomial x ⁴ + x + 1. Except for the first term ( x ⁴ ), an Exclusive-OR is included for each power of existing term, as shown. Note that the notion of the generator value 10010 is now appearing in the form of hardware shown by a combination of 1-bit shift registers and Exclusive-OR gates. Therefore, we can see from the figure where there is a term in the generating polynomial.

Figure 4.9. CRC process: The most significant bit enters first.

Initially, the registers contain 0s. All data bits of 1010111, 0000 , beginning from the most-significant bit, arrive from the left, and a 1-bit shift register shifts the bits to the right every time a new bit is entered. The rightmost bit in a register feeds back around at select points. At these points, the value of this feedback bit is Exclusive-ORed, with the bits shifting left in the register. Before a bit shifts right, if there is an Exclusive-OR to shift through, the rightmost bit currently stored in the shift register wraps around and is Exclusive-ORed with the moving bit. Once all data bits are fed through, the register's contents must be exactly the same as the remainder indicated in Figure 4.8 (a).