Richard Hamming developed procedures to not only detect, but also correct errors in computer codes. Let us see how!

The relay computer used by Hamming detected an error by computing a check digit. For example, the string 1011 was entered as 10111 where the last digit, the check digit, is the remainder when the sum of the digits is divided by 2; here (1+0+1+1)/2 is 1. As a consequence there were so called legal (say 10111) and illegal (say 00111) strings. Note that in an illegal string the last digit does not equal the correct remainder. In 1946 the occurrence of an illegal string meant the computer rejected the entire program.

To be able to correct an error the computer needed more than just one check digit. Hamming started to experiment with repeating the string, entering 10111011. Now a mistake such as 11111011 could be detected, but it could have come from the legal strings 10111011 or 11111111. Hamming perceived that in some sense the legal strings were still too close together. Repeating the string 3 times spread out the illegal code words and allowed for correction of a single error (check for yourself) but it also added lots of redundancy!

So Hamming decided to calculate three remainder check digits; let 1011=abcd, so a=1, b=0, c=1 and d=1, and remainders r of (a+b+d)/2, s of (a+c+d)/2 and t of (b+c+d)/2 will form the check digits. Now legal strings took the form r s a t b c d. So for 1011, r=0, s=1 and t=0 and 0110011 was a legal string. When checking, the computer calculated the three remainders of (r+a+b+d)/2, (s+a+c+d)/2 and (t+b+c+d)/2; if any were non-zero the computer recognised that at least one mistake had occurred. What is clever is that Hamming showed that if one mistake had occurred, the computer could correct it, because if the remainders were 0, 0, 1 then t was incorrect, 0, 1, 0 indicated an error in s; 0, 1, 1 indicated an error in c; 1, 0, 0 indicated an error in r; 1, 0, 1 indicated an error in b; 1, 1, 0 indicated an error in a; 1, 1, 1 indicated an error in d. So the computer could correct an error!

See if you can correct the error in 0110111