Hamming code is a family of error-correcting codes that adds carefully positioned parity bits to a data word. At the receiver, those checks form a binary address called a syndrome. If one transmitted bit has changed, the syndrome identifies its exact position, allowing the receiver to repair the word without requesting it again.
The classic Hamming code example is Hamming(7,4): four data bits become a seven-bit codeword by adding three parity bits. This guide derives that layout, encodes a complete example, introduces an error, and corrects it step by step. It also explains the limits of the basic method and why an extra overall parity bit is used for SECDED memory.
What Problem Hamming Code Solves
Communication links and storage devices can alter bits because of noise, interference, weak cells, radiation, or timing faults. A single parity bit can report that an odd number of bits changed, but it cannot say which bit is wrong. Hamming code combines several overlapping parity checks so every codeword position has a unique check membership.
Each parity check returns pass or fail. Read together, the results encode the location of a single error. This is the defining insight behind Hamming code: parity bits do more than announce corruption; their pattern points to the damaged bit.
The Hamming code method is a forward error correction technique. The sender supplies redundancy in advance, and the receiver can correct the expected fault locally. That is different from error detection followed by retransmission. This makes Hamming code practical when a return channel is unavailable or a retry would be expensive.
Hamming Distance and Correction Capability
The Hamming distance between two equal-length words is the number of bit positions in which they differ. For example, 101101 and 100001 differ in two positions, so their distance is 2.
A code's minimum distance determines what it can guarantee:
| Minimum distance | Guaranteed capability |
|---|---|
| 2 | Detect one bit error |
| 3 | Correct one bit error |
| 4 | Correct one bit error and detect two bit errors |
The basic Hamming code has minimum distance 3. Valid codewords are separated far enough that a received word with one flipped bit remains closest to exactly one valid codeword. Adding an overall parity bit creates the extended Hamming code form with distance 4, commonly described as SECDED: single-error correction, double-error detection.
How Many Parity Bits Are Required?
For m data bits and r Hamming code parity bits, the codeword needs positions for all data bits, all parity bits, and the no-error result. The requirement is:
2^r >= m + r + 1For four data bits, two parity bits are insufficient because 2^2 = 4, while 4 + 2 + 1 = 7. Three are sufficient because 2^3 = 8 and 4 + 3 + 1 = 8. Therefore four data bits produce a seven-bit Hamming code word.
For 11 data bits, four parity bits work because 2^4 = 16 and 11 + 4 + 1 = 16, giving Hamming(15,11). The notation Hamming(n,k) means a total Hamming code word length n containing k data bits.
Where Hamming Code Places Parity Bits
Number codeword positions starting at 1. Reserve powers of two for parity bits: positions 1, 2, 4, 8, and so on. Place data in the remaining positions.
The Hamming(7,4) Hamming code layout is:
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Purpose | P1 | P2 | D1 | P4 | D2 | D3 | D4 |
The labels P1, P2, and P4 match their position values. Writing each position in binary explains which checks cover it:
| Position | Binary address | Checked by |
|---|---|---|
| 1 | 001 | P1 |
| 2 | 010 | P2 |
| 3 | 011 | P1, P2 |
| 4 | 100 | P4 |
| 5 | 101 | P1, P4 |
| 6 | 110 | P2, P4 |
| 7 | 111 | P1, P2, P4 |
P1 checks every position whose binary address has the ones bit set: 1, 3, 5, and 7. P2 checks addresses with the twos bit set: 2, 3, 6, and 7. P4 checks addresses with the fours bit set: 4, 5, 6, and 7. This binary addressing makes every position participate in a unique combination.
Worked Hamming(7,4) Encoding Example
Encode data 1011 using even parity. Place its four bits in positions 3, 5, 6, and 7:
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Value | P1 | P2 | 1 | P4 | 0 | 1 | 1 |
Now calculate each Hamming code parity bit.
Calculate P1
P1 covers positions 1, 3, 5, and 7. The known data values are 1, 0, 1, containing two ones. Even parity already holds, so P1 is 0.
Calculate P2
P2 covers positions 2, 3, 6, and 7. The known values are 1, 1, 1, containing three ones. Set P2 to 1 so the total becomes four.
Calculate P4
P4 covers positions 4, 5, 6, and 7. The known values are 0, 1, 1, containing two ones. Set P4 to 0.
The final Hamming code word is:
Position: 1 2 3 4 5 6 7
Codeword: 0 1 1 0 0 1 1
Result: 0110011Odd parity follows the same layout but chooses each parity bit so its covered group contains an odd number of ones. Sender and receiver must agree on the convention.
Detect and Correct a Single-Bit Error
Suppose position 5 changes during storage or transmission. The receiver gets 0110111 instead of 0110011. Recalculate the same parity groups, including their parity positions:
| Check | Covered positions | Result |
|---|---|---|
| P1 | 1, 3, 5, 7 | Fails (0 XOR 1 XOR 1 XOR 1 = 1) |
| P2 | 2, 3, 6, 7 | Passes (1 XOR 1 XOR 1 XOR 1 = 0) |
| P4 | 4, 5, 6, 7 | Fails (0 XOR 1 XOR 1 XOR 1 = 1) |
Write the check results in P4-P2-P1 order:
P4 P2 P1 = 1 0 1
Binary 101 = decimal position 5The syndrome is 5, so Hamming code identifies position 5. Flip that bit from 1 back to 0, obtaining 0110011. Then extract data positions 3, 5, 6, and 7 to recover 1011.
If the syndrome is zero, every basic check passes. Under the single-error assumption, the receiver accepts the word. The binary to decimal converter can help verify a syndrome's positional value while learning the Hamming code method.
A Decoder Procedure
A practical Hamming code decoder follows a compact sequence:
- Receive the fixed-width codeword.
- Recalculate every parity group using the agreed even or odd convention.
- Assemble failed checks into the syndrome, with each check contributing its position value.
- If the syndrome is nonzero and within the word, flip that position.
- Remove parity positions and return the data bits.
- If extended overall parity is present, use it to distinguish single- and double-bit cases before correcting.
The parity calculations are XOR reductions. Hardware can perform them in parallel using the circuits described in the logic gates guide. The binary number system guide explains why powers-of-two positions form unique binary addresses.
Basic Hamming Code Versus SECDED
Basic Hamming code is designed to correct one error. A two-bit error can produce a nonzero syndrome that points to a third position. Blindly flipping that position would turn two errors into three. The seven-bit Hamming code form alone cannot reliably distinguish every double-bit error from a single-bit error.
Extended Hamming code adds one overall parity bit across the complete basic codeword. The receiver combines the syndrome with the overall parity result:
| Syndrome | Overall parity | Interpretation |
|---|---|---|
| Zero | Pass | No detected error |
| Nonzero | Fail | One error in the addressed basic-code position; correct it |
| Zero | Fail | Error in the overall parity bit |
| Nonzero | Pass | Detected double-bit error; do not correct as a single error |
This SECDED behavior is widely associated with ECC memory. It corrects any single-bit error and detects, but does not repair, a two-bit error. Larger bursts and chip-level failures require stronger schemes, interleaving, or device-specific protection.
Shortened and Larger Hamming Codes
The perfect binary forms have lengths 2^r - 1, such as 7, 15, 31, and 63 bits. A system may shorten a Hamming code by fixing selected data positions and omitting them from transmission. The resulting layout keeps the inherited parity relationships but carries fewer data bits.
Real systems must document bit numbering, wire order, byte packing, parity convention, and whether an overall parity bit is included. Two implementations can both claim Hamming code while placing the displayed bits in opposite directions. Compatibility depends on the complete format, not only the mathematical family name.
Where Hamming Code Is Used
- ECC memory: extended variants correct isolated memory-cell errors and report double-bit failures.
- Digital communication: simple links can repair an occasional bit without a retransmission round trip.
- Storage and embedded systems: small codewords provide understandable protection with modest logic.
- Education and hardware design: the Hamming code scheme demonstrates how redundant parity equations locate an error.
- QR and modern storage context: these often use stronger block codes, but Hamming code provides the conceptual foundation for minimum distance and syndrome decoding.
The Hamming code technique is attractive when single independent bit errors dominate and low implementation cost matters. Hamming code is not the right answer for every channel; error statistics should drive code selection.
Common Mistakes
- Starting positions at zero. Standard derivations number positions from 1 so parity bits fall at powers of two.
- Putting data in parity positions. Positions 1, 2, 4, 8, and so on are reserved.
- Changing parity convention midway. Even and odd parity both work, but encoder and decoder must match.
- Reading the syndrome backward. P1 is the least significant syndrome bit; P4-P2-P1 gives the numeric position.
- Assuming basic Hamming code safely detects every double error. Add overall parity for SECDED behavior.
- Correcting an out-of-range syndrome. Treat it as a format or multi-error failure rather than indexing memory blindly.
- Confusing data order with displayed order. Document whether the first supplied data bit enters the lowest or highest available position.
Frequently Asked Questions
What is Hamming code in simple terms?
Hamming code adds overlapping parity checks to a data word. The pattern of failed checks forms the address of one incorrect bit, so the receiver can flip it back.
Why are parity bits placed at powers of two?
Those positions correspond to single set bits in binary addresses. Each other position has a unique combination of set address bits, so its membership across parity groups uniquely identifies it.
What does Hamming(7,4) mean?
It means a seven-bit codeword that carries four data bits and three parity bits. The basic Hamming code corrects one bit error within that word.
Can Hamming code correct two errors?
No. The standard form corrects one. An added overall parity bit provides SECDED, which detects two errors but still cannot correct both. Stronger codes are needed for multi-bit correction.
What is a syndrome?
The syndrome is the combined result of all parity checks. A zero syndrome means the basic checks pass; a nonzero syndrome is interpreted as the binary index of a faulty position under the single-error model.
Is Hamming distance the same as Hamming code?
No. Hamming distance is a general measurement of differences between equal-length strings. Hamming code is a particular error-correcting family designed using that distance.
Does Hamming code encrypt data?
No. Its redundancy is public and exists for reliability, not secrecy. Anyone who knows the layout can decode the data; confidentiality requires encryption.
Summary
Hamming code assigns parity bits to power-of-two positions and lets each one check a different set of binary addresses. Failed checks form a syndrome that locates one flipped bit. Hamming(7,4) turns four data bits into seven, while an added overall parity bit extends the design to SECDED. The Hamming code method is compact and instructive, but its guarantee must be respected: correct one error, detect two only in the extended form, and use stronger protection when bursts or multiple failures are realistic.
