How do we communicate digital information reliably in the presence of noise? Hamming's (7,4) error correction code demonstrates how parity bits can help us recover from transmission/storage errors. This must be taken into account when thinking about Shannon's idea of channel capacity and information rate. (hamming code, error correction)
Transcript
Alice and Bob have figured out an amazing trick. They're exchanging messages by plucking a wire either hard or soft to transmit a zero versus a one. However, due to gusts of wind, false zeros or ones can occur during transmission, resulting in errors. Though they 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. At the Bell Telephone Laboratories, we do about 10% of the experiments on a computer, and about 90% in the laboratory. Highly expected 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 versus zero with hole versus 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. So 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 it 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 can 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. Now, these circles intersect to produce four regions, and the four data bits are placed inside these regions in a specific order. Now, 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 is one for odd. And 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 character 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. And this is Alice and Bob's trick, the additional parity bits are known as redundant bits, because they don't carry any new information. And all air 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 correcting 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, and this must then decrease the effective amount of information you can send per unit time.