Hamming(7,4), Explained

After reading this you will be able to encode four data bits into a seven-bit codeword, flip any single bit, and compute the syndrome by hand to find and repair the error.

What error-correcting codes do

Send seven bits across a noisy channel and one of them might arrive wrong. A plain message cannot tell you that anything happened. Hamming(7,4) can. It takes four data bits, adds three parity bits, and arranges them so that any single flipped bit announces its own position.

Here is the hook. Encode the data 1011 and you get the codeword 0110011 (positions 1 through 7). Flip bit 5 during transmission and the receiver sees 0110111. The decoder runs three parity checks, reads out the binary number 101, and that is 5 in decimal. It flips bit 5 back. No retransmission, no request for a resend. The code repaired itself.

The trick is not magic. It is a careful placement of parity bits so that the pattern of failed checks spells the error location in binary. The rest of this article shows exactly how.

When to reach for it, and when not

Hamming(7,4) is the right teaching example because it is small enough to check every case by hand: there are only 2^4 = 16 valid codewords, and each has exactly 7 single-bit neighbours. It corrects any one flipped bit per seven-bit block.

It is the wrong choice when errors arrive in bursts. If two bits in the same block flip, plain Hamming(7,4) will detect nothing wrong in some cases and will "correct" the wrong bit in others, making things worse. Real systems that face burst errors use interleaving, Reed-Solomon codes, or longer LDPC codes.

The efficiency here is 4 data bits per 7 transmitted bits, a rate of 4/7 \approx 0.5714. You pay 3 extra bits to protect 4. Longer Hamming codes are far cheaper: Hamming(15,11) carries 11 data bits with 4 parity bits, a rate of 11/15 \approx 0.7333, still correcting one error per block.

The parity placement rule

Number the seven positions 1 to 7. Parity bits sit at the powers of two: positions 1, 2 and 4. Data bits fill the rest: positions 3, 5, 6 and 7.

1 = 001,\quad 2 = 010,\quad 4 = 100

Each parity bit covers every position whose binary index has a particular bit set. Parity bit at position 1 (binary 001) covers all positions with the low bit set: 1, 3, 5, 7. Parity bit at position 2 (binary 010) covers positions 2, 3, 6, 7. Parity bit at position 4 (binary 100) covers positions 4, 5, 6, 7.

Each parity bit is chosen so that the total number of ones in its group is even. That is even parity. Write the three groups as sums modulo 2:

p_1 = d_3 \oplus d_5 \oplus d_7,\quad p_2 = d_3 \oplus d_6 \oplus d_7,\quad p_4 = d_5 \oplus d_6 \oplus d_7

Here p_1, p_2, p_4 are the parity bits at positions 1, 2 and 4, the symbol \oplus is XOR (addition modulo 2), and d_3, d_5, d_6, d_7 are the data bits at positions 3, 5, 6 and 7. Every position except 1, 2 and 4 holds a data bit.

Encoding the demo data step by step

Encode data 1011

Take the four data bits as d_3 d_5 d_6 d_7 = 1011, which is the tool's default. That means d3 = 1, d5 = 0, d6 = 1, d7 = 1.

Compute p_1 = d_3 \oplus d_5 \oplus d_7 = 1 \oplus 0 \oplus 1 = 0.
Compute p_2 = d_3 \oplus d_6 \oplus d_7 = 1 \oplus 1 \oplus 1 = 1.
Compute p_4 = d_5 \oplus d_6 \oplus d_7 = 0 \oplus 1 \oplus 1 = 0.
Lay the bits into positions 1 to 7: p1 p2 d3 p4 d5 d6 d7 = 0 1 1 0 0 1 1.

The transmitted codeword is 0110011. Check one group by hand: positions 1, 3, 5, 7 hold 0, 1, 0, 1, which sum to 2, an even count. Even parity holds, as it should.

The seven positions of the codeword 0110011
Position	Binary index	Role	Value
1	001	parity p1	0
2	010	parity p2	1
3	011	data d3	1
4	100	parity p4	0
5	101	data d5	0
6	110	data d6	1
7	111	data d7	1

The syndrome, and why it spells the position

At the receiver, recompute each parity check across the bits actually received. Each check produces one syndrome bit: 0 if that group still has even parity, 1 if it does not.

s_1 = r_1 \oplus r_3 \oplus r_5 \oplus r_7,\quad s_2 = r_2 \oplus r_3 \oplus r_6 \oplus r_7,\quad s_3 = r_4 \oplus r_5 \oplus r_6 \oplus r_7

Here r_i is the received bit at position i, and s_1, s_2, s_3 are the three syndrome bits. Read them as a binary number with s_3 as the high bit:

\text{position} = s_3 \cdot 4 + s_2 \cdot 2 + s_1 \cdot 1

If the syndrome is 000, no single-bit error is detected. Otherwise the value is the position of the flipped bit. The reason is structural: position i belongs to check s_k exactly when bit k of i's binary index is 1. So flipping bit i flips precisely the checks whose bit pattern equals i. The failing checks reconstruct the index.

Decoding the corrupted demo message

Flip bit 5 and repair it

Start from the transmitted codeword 0110011. Flip position 5 (currently 0) to 1. The received word is 0110111, so r_1 \dots r_7 = 0,1,1,0,1,1,1.

s_1 = r_1 \oplus r_3 \oplus r_5 \oplus r_7 = 0 \oplus 1 \oplus 1 \oplus 1 = 1.
s_2 = r_2 \oplus r_3 \oplus r_6 \oplus r_7 = 1 \oplus 1 \oplus 1 \oplus 1 = 0.
s_3 = r_4 \oplus r_5 \oplus r_6 \oplus r_7 = 0 \oplus 1 \oplus 1 \oplus 1 = 1.
Assemble s_3 s_2 s_1 = 101 = 5. Flip position 5 back to 0.
The repaired word is 0110011. Read data bits at 3, 5, 6, 7: 1011, the original.

Try any other single flip and the arithmetic lands on its position. Flip position 2 alone and you get s_1 = 0, s_2 = 1, s_3 = 0, giving 010 = 2.

Each single flip of the demo codeword produces a syndrome equal to the position flipped. The line is exactly y = x, which is the whole point of the design.

Reading the results honestly

A syndrome of 0 means "no single-bit error found," not "the message is perfect." Zero errors and any even number of errors can both give syndrome 0. Hamming(7,4) simply cannot tell those cases apart.

A nonzero syndrome from 1 to 7 always points at one position. If exactly one bit flipped, that pointer is correct. If two bits flipped, the pointer is still 1 to 7 but names an innocent bit, and the decoder will corrupt it further. There is no built-in alarm for this in the bare (7,4) code.

Add one overall parity bit across all seven positions to make Hamming(8,4). Now a single error gives a nonzero syndrome and a failed overall check, while a double error gives a nonzero syndrome but a passing overall check. That contradiction flags "two errors, do not trust the correction."

Common mistakes

The errors below trip up almost everyone the first time.

Counting positions from 0: Hamming positions start at 1, not 0. The parity bits sit at 1, 2, 4, which are 2^0, 2^1, 2^2. Start at 0 and the whole index arithmetic collapses.
Reading the syndrome backwards: The high bit is s_3 (the position-4 check), the low bit is s_1 (the position-1 check). Swap them and you will flip the wrong bit. In the demo, reading 101 as s_1 s_2 s_3 instead of s_3 s_2 s_1 happens to give the same 5, but with syndrome 110 the two readings differ: 6 versus 3.
Including the parity bit in its own count only sometimes: Each check must always include its own parity bit. Check s_1 covers positions 1, 3, 5, 7, and position 1 is the parity bit itself. Leave it out and the group loses the even-parity property.
Assuming double errors are corrected: They are not. Hamming(7,4) has minimum distance 3, which allows correcting \lfloor (3-1)/2 \rfloor = 1 error, or detecting up to 2 errors, but not both at once.

Related tools on this site

If watching a small algorithm run bit by bit appeals to you, the Turing Machine Simulator strips computation down to reads and writes on a tape. The Huffman Coding Visualizer builds the opposite side of information theory: compressing data rather than protecting it. For the accepting-and-rejecting logic behind pattern matching, see Regex to Automaton. And to feel how algorithm cost grows, the Big-O Complexity Race pits log n against exponential time.

Frequently asked questions

Why are parity bits at positions 1, 2 and 4 instead of at the end?

Placing them at the powers of two makes the syndrome equal the error position directly. If you put parity bits at the end, you still get a valid code, but the syndrome no longer reads out as a clean binary position and you need a lookup table to decode.

What happens if a parity bit itself gets corrupted?

It is corrected like any other bit. Flip position 2 of the demo codeword and the syndrome is 010 = 2, which points straight at the parity bit. The decoder flips it back. Parity bits are protected by the same mechanism they provide.

How many errors can Hamming(7,4) correct?

Exactly one per seven-bit block. Its minimum Hamming distance is 3, so any two valid codewords differ in at least 3 positions, which leaves room to correct a single flip unambiguously.

What does a syndrome of 000 tell me?

That no single-bit error was detected. The block might be error-free, or it might have suffered an even number of errors that cancel out in every check. The bare (7,4) code cannot distinguish these.

Is the 4/7 overhead worth it?

For teaching, yes, because you can verify all 16 codewords by hand. For real channels, longer Hamming codes give the same single-error correction at far lower overhead: Hamming(15,11) spends only 4 parity bits on 11 data bits.

Try it yourself in the tool