A Hamming code is a method for detecting and correcting errors in a binary transmission. It does so through the inclusion of additional binary digits in the sequence that are used for checking, as well as an algorithm that provides the detection logic. Such a code is capable of finding two errors in any sequence of bits and repairing one bit that may be incorrect. The most commonly referenced Hamming code is known as the Hamming(7,4), where the four indicates the original number of starting bits and the seven represents the total number of bits in the sequence after the additional checking bits have been included.
The technique got its name from its creator, Richard Hamming, who published the method in 1950. The way the Hamming code works is by taking a string of bits and inserting additional checking bits, referred to as parity bits, into the sequence. The checking bits are always injected at a position that is a power of two, so any number of bits can be verified by including additional parity bits. This may continue until the last parity bit added into the sequence is in a position that is a power of two which is less than or equal to the final position in the sequence.
With all of the parity bits in place, the remaining positions are the actual data bits. Given the four-bit example, then, bit positions one, two, and four would be the parity bits, while positions three, five, six, and seven are the data. Once this sequence has been established, the logic of the Hamming code goes to work.
In a Hamming code, each of the parity bits that have been added to the sequence are used to check some of the bit positions they are close to, including themselves. The parity bit in position one checks every other bit position, which is essentially every odd-numbered position in the sequence. The second parity bit, in position two, checks positions two and three, then skips two positions, checks two more positions, skips two more, and so on. If there is a parity bit in position four, it acts similarly in that it checks positions four through seven, then skips four positions, checks four more, and onward. Every parity bit in the sequence continues in this manner throughout the entire sequence.
The process by which a Hamming code detects and corrects an error is by adding up the bits in the checking sequence for each parity check, each of which must come out an even number. Given the seven-bit example, for the first parity check, bits one, three, five and seven are added up. If the total is an even number, the parity checks out, but if the total is odd, then there is an error. Since the parity checks overlap, two such errors will show up. When the two-parity bit positions that fail to come up with even totals are added together, it will reveal the bit that needs to be corrected.
In the seven-bit Hamming code example, consider that the bit in position number five is incorrect. The sum of the bits in positions one, three, five, and seven will come out as an odd number, as will the sum of the bits in positions four through seven. This indicates that parity checks for the checking bits in positions one and four failed. When one and four are added together, the total is five, which is the position for the incorrect bit in the transmission that needs to be corrected.
