Hamming Code: Correcting a Bit by Naming Where It Is

Set four data bits and flip any bits in the channel, with the buttons or by clicking the diagram. The decoder reruns the three parity checks, reads the ones that fail as a binary number and flips that bit. Step through it once, then try two flips.

Worked example — Hamming Code: Correcting a Bit by Naming Where It Is

Sent: the check bits	0110011
Received	0110111
Syndrome	1012
Data delivered	1011
Data bits wrong, against the 1011 sent	0
Rate, data bits per bit sent	57.1%

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Hamming Code: Correcting a Bit by Naming Where It Is

A Hamming code adds check bits to data so that one flipped bit can be found and flipped back. Each check bit makes a chosen set of positions hold an even number of ones, a parity check. The decoder repeats the checks on what arrived, and the pattern of failures, the syndrome, read as a binary number, is the position of the wrong bit, 0 meaning none. A check digit can only say that something is wrong; this says where. The extended code adds one bit that makes the whole word even, and then corrects any single flip and detects, without correcting, any two: SECDED.

What each symbol means

dᵢ: the four data bits, at positions 3, 5, 6 and 7
p₁, p₂, p₄: the check bits, each at the position it is named after; p₀ is the extended code's overall bit
s: the syndrome, 4s₄ + 2s₂ + s₁, where s_k is 1 when circle k holds an odd number of ones on arrival
P: the parity of all eight received bits in the extended code: 1 means an odd number of flips
p: the bit-error rate, the chance that any one bit flips, independently of every other

Assumes: Every bit flips independently, with the same probability p. Real channels and memories also fail in bursts, several neighbouring bits at once, and a burst is exactly the multiple flip these codes handle worst.
Breaks when: At three flips. The extended code reads three flips as one, because the overall check comes out odd, and corrects a bit that was right: the table of every flip shows all 896 triple flips delivering wrong data with no flag.

The circles that fail add up to the bit that flipped 🖖

Press One flip. Bit 5 is flipped in the channel, and circles 1 and 4 now hold an odd number of ones while circle 2 is still even: 1 + 4 = 5. No preset was chosen to make that work. Circle k checks exactly the positions whose binary number contains k, so a wrong bit at position i upsets exactly the circles that add up to i, and a bit's place in the diagram is its address. Hamming asked for this in 1950, a "checking number" that gives the position of any single error, with zero meaning none. Three checks give eight answers and the seven-bit word needs exactly eight, seven positions and "no error", so nothing is spare: of the 128 seven-bit words, 16 are codewords and the other 112 are their single flips, each one flip from exactly one codeword. The table under the chart decodes all 112 correctly. Why the check bits sit at 1, 2 and 4 is a smaller point than it looks. Those positions have a single 1 in binary, so each check bit lies in one circle only and can be set by its own check, which is the reason Hamming gave.

Two flips, and the decoder breaks a third bit 🖖

Press Two flips. Bits 3 and 5 go wrong. Circle 1 contains both, is upset twice and stays even; circles 2 and 4 go odd, and the syndrome reads 6, a perfectly good position. The decoder flips bit 6, which was right. Two data bits were wrong on arrival and three are wrong after the correction. The grid shows every pair doing the same: all 21, and so all 336 double flips across the 16 data words, deliver wrong data without a flag. Press Check bits only: positions 1 and 2 carry no data, the data arrived intact, and the syndrome 3 sends the decoder to break d₁. Now press Extended, two flips. The eighth bit makes all eight even, so one flip always leaves the overall check odd and two always leave it even. Seeing it even beside a nonzero syndrome, the decoder flags the word and touches nothing, for all 448 double flips. It cannot repair them, because 3 and 5 give syndrome 6 and so do 1 and 7. A flag was where Hamming started. His 1950 paper opens on the two relay computers Bell Labs built for the Aberdeen Proving Ground, which let no relay failure through undetected, about two or three a day among 8,900 relays in the early period, and, run unattended over nights and weekends, frequently came to a halt.

Sending each bit twice costs the same eight bits and corrects nothing 🖖

Each bit twice and the extended code both spend eight bits on four. Sent twice, a pair that disagrees shows something went wrong and cannot show which copy is right, so all the receiver can do is flag the block. At p = 0.01 that happens to 7.69×10⁻² of blocks, and 3.77×10⁻⁴ get through wrong, when both copies of a bit flip together. The extended Hamming code corrects every single flip, flags 2.64×10⁻³ and lets 5.34×10⁻⁵ through: 29 times fewer flags and 7 times fewer wrong blocks, from the same budget. The dashed and solid lines show it ahead on both counts until p passes 0.066, a channel that flips one bit in fifteen. Three copies of each bit do beat the seven-bit code per block at every p on the slider, 1.19×10⁻³ against 2.03×10⁻³ here, but with 12 bits against 7, which is why the fair test is the one at eight.

Problem solved in full

How many check bits does a 64-bit word need? 4 steps
Protect 64 data bits the same way. Press Extended, one flip: four check bits for four data bits, a rate of 50.0%. Find how many check bits one 64-bit word needs for the same promise, any single flip corrected and any two flagged, and what the longer word costs at that preset's p = 0.001.

Open this problem in the tool
1. With r checks the syndrome takes 2^r values. One has to mean no error and each of the m + r positions needs its own, so 2^r ≥ m + r + 1. On the page m = 4, and r = 3 meets it exactly, with no value to spare.
  
  $2^{r} \geq m + r + 1, m = 4 : 2^{3} = 8 = 4 + 3 + 1$
2. For m = 64, six checks give 64 values against the 71 needed; seven give 128, enough for 72. So 71 bits correct any single flip.
  
  $m = 64 : 2^{6} = 64 < 71, 2^{7} = 128 \geq 72 \Rightarrow r = 7, n = 71$
3. One overall bit on top makes 72 bits, 8 of them checks, and a rate of 88.9% against the page's 50.0%.
  
  $n = 64 + 7 + 1 = 72, \frac{64}{72} = 88 . 9%$
4. The cost is that a longer word collects two flips more often, and two flips are what SECDED can no longer repair. For one 8-bit word that probability is the page's two figures added together.
  
  $P_{\geq 2} (n) = 1 - q^{n} - n p q^{n - 1}, P_{\geq 2} (8) = 2.78 \times 1 0^{- 5} + 5.57 \times 1 0^{- 8} = 2.79 \times 1 0^{- 5}$
Answer

Eight check bits, a 72-bit word, rate 88.9%. At p = 0.001 it holds two or more flips with probability 2.44×10⁻³. The same 64 bits as sixteen 8-bit words are lost when any one of them is, 4.46×10⁻⁴. The long word is about 5.5 times as likely to lose its 64 bits, and pays an eighth as many check bits for it.

$P_{\geq 2} (72) = 2.44 \times 1 0^{- 3}, 1 - (1 - P_{\geq 2} (8))^{16} = 4.46 \times 1 0^{- 4}, \frac{2 . 44}{0 . 446} \approx 5.5$

Learning path

Why an algorithm is correct

References (2)

The code itself, the requirement that the checking number give the position of any single error, the check positions 1, 2, 4 and the reason for them, the extended code that adds double-error detection, and the relay computers that motivated it: R. W. Hamming, "Error Detecting and Error Correcting Codes." Bell System Technical Journal 29(2), April 1950, pp. 147-160. DOI 10.1002/j.1538-7305.1950.tb00463.x
How Hamming told the story in his later course: a relay computer that could detect an error, retried three times and then dropped the problem, and the question that followed: R. W. Hamming, The Art of Doing Science and Engineering: Learning to Learn, Session 12, "Error-Correcting Codes". Lecture slides, Naval Postgraduate School, Monterey (course delivered 1995).

By the 42Math team · Reviewed against published sources. Corrections welcome.