Using it
Type data bits in groups of four. Each group becomes seven bits, with the three parity bits worked out in the steps. Swap the boxes to check a code: flip any one bit of a seven-bit group and the decoder finds it, fixes it, and gives the original four data bits back.
The Code setting switches to extended Hamming(8,4), which adds an eighth bit. Parity sets whether each group adds up to an even or an odd count. Even is the usual choice. Odd works just as well, as long as the sender and the receiver agree.
Parity first
A parity bit is one extra bit that makes the count of 1s even. Send 1011 with even parity and it goes as 1011 1; if any single bit flips on the way, the count turns odd and the receiver knows something went wrong. It can't tell which bit, though, and two flips cancel out.
How Hamming(7,4) finds the bit
Number the seven positions 1 to 7. Parity bits sit at the powers of two, 1, 2 and 4; data bits fill 3, 5, 6 and 7. Each parity bit checks the positions whose number includes it in binary: p1 checks 1, 3, 5, 7; p2 checks 2, 3, 6, 7; p4 checks 4, 5, 6, 7.
When a bit flips, the groups that now fail add up to its position. If p1 and p4 fail, the bad bit is 1 + 4 = 5. Flip it back and the data is right again. Richard Hamming worked this out at Bell Labs and published it in 1950, after his weekend jobs on a relay computer kept being dropped: the machine could detect an error, but with no operator there it simply moved on to the next job.
The eighth bit: SECDED
Plain Hamming(7,4) can't tell one flipped bit from two. Two flips still make some groups fail, so it fixes the wrong bit and gives back wrong data without a word.
Extended Hamming(8,4) adds one more parity bit at the end, covering all seven bits before it. 1011 becomes 01100110. When a group fails and the overall bit fails too, one bit flipped, and it gets fixed. When the groups fail but the overall bit passes, two bits flipped. The decoder says so and shows ???? for that group rather than guess. That's single error correction with double error detection, SECDED for short.
Which positions each parity bit checks
| Parity bit | Checks positions |
|---|---|
| p1 (position 1) | 1, 3, 5, 7 |
| p2 (position 2) | 2, 3, 6, 7 |
| p4 (position 4) | 4, 5, 6, 7 |
In the classroom
Ages 12 and up, about 20 minutes. One pupil encodes a 4-bit message into 7 bits with the tool, writes the bits on cards face up, and leaves the room; a classmate flips one card. The first pupil returns, checks the three parity groups, and finds which card was flipped.
Take it further: CS Unplugged's "Parity magic" lesson is a card trick built on the same idea, with versions for ages 5 to 7 and 8 to 10.
Questions
What is 1011 in Hamming(7,4)?
0110011, laid out as p1 p2 d1 p4 d2 d3 d4.
Can it fix two errors?
No. Two flipped bits point at the wrong position. Pick extended (8,4) in the Code setting and the eighth bit lets it at least notice two.
Where are Hamming codes used?
Versions of them protect ECC memory in servers, where a stray flipped bit is corrected without anyone noticing.
Sources
- Hamming, R. W. (1950). Error Detecting and Error Correcting Codes. Bell System Technical Journal 29(2)
- Wikipedia: Hamming(7,4)
- Wikipedia: Hamming code
- CS Unplugged: Error detection and correction
Added . Last updated and reviewed . What's new






