Math 511, Error Correcting Codes

Error Correcting Codes

Parity checks give us a way to detect if an error has occurred in recording a byte of data. But often just knowing that an error has occurred isn't sufficient; you want to know what the error was and how to fix it. Richard Hamming at Bell Labs was having a problem with parity errors in the 50's while working at Bell Labs. Because the only computer (back in the 50's computers weren't household items) was busy with high priority projects during the week, Hamming could only submit his jobs to be run over the weekend. For several weeks, each Monday when he came in he got the message that the program had terminated with a parity error and to please try again. Of course, trying again meant waiting till the next weekend. Hamming thought there had to be a way to set things up to use parity to correct a single error, rather than just detecting it. He worked out a method to do just that, now called the Hamming code.

The (7,4) Hamming code uses four data bits and three parity bits (for a total of seven bits). Suppose the data bits are b₁b₂b₃b₄. We set the parity bit p₁₂₃ so b₁b₂b₃p₁₂₃ has even parity. Then we set the parity bit p₁₂₄ so b₁b₂b₄p₁₂₄ has even parity. Finally we set the parity bit p₁₃₄ so b₁b₃b₄p₁₃₄ has even parity. We then encode our results as b₁b₂b₃b₄p₁₂₃p₁₂₄p₁₃₄. We can write this in terms of matrices as

where the computation is done mod 2.

Let's look at an example. Suppose our four data bits are 0110. Then we compute the parity bits p₁₂₃ = 0, p₁₂₄ = 1, and p₁₃₄ = 1, and we get our seven-bit result 0110011. To test this sequence for errors, we check the parity of the sets b₁b₂b₃p₁₂₃, b₁b₂b₄p₁₂₄, and b₁b₃b₄p₁₃₄, which in this case are 0110, 0101, and 0101 respectively. Since all three have even parity, we detect no errors. Now suppose an error changes our seven-bit sequence to 0111011. This time when we look at the sets b₁b₂b₃p₁₂₃, b₁b₂b₄p₁₂₄, and b₁b₃b₄p₁₃₄, we get 0110, 0111, and 0111 respectively. Since two of these have odd parity, we detect an error. Looking at which sequences have errors, we see that we have detected no error in b₁b₂b₃p₁₂₃, but we have detected an error in b₁b₂b₄p₁₂₄, and b₁b₃b₄p₁₃₄. Assuming that there is only a single error (which we hope is more likely than there being two errors), we can conclude that the error is in bit b₄, since it is the only bit that is in both sets b₁b₂b₄p₁₂₄ and b₁b₃b₄p₁₃₄ but not in b₁b₂b₃p₁₂₃. So we switch bit b₄ in the errant sequence 0111011 from a 1 to a 0 to get back to the correct seven-bit sequence 0110011. Extracting the four data bits, we finally get 0110, which is what we started this paragraph with.

Since every bit, both data and parity, is in at least one of the sets b₁b₂b₃p₁₂₃, b₁b₂b₄p₁₂₄, and b₁b₃b₄p₁₃₄, any change in a single bit will foul up at least one of the three parity checks. On the other hand, since no two bits are in exactly the same parity checks, we can always determine which single bit was changed by examining which parity checks fail.