Main content

## Modern information theory

# Error correction

## Video transcript

Voiceover: Alice and Bob have
figured out an amazing trick. They are exchanging
messages by plucking a wire either hard or soft, to
transmit a zero vs. a one However due to gusts of
wind, false zeros or ones can occur during transmission,
resulting in errors. Though they've figured out a way to communicate error-free, even in the presence of noise. How could they do this? In the 1940s, Richard Hamming faced a similar problem, while working at Bell Laboratories. Richard: At the Bell
Telephone Laboratories, we do about 10% of the
experiments on a computer, and about 90% in the laboratory. I expect that in time, we
will do 90% on the computer, and 10% in the lab. Speed, cost, and effort favor the computer over the laboratory approach. At the time, the computers
used stored information on punch cards, representing one vs. zero with hole vs. no hole. This system was error
prone, because it was common for cards to get bent or
mis-punched in the first place. So holes could be missed, or no holes could be
accidentally punctured, causing flipped bits. These errors would cause
the entire system to halt, until the error location could be found and corrected manually. Hamming took it upon
himself to devise a method which could automatically
detect and correct single bit errors, without
interrupting calculations. His solution was rooted in the intuitive idea of repetition, something we all do when
faced with interference, or the chance that part of
our message will be corrupted. His error-correcting codes were built on the simple concept of a parity bit. A parity bit is a single bit which is added to the end of a message, and indicates whether the number of ones in the message is even or odd. If a single error occurs, the receiver could then detect it, because the parity bit
will no longer match. However to detect and
correct single errors, Hamming needed to add more parity bits to identify the error location. This leads to his seven-four code, which adds three parity bits to each block of four data bits as follows. First we start with the three parity bits, which can be represented by a circle. These circles intersect
to produce four regions. The four data bits are
placed inside these regions in a specific order. To calculate the parity bits, we look at each circle one at a time, each containing three data bits. We determine the parity bit as before. Add up the data bits, and
if we get zero or two, the parity bit is zero for even, and if we get one or three, the parity bit is one, for odd. We do this for all circles, and end up with three parity bits to match the four data bits. These are then placed in a standard sequence as follows. Realize now, this system
can automatically correct single errors with a simple rule. If a single error occurs, two or more of the parity
bits will be incorrect, and wherever they intersect is the location of the error. This intersecting data bit is
then flipped automatically, so that all parity bits are valid again. This is Alice and Bob's trick. The additional parity bits are known as redundant bits, because they don't carry
any new information. All error-correction codes work this way. They all increase the size of the source messages slightly, at the expense of automatically
correcting errors. We also use error correction
codes for storage, for example on a physical CD, the information is encoded
using special codes, to correct for chunks of errors caused by scratches or dust, which corrupt longer
sequences of zeros and ones stored on the surface. This is why you can scratch a CD and often it will still play perfectly. Claude Shannon used
this idea of redundancy to redefine the capacity
of a communication channel, because as the noise on
your channel increases, we must increase the amount of redundancy to communicate error-free. This must then decrease
the effective amount of information you can send per unit time.