Hamming
Nothing on this page searches for the error. The checks that fail, read as a binary number, are its address.
Seven positions, three checks
1 Four bits to send, and three positions left over
Press a bit to change the message. The three check positions are filled in for you, because they are not yours to choose: each one is whatever makes its own parity come out even.
2 Each check covers the positions whose number contains its bit
the check at 1 covers 1, 3, 5, 7; the check at 2 covers 2, 3, 6, 7; the check at 4 covers 4, 5, 6, 7. Every position whose number contains that check's bit, which is why the failures can spell an address at all.
3 Flip one, and some of the checks disagree
Press any position below to flip it. Check positions are marked; flipping one of those is just as valid an error and the code handles it the same way, which is the part that surprises people.
4 The failed checks, read as a number, are the address
The checking number is 0. Nothing is claiming to be wrong.
sent 1011received 1011checking number 0checks failed 0
Nothing is flipped, every check agrees, and the checking number is zero. Press a position to break it.
Checked when this page loaded, by exhaustion rather than by sample: all 16 four-bit messages against every one of the 7 positions it could be flipped in, plus the clean case, 128 cases in all. In every one the checking number was exactly the position of the flipped bit, and correcting there gave the message back. Of the 336 ways to flip two bits, 336 end with the wrong message and no complaint.
A lost weekend at Bell Labs
Richard Hamming could only get time on the relay computer at weekends, when there were no operators in the building. The machine checked parity, and when parity failed it did the sensible thing for an unattended run: it gave up on the job and moved to the next one. He would come in on Monday to find the weekend gone and nothing to show.
The complaint that produced the machine below is the one anybody would make, which is why it is worth repeating: if it can tell that something is wrong, why can it not tell what.
Why the checks sit at 1, 2 and 4
Because those are the powers of two, and a position's number is written in exactly those bits. Put the check for bit j at position 2j and let it cover every position whose number has bit j set, and a flip at position p breaks precisely the checks whose bit appears in p, and no others.
So the pattern of failures cannot be anything except p written in binary. There is no search, no table and no comparison against candidates. The arithmetic that detects the error is the same arithmetic that names it, which is the trick, and it is why the check positions cannot be moved somewhere tidier.
Hamming's own word for the result was the checking number, not the syndrome that later became standard. Of the string of ones and zeros the checks produce, he wrote that it "may be regarded as a binary number and will be called the checking number. We shall require that this checking number give the position of any single error, with the zero value meaning no error in the symbol."
What it costs, and where it stops
Three positions of the seven carry no message, so four bits of payload need seven bits on the wire. That is the price, and it buys a minimum distance of three between any two valid code words.
A distance of three is enough to correct one error or to detect two, and not both at once, which is the sentence most explanations leave out. Flip two bits above and the code does not hesitate and does not complain. It computes a checking number, points confidently at a third position that you did not touch, corrects that, and hands on a message that is wrong. Every one of the 336 ways to flip two bits in this code ends that way. An extra overall parity bit buys the detection back, and this page does not have one, because watching it fail silently is more use than being told it can.
What is real here, and what is not
The proof is exhaustive, which is why it is worth trusting
The line at the bottom is not a sample. It runs all sixteen four-bit messages against every one of the seven positions the bit could be flipped in, plus the clean case, and checks two things each time: that the checking number equals the position, and that flipping the bit it names restores the original message. That is 128 cases and there is nowhere else for a counterexample to hide, because the code is small enough to finish. Most claims on this site are measured; this one is settled.
This is (7,4), and real hardware is not
Seven positions carrying four bits is the smallest Hamming code that shows the mechanism, which is why it is here. Memory uses wider ones, typically 72 bits carrying 64, because the overhead falls as the code grows: the checks go up by one each time the length doubles. The mechanism does not change and the arithmetic on this page is the arithmetic there.
Nothing here is a channel
Bits are flipped by pressing them. There is no noise model, no burst behaviour, no probability that two errors arrive together rather than one, and that last one matters: the case this code cannot handle is exactly the case a real channel produces most often, which is why a scratch on a CD gets scattered before it is written rather than handed to a code like this one.
The double-error count is computed, not quoted
The 336 figure in the prose is every unordered pair of positions across all sixteen messages, worked out when the page loads and printed in the proof line beside the exhaustive result. If it ever stopped being 336, or stopped being all of them, the number on this page would change with it.