About this video
The video explains how Richard Hamming, frustrated by errors in punch-card computers, built codes that automatically detect and correct single-bit errors. A parity bit records whether the number of ones is even or odd; Hamming's seven-four code adds three parity bits to four data bits using overlapping circles, so a single error can be located and flipped. All error-correction codes add redundancy, which is why scratched CDs still play, and Shannon showed noisier channels need more redundancy, lowering effective capacity.
You'll be able to
- calculate a parity bit for a group of data bits.
- explain how Hamming's seven-four code locates and corrects a single error.
- explain the trade-off between redundancy and the amount of information sent.
Key words
- flipped bit
- An error where a 0 becomes a 1 or a 1 becomes a 0.
- parity bit
- An extra bit added to a message showing whether the number of ones is even (0) or odd (1).
- seven-four code
- Hamming's code that adds three parity bits to every four data bits, making seven bits in total.
- redundant bits
- Extra bits, like parity bits, that carry no new information but help catch or fix errors.
- error-correction code
- A way of encoding data with redundancy so errors can be automatically detected and fixed.
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.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.