Hamming
Nothing on this page searches for the error. The checks that fail, read as a binary number, are its address.
New to error correction? Start here
Bits come back wrong
A bit written to a disc, sent down a wire or held in memory sometimes comes back as the other one. A scratch, a cosmic ray, a bad connector. You cannot prevent it and you cannot ask the sender, because the sender is a scratched disc or a satellite that has already moved on.
So you send more than the message. The extra part is chosen so that a corrupted message is not a valid one, which is how a machine can notice; and if there is enough of it, chosen so that only one original could have produced what arrived, which is how a machine can repair. The machines here differ in how much extra, and in what they promise back for it.
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.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every single-bit error in every one of the 16 messages is found and corrected, all 128 cases | yes | exhausted rather than sampled: every message, every bit position, and the clean word too |
| the check bits spell the position of the wrong bit, not merely that one is wrong | yes | each of the 7 positions names itself in binary |
| and a word with nothing wrong spells nought | yes | zero is not a position, which is what makes the address usable |
| two errors defeat it: 336 of 336 double errors are miscorrected, which is 100 per cent | yes | it does not fail safe -- it corrects confidently and makes the message worse, which is why a second check bit exists |
| each check bit covers exactly the positions whose number contains its own bit | yes | that overlap is what makes the syndrome an address rather than a flag |
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 number of check bits grows only logarithmically, roughly one more as the protected word doubles. But 72 carrying 64 is not this code made wider. It is seven Hamming check bits plus one overall parity bit, and that extra bit is precisely what turns a code that corrects one error into one that also detects two — the failure this page has just demonstrated. The checking-number mechanism is still inside it 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 the case a whole family of real channels produces. A burst, where errors arrive in a clump rather than independently, is not what every channel does and is very much what a scratched disc does. That 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.