12.5. Hamming (7,4)

The Hamming (7,4) code consists of code “words” that are seven bits long. Four of those bits–the 3rd, 5th, 6th, and 7th–are used to convey a message and the remaining three are check digits. This means that better than 50% of the transmission is message and errors can still be corrected, compared with only 33% if bits are simply repeated. The words are:

0000000, 1101001, 0101010, 1000011, 1001100, 0011001, 1100110, 0001111, 1110000, 0100101, 1011010, 0110011, 0111100, 1010101, 0010110, 1111111

Examine any pair of words, for example 0001111 and 1000011 and we will see that the words differ in at least three bits. So at least three errors would have to occur simultaneously before a mistake could go undetected. Also, if one error occurs the incorrect word will be closer to one of the correct words than any of the others. Therefore, Hamming (7, 4) can detect up to two errors and correct one error.

The three check digits are parity bits that are calculated according to the following rules:

For example, examine the code word, 1000011. The check digits are in red. The first check digit is the XOR of the 3rd, 5th, and 7th. Let’s imagine that this there is an error in this digit, and we receive the transmission 0000011. Only the first test fails, therefore the error must be in the first check digit. We change this digit to a 1 and, voilà, we have corrected the error. If we receive the transmission 1010011 then both the first and second test fail, then the error must be in the 3rd digit. If all three tests fail, then the error must be in the 7th digit. Finally, if the first and third tests fail then the error must be in the 5th digit.

The system is not perfect. What will happen if there is an error in two bits? Again, consider the message 1000011. But this time, a transmission error in the 4th and 5th bits causes the message to be rendered as 1001111. The first test fails: . We conclude that the first digit must be in error and we correct it. Now the message is: 0001111. What have we done? We have inadvertently piled an error onto two previous errors. We think we have corrected the code, but we have not. We could add an additional parity bit and such a code, unsurprisingly called Hamming (8, 4), does exist but the trade-off of decreased efficiency is evident.