Coding theory is the branch of mathematics concerned with transmitting data across noisy channels and recovering the message. Coding theory is about making messages easy to read and is thus not to be confused with cryptography, which is the art of making messages hard to read!

 

The basic problem is that messages, in the form of binary digits or bits (strings of 0 or 1) have to be transmitted along a channel (such as a telephone line) in which errors occur randomly, but at a predictable overall rate. To compensate for the errors, more bits need to be transmitted than are in the original message.

 

The simplest method for detecting errors in binary data is the parity code, which transmits an extra parity bit after every 7 bits from the source message. However, this method can only detect errors: the only way to correct them is to ask for the data to be retransmitted. A simple way to correct as well as detect errors is to repeat each bit a set number of times. The recipient sees which value, 0 or 1, occurs more often and assumes that to be the intended bit. This scheme can tolerate error rates up to 1 error in every 2 bits transmitted at the expense of increasing the amount of repetition. The disadvantage of the repetition scheme is that it multiplies the number of bits transmitted by a factor that may prove unacceptably high.

 

In 1948, Claude Shannon, at Bell Labs, started the whole subject of coding theory by proving the minimum number of extra bits that had to be transmitted to encode messages. Unfortunately his proof didn't give any explicit recipes for finding these optimal codes. Two years later, Richard Hamming, also at Bell Labs, published details of his work on explicit error-correcting codes with information transmission rates more efficient than simple repetition. His first code, in which four data bits were followed by three check bits, allowed not only the detection but the correction of a single error. (The repetition code would require nine check bits to achieve this.) It's said that Hamming invented his code after several attempts to punch out a message on paper tape using the parity code. "If it can detect the error," he complained, "why can't it correct it!"

 

While Shannon and Hamming were working on information transmission in the US, John Leech devised similar codes while working on group theory at Cambridge University. This research also included work on the sphere packing problem and culminated in the amazing, 24-dimensional Leech lattice, the study of which proved crucial to understanding and classifying finite symmetry groups.

 

The value of error-correcting codes for information transmission, both on Earth and from space, was immediately apparent, and a wide variety of codes were constructed that achieved both economy of transmission and error-correction capacity. Between 1969 and 1973 the NASA Mariner probes used a powerful Reed-Muller code capable of correcting 7 errors out of 32 bits transmitted, consisting now of 6 data bits and 26 check bits. A less obvious application of error-correcting codes came with the development of the compact disk on which the signal is encoded digitally. To guard against scratches and similar damage, two interleaved codes that can correct up to 4,000 consecutive errors are used. By the late 1990s the goal of finding explicit codes that reach the limits predicted by Shannon's original work had been achieved.