If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains ***.kastatic.org** and ***.kasandbox.org** are unblocked.

Main content

Current time:0:00Total duration:5:25

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 at one however due to gusts of wind false zeros or ones can occur during transmission resulting in airs 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% experiments on a computer in about 90% in laboratory highly expected in time we will do 90% on the computer and 10% in 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 whole versus no hole this system was error-prone because it was common for cards to get bent or miss 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 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 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 7/4 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 error occurs two or more of the parity bits will be incorrect and wherever they intercept 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 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 use 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 you