Hamming Code Visualizer

In the late 1940s Richard Hamming worked at Bell Labs on the Bell Model V, a relay computer fed by punched paper tape. The machine could tell when a relay had slipped. What it did next depended on the day of the week.

On weekdays a detected error stopped the machine and lit its lamps so that operators could put things right. After hours and on weekends nobody was there, so the machine dropped the job and moved to the next one. Hamming worked weekends. He kept returning to find his programs abandoned and had to start them again from the beginning. As the story is told, the irritation hardened into a question: if a machine can tell that an error happened, why can it not find where it happened and fix it? The paper that answered it appeared in 1950.

One long path, one extra bit

Its opening frames the problem in terms that still apply. A telephone exchange performs enormous numbers of operations and can live with the odd wrong number, because its many paths are more or less independent of one another. A digital computer is different. There is usually one long path that passes through the same equipment again and again, so a single failure either halts everything or quietly spoils all the work that follows it.

The tool he started from was the parity bit. Add one extra bit to a group so that the count of ones comes out even. If a single bit flips on the way, the count turns odd and the receiver knows. It was cheap enough to become routine; a parity track was present on the first magnetic tape data storage in 1951.

But one check gives one answer. It says that something is wrong and nothing about where. It also misses every even number of flips, since two changes restore the count.

The blunt way to locate an error is to say everything three times and take a majority vote. That works, and it repairs any single flip within a triple, but it sends three bits for every bit of data. Hamming wanted both things at once: more distance between valid messages and less waste. His notation survives. A scheme that sends n bits to carry k is an (n,k) code, so triple repetition is (3,1), with a rate of one third.

Checks that overlap can spell a number

The idea that broke the trade was to let the checks overlap. Number the positions of a word from 1 and write each number in binary. Give every power of two, positions 1, 2, 4, 8 and onward, to a parity bit, and fill the other positions with data. The parity bit at position 1 checks every position whose number has its lowest binary digit set: 1, 3, 5, 7. The bit at position 2 checks the positions with the second digit set: 2, 3, 6, 7. The bit at position 4 checks 4, 5, 6, 7. Each position now sits in its own combination of checks, shared with no other.

That uniqueness is the whole trick. When one bit flips, exactly the checks that cover it fail. Write a 1 for each failing check and a 0 for each passing one, and the pattern is the binary number of the damaged position. The receiver does not search for the error. It reads the address and flips that bit back.

With r parity bits there are 2^r - 1 patterns other than all zeros, so the word can be 2^r - 1 bits long, and all but r of those bits carry data. Three checks protect 4 data bits in 7 bits. Four protect 11 in 15. Five protect 26 in 31, and the overhead keeps shrinking as the word grows.

Here is one case worked by hand. Take the data 1011. In the (7,4) code the data bits go to positions 3, 5, 6 and 7, and the three parity bits are chosen to make each check even, which gives the codeword 0110011. Now flip position 5, so the receiver sees 0110111. The first check adds positions 1, 3, 5 and 7 and gets 0 + 1 + 1 + 1 = 3, which is odd. The second adds positions 2, 3, 6 and 7 and gets 4, even. The third adds positions 4, 5, 6 and 7 and gets 3, odd.

Read the results from the last check back to the first: fail, pass, fail, or 101. In binary that is 5. Flip position 5 and the word is 0110011 again. The tool above opens on exactly this case, and its table of the parity-check matrix shows why it works: the column for position 5 holds the pattern 101, and no other column does.

The same thing can be drawn as three overlapping circles, one for each check, with the seven bits placed in the seven regions. A flipped bit makes odd exactly the circles it lies in. For a word of seven bits it is the clearest explanation there is.

Distance, and what the code cannot promise

Underneath sits a single idea that now carries Hamming’s name. The Hamming distance between two words is the number of positions in which they differ. A code is a chosen set of words, and its minimum distance is the smallest distance between any two of them. If every pair of codewords is at least k + 1 apart, no k flips can turn one codeword into another, so k errors are always noticed. Plain parity has distance 2. Every plain Hamming code has distance 3.

A code of distance 3 offers a choice, not both options together. Use it only to detect, and any one or two flips will be noticed. Use it to correct, and any single flip is repaired, but then a second flip becomes a trap. Two flipped bits make the checks fail in a pattern that names a third, innocent position. The decoder obediently flips it and delivers a valid codeword three bits away from the one that was sent. Nothing warns anyone. Send 0110011, flip positions 1 and 2, and the decoder hands back 1000011, which turns the data 1011 into 0011.

The standard repair is one more bit: an overall parity bit across the whole word. That raises the minimum distance to 4 and lets the receiver separate the two cases. One flip makes the overall count odd and is corrected as before. Two flips leave the count even while some check fails, which a single error cannot do, so the decoder raises a flag and changes nothing. This is single error correction with double error detection, shortened to SECDED.

The extended code has a blind spot of its own, and it deserves to be stated exactly. Three flips make the overall count odd, just as one does, so triple errors are mistaken for single ones and “corrected” into the wrong word. Four flips can form a codeword and pass every check. The code tells one from two. It never promised to tell one from three.

Perfect, and how good that is

There is a counting argument behind the plain code’s stubborn confidence. Around each codeword draw a ball holding the codeword itself and every word one flip away. In the (7,4) code a ball holds 8 words and there are 16 codewords, and 16 x 8 = 128, which is every 7-bit word there is. The balls do not overlap and they leave no gaps. A code that fills its space this way meets the Hamming bound exactly and is called perfect. It gives the highest possible rate for that length at distance 3, and it also means that every received word, however mangled, looks like a correctable one.

How much this is worth depends on the channel. On a channel that flips each bit independently with a small fixed probability, the number of flips in a word follows the binomial distribution, and a block comes out right when at most one bit flipped. At a flip probability of 0.05, a (7,4) block is right about 95.6 percent of the time, against 81.5 percent for the same four bits sent bare.

The comparison is not all flattering. At that same error rate, sending each bit three times gets about 97.1 percent of four-bit blocks right, better than the Hamming code, at the cost of 12 bits instead of 7. The experiment in the tool sends seeded random blocks through such a channel under each scheme and prints the measured share beside the exact value with a Wilson interval. It also tests the agreement with a chi-square statistic against the tabulated critical value, which is 3.841 for one degree of freedom at the 0.95 level, and it reports the result whichever way it falls.

Where the idea lives now

Hamming codes suit places where errors are rare and arrive one at a time, and computer memory is the classic case. Memory with this protection is called ECC memory. Most of it uses a SECDED code, and through several generations of memory the usual arrangement has been a word of 72 bits holding 64 data bits and 8 check bits. The stray flips it guards against come largely from background radiation, chiefly neutrons from cosmic ray secondaries, which is why error rates climb with altitude. The extended code was in memory systems as early as the IBM 7030 Stretch in 1961.

Field data is a useful test of the assumption that errors are rare and isolated. A study of memory errors across a large fleet of servers over two and a half years found error rates orders of magnitude above what had been reported before, with more than 8 percent of memory modules affected in a year. It also found that hard errors, faults that persist, dominated over the transient kind. A code built for one flip in a word is a first line of defense there, not a guarantee.

That is the honest shape of the invention. Hamming did not make errors impossible. He made the common one, a single flipped bit, announce its own position at the cost of a few extra bits, and he gave the rest of the field its ruler: count the places where two words differ.