Error detection and correction

As we have noted, it is not reasonable to assume that information transmitted from A to B or to anywhere else will arrive unchanged. Some mechanism must be implemented to detect and correct errors. There are a variety of successful approaches to doing this, and most are like compression in that they use algorithms to analyze the data—either to detect errors or to both detect and correct them. The algorithms, like those for compression, vary in their accuracy. Not surprisingly, the most accurate are the most complex.

Basic Error Detection/Correction

An example of a low accuracy algorithm is parity checking. In this approach, each bit in a byte is summed to see whether the byte's total is odd or even; if it is even, a 0 is added to the end of the byte; if odd, a 1 is added. This means that a byte now becomes nine bits. After the sender performs the calculation and adds the bit, the receiver does the same calculation and, if the parity bit is wrong (the final bits don't match), signals an error. Parity checking is by no means foolproof; two errors in a byte could yield a falsely positive or falsely negative result. Nevertheless, parity is used extensively in computers—most who have used desktop computers are familiar with parity in memory (high reliability systems use a more sophisticated approach known as ECC).

A better approach, cyclical redundancy checking (CRC), improves on parity checking in two ways. First, it uses a much more complex algorithm, one that divides the value of the bits by a fixed number, yielding a whole number and a remainder. The remainder is attached to the data and the receiver repeats the division and compares its remainder to the one appended to the data. It is extremely unlikely that this process will fail to determine whether an error exists or that it will be fooled into thinking one is there when it isn't. Second, CRCs perform their analysis on collections of bytes at one time; in communications, these collections are called packets, frames, or blocks. The CRC approach is not only more accurate, it is more efficient because it doesn't add as much overhead as parity (information in packets that is not user data is called overhead).

What do you do when an error is detected? This depends on the nature of the communications being used. If you are sending data, such as banking transactions, across a wire or other medium, then the best approach is to have the receiver detect errors and, if they are found, to ask the sender to send again (in fact, in many systems, the receiver must acknowledge the successful receipt of each packet or group of packets). This can go on until the packet is received correctly or until sender and receiver realize something is seriously wrong and try to reconnect.

By the way, you'll want to adjust the type of error checking to the medium. If you have a noisy medium, one in which corrupted data is common (ordinary telephone lines would be an example of this), you'll be well advised to put data into relatively small packets. Thus, if a packet contains errors and has to be resent, the amount of data to be retransmitted won't be that great. Also, recall that buffers are important—packets or frames have to be held in an input buffer long enough for the receiver to analyze them, and the sender has to hang on to the original (technically, it's a copy that is sent) in an output buffer until it knows that it has been received successfully.

Forward Error Detection/Correction

A television receiver can't wait for information to be resent. Even a little bit of sending and resending could make for a very jerky picture. Surprisingly, there is an answer for these real-time applications—forward error correction (FEC). FEC works by building packets that include two kinds of additional data—error detection information of the kind described above and redundant data that can be used to fill in the blanks when errors are found. The amount of overhead (additional bits) required for FEC depends on the noise potential of the medium. Direct broadcast satellites might add as much as thirty percent or so of FEC overhead, while in digital cable television 10 percent or less would be more common. Whatever is required, errors do occur in broadcasting and FEC is absolutely essential. Note that FEC is inherently lossy; it does happen that the needed data isn't available. The receiver then has the choice of displaying an inaccurate image or dropping the frame entirely. Television systems choose the latter course. You've probably been watching television when the set gives off the sound of static but the screen, instead of showing a distorted image, seems to freeze for a second or so. This ragged action means that the receiver has dropped some defective frames, leaving the last good one on for fraction of a second until the next good one arrives. When you see this digital artifact on a normal analog TV, it's because the interference with the digital image occurred somewhere upstream—probably in a digital satellite link between the network headquarters and the local station.