The Hamming Code
Consider a message having four data bits (D) which is to be transmitted as a 7-bit codeword by adding three error control bits. This would be called a (7,4) code. The three bits to be added are three EVEN Parity bits (P), where the parity of each is computed on different subsets of the message bits as shown below.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| D | D | D | P | D | P | P | 7-BIT CODEWORD |
| D | - | D | - | D | - | P | (EVEN PARITY) |
| D | D | - | - | D | P | - | (EVEN PARITY) |
| D | D | D | P | - | - | - | (EVEN PARITY) |
For example, the message 1101 would be sent as 1100110, since:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 7-BIT CODEWORD |
| 1 | - | 0 | - | 1 | - | 0 | (EVEN PARITY) |
| 1 | 1 | - | - | 1 | 1 | - | (EVEN PARITY) |
| 1 | 1 | 0 | 0 | - | - | - | (EVEN PARITY) |
It may now be observed that if an error occurs in any of the seven bits, that error will affect different combinations of the three parity bits depending on the bit position.
For example, suppose the above message 1100110 is sent and a single bit errors such that the codeword 1110110 is received:
transmitted message received message
1 1 0 0 1 1 0 ------------> 1 1 1 0 1 1 0
The above error can be corrected by examining which of the three parity bits was affectd by the bad bit:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | ||
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 7-BIT CODEWORD | |
| 1 | - | 1 | - | 1 | - | 0 | (EVEN PARITY) | NOT! |
| 1 | 1 | - | - | 1 | 1 | - | (EVEN PARITY) | OK! |
| 1 | 1 | 1 | 0 | - | - | - | (EVEN PARITY) | NOT! |
The value of the Hamming code can be summarized:
The ability to correct single bit errors comes at a cost which is less than sending the entire message twice. (Recall that simply sending a message twice accomplishes no error correction.)
