Feature Column from the AMS

Digital Revolution (Part III) - Error Correction Codes

6. Error-correction technologies

The basic principle behind applying digital technologies is to break up a picture or a sound into small parts, and use a binary string to represent each of these small parts. The binary strings are often chosen to achieve some additional goal such as to compress the information involved or to correct errors that might be caused by noise when the information is sent over a noisy channel.

For example, the pixels (picture elements) in the image below could be sent over a channel by coding a white pixel with 000000, a black pixel with 111111 and a gray pixel with 000111. If the receiver knows the size of the image, in this example, 7x7, and that the pixels are being sent row by row in order of increasing column number, then the picture can be accurately decoded if not too many errors occur during the transmission process.

A crude pixel image of a person with three gray levels

The Hamming distance between any pair of code words is at least 3, so if no more than one error is made when any code word is transmitted, then received codewords can be checked and if errors have occurred, they can be corrected so that the original image can be reconstructed. Using the table in the previous section, one can send a picture with 8 gray levels and still use code words of length 6 while being able to correct up to one error per code word. If one needed to use 16 gray levels, one can use the code based on the Fano Plane (Hamming's code), which would correct up to one error per codeword.

Among the very earliest users of error correction technologies were the nascent computer industry and the phone industry. For example, data is moved around often within a computer. To prevent errors occurring in some of these situations, computer memory systems use Hamming codes to prevent errors. With the birth of the space program, NASA (current name) became a major user and developer of error correction code technologies. The payloads on early rockets were limited because the lifting power of the rockets was not that great. Payloads were miniaturized and every effort was to get the maximal amount of "function" for the smallest amount of weight. The radios (and mircowave transmitters) that were used to transmit information back to earth had relatively low power, which meant that the signals that were received, when subjected to the noise that accompanies radio transmissions, often were not as strong as would have been desired. To help overcome this reality, the information was encoded using an error correcting code so as to improve the accuracy of reconstructing the signal that was sent.

The Mariner spacecraft mission successfully took photographs (without color) of Mars in 1965. The images were 200x200 with each pixel being assigned one of 64 brightness levels (six bits). Since the data was transmitted at about 8 bits per second (!), transmission of a single picture took about 8 hours. By the time Mariner 9 went into orbit around Mars in 1972, much better pictures were being obtained. This was because the spacecraft used a Reed-Muller code having 6 information bits and 26 additional bits to provide error correction (the code words were 32 bits long). Although transmission speed now was up to about 16000 bits per second, the individual images were larger, and so about 100000 bits per second were being acquired by the cameras. This meant that the images were stored for transmission. By the time Viking landed on Mars in 1976 the technology had improved so that color pictures were being obtained. The early approach to doing this was to take separate images of the same location using filters of three different colors. The separate black and white images obtained through each filter were transmitted and then a color image reconstructed from the information in the three black and white images.

NASA has used many different error correcting codes. For missions between 1969 and 1977 the Mariner spacecraft used a Reed-Muller code. The noise these spacecraft were subject to was well approximated by a "bell-curve" (normal distribution), so the Reed-Muller codes were well suited to the situation. A Golay code was used on the flight to Jupiter and Saturn by Voyager 2. A Reed-Solomon code was also used on a Voyager mission. NASA, however, also used convolutional codes for some of its work. The different kinds of missions that NASA conducts suggest the problem in trying to get a "one size fits all" error correction system. For missions close to the earth the nature of the "noise" that must be faced is different from that on a spacecraft headed towards the outer planets. In particular, if a transmitter on a spacecraft far from earth is operating at a low wattage, the problem with controlling for noise gets larger with distance from the earth.

Compact discs are an example of a technology that is rapidly changing the way we live. There are audio compact discs and those that are used in conjunction with computers. Although some of the systems used in these technologies are proprietary, it is known that Reed-Solomon codes are used for some compact discs.

There are also error correcting codes which do not employ the idea of separate codewords of the same length, where the code word has information symbols and some other symbols present for the error correction capability. For example, convolutional codes can be thought of as sending information as a stream of symbols where "check symbols" are entered into the stream being sent from time to time. The output from the encoder of a message divided into k-tuples depends not only on the current k-tuple being processed but also on some of the prior message k-tuples. The output from pieces are longer than the input pieces to incorporate the error correction capability. Some of these codes are Turbo codes.

The nascent computer industry was an early user of error correction codes and technology. Another major application of the use of error correction codes has been for modems, the devices that allow computers to receive and transmit data by use of telephone lines or fiber optic cable. Systems for error correction are needed for satellite communications systems; there are many patents involved in this area. These technologies include DARS (digital audio radio services) and SDARS (satellite digital audio radio services). Other technologies using error correction systems are fax machines and HDTV (High Definition Television). There is little doubt that the use of error correction technologies will continue to nurture and expand the digital revolution.