# coding theory

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.