Hamming Codes
10/2026
During a Belgian parliamentary election in 2003, an electronic voting system gave a candidate 4,096 extra votes. Investigators noticed that this discrepancy of 4,096 is exactly 212, evidence of a flipped bit. This error was unable to be reproduced, leading investigators to believe that the flip was caused by a cosmic particle hitting a bit in the computer’s RAM.
In 1947, flipped bits were more often caused by failures in mechanical relay switches. Richard Hamming, a mathematician at Bell Labs, would often encounter these errors when using a relay computer. To solve these he devised a clever system. Using Hamming codes, a computer (or a person) can take a 255 bit message and find a single bit of error just by looking at it, reserving only 8 bits for correction. Does designing such a task seem impossible? By the end of this, it will seem quite straightforward.
There were a few error detection methods up to that point. Hamming knew that if the error could be detected, then with a bit more information you could locate the error. If you could locate it, then you simply flip the bit. This is error correction.
The error detection method he built on was the parity check. In a parity check, the total amount of 1s in the message gets counted. If the total contains an odd number of 1s, then an additional parity bit is set to 1. If the message contains an even number of 1s, then the parity bit gets set to 0. This guarantees the total number of 1s is always even.
In order to detect the presence of an error, you simply need to count the number of 1s.
Try for yourself
Note: You may be thinking that this falls apart when more than one error is introduced, but we will worry about that later.
Now if you were to add a parity check to only one half of the message, you can now localize the error to a given location.
As you can see, we can be sure when the error is in the bottom half. But with only one “parity block” you can’t determine if an error is in the other half, it could be there or it could be error free. Keep this idea in mind.
The parity bit is placed in the 8th index of the message. 8 in binary is 1000, and we are actually checking the parity of all the positions with a 1 in the 4th binary digit (8–15). When we put a parity bit in the indexes that are multiples of 2, we can run a check for each binary position.
If you put all 4 of these checks in one message, you can find the exact binary position where an error occurs! Well, almost.
The astute reader may have found the blindspot in these 4 checks. If you didn’t, go back and see if you can find it.
The blind spot is position 0. P1 checks positions whose last binary digit is 1, P2 checks positions whose second digit is 1, P4 checks the third, and P8 checks the fourth. 0000 falls in none of these checks. The solution to this is, simply, to get rid of the 0th bit. This gives what is called a (15, 11) Hamming code for 11 message bits out of 15 total bits.
Let’s also notice this last bit of cleverness. If you add the parity bits from checks that fail, the final syndrome is actually the index of the error bit! Since we eliminatied the 0th bit, can 0000 represent an error-free message.
Hamming codes scale incredibly well. Since the parity bits are placed in positions that are powers of 2, for every message that is 2^n - 1 bits, only n parity bits are needed. Here is how it looks at for 255 bits.