Hamming Code Visualization | Hamming(7,4), Syndrome and SECDED

The idea: parity bits that point at the error

One parity bit tells you that a block has an error, but not where. Richard Hamming (1950) used several parity bits, each over a different group of positions. When one bit flips, the set of groups that fail is different for every position, so the receiver can name the bad bit and flip it back. No resend is needed. Hamming(7,4) sends 4 data bits in a 7-bit codeword: 4 data bits plus 3 parity bits.

The data 1011 is encoded as the codeword 0110011, with parity bits at positions 1, 2 and 4. On the channel bit 6 flips, so the receiver gets 0110001. Its checks give c4 = 1, c2 = 1, c1 = 0: the syndrome 110 is 6, so it flips bit 6 back and recovers 1011. — The failed checks, read as a binary number, are the position of the flipped bit.

Where the parity bits go

Number the codeword positions 1 to 7 and write each number in binary: 1 = 001, 2 = 010, 3 = 011, 4 = 100, 5 = 101, 6 = 110, 7 = 111. The powers of two (1, 2, 4) have a single 1 in binary. They hold the parity bits p1, p2, p4. The other positions (3, 5, 6, 7) hold the data bits d1, d2, d3, d4. So the codeword is p1 p2 d1 p4 d2 d3 d4.

Parity bit p_k covers every position whose binary number has the bit worth k set:

parity bit	binary pattern	covers positions	formula
p1	xx1	1, 3, 5, 7	p1 = d1 ⊕ d2 ⊕ d4
p2	x1x	2, 3, 6, 7	p2 = d1 ⊕ d3 ⊕ d4
p4	1xx	4, 5, 6, 7	p4 = d2 ⊕ d3 ⊕ d4

Encoding

The sender puts the data bits in place and picks each parity bit so that its group has an even number of 1s (even parity). XOR (⊕) is addition mod 2, so the parity bit is just the XOR of the other bits in the group. For data 1011: p1 = 1 ⊕ 0 ⊕ 1 = 0, p2 = 1 ⊕ 1 ⊕ 1 = 1, p4 = 0 ⊕ 1 ⊕ 1 = 0, and the codeword is 0110011 (Demo: encode 1011).

Three overlapping circles for the groups of p1, p2 and p4. Each parity bit sits in the part of its circle that no other circle covers. d4 at position 7 is in all three circles, d1 at position 3 in p1 and p2, d2 at position 5 in p1 and p4, d3 at position 6 in p2 and p4. — Each of the 7 regions of the three circles is one position, so a single flip makes a unique set of circles odd.

The syndrome is the position

The receiver redoes the three checks over the bits it got, parity bits included: c1 over positions 1, 3, 5, 7, c2 over 2, 3, 6, 7 and c4 over 4, 5, 6, 7. A check is 0 when its group is still even. Written as the binary number c4 c2 c1, the three checks form the syndrome.

Syndrome 000: every group is even, so no bit flipped (Demo: clean channel, syndrome 000).
If bit 6 = 110 flips, exactly the groups of p4 and p2 contain it. Checks c4 and c2 fail, c1 passes: syndrome 110 = 6. The receiver flips bit 6 back (Demo: flipped data bit 6 is corrected).
A parity bit can flip too. Bit 4 is only in its own group, so the syndrome is 100 = 4 and the data was never wrong (Demo: flipped parity bit 4 is corrected).

This works because position p is in group k exactly when bit k of p is 1. The checks therefore spell out the binary number of the flipped position.

Two errors and code distance

Any two valid Hamming(7,4) codewords differ in at least 3 bits: the minimum distance is 3. A word with one flipped bit is still closest to the codeword it came from, so one error can be corrected. With two flips the syndrome is the XOR of the two positions, which is a third position. Flipping bits 3 and 5 gives 011 ⊕ 101 = 110 = 6, and the receiver "corrects" bit 6, which was fine. Now three bits are wrong and it delivers 0101 instead of 1011 (Demo: two flips, wrong correction). Distance 3 lets a code correct one error or detect two, but not both at once.

SECDED: one more parity bit

SECDED (single error correction, double error detection) adds an overall parity bit p0, the XOR of all seven other bits, at position 0. The distance becomes 4. The receiver checks the overall parity P over all 8 bits as well as the syndrome:

syndrome	overall parity P	meaning	action
0	0 (even)	no error	deliver
≠ 0	1 (odd)	one error at the syndrome position	flip it back ✓
0	1 (odd)	p0 itself flipped	flip p0, data is fine
≠ 0	0 (even)	two errors	report, do not correct ✗

With bits 3 and 5 flipped, the syndrome is 6 but P is even, so the receiver knows two bits flipped and refuses to guess (Demo: SECDED detects two flips). ECC memory in servers uses the same idea on wider words: 64 data bits plus 8 check bits, a (72,64) SECDED code. A single flipped bit in a DIMM is corrected silently and logged; a double flip raises a machine-check error instead of handing wrong data to the program.

Hamming code vs CRC

A cyclic redundancy check only detects errors. It adds few check bits to a long frame (32 bits for an Ethernet frame of up to 1500 bytes) and catches bursts well, but the receiver must drop the frame and wait for a resend. A Hamming code spends more check bits per data bit (3 for 4 here, 8 for 64 in ECC memory) and in return fixes a single error on the spot. That suits memory and storage, where nobody can resend.

	Hamming(7,4) / SECDED	CRC-32
job	correct 1 error (and detect 2)	detect errors only
overhead	3 of 7 bits; 8 of 72 in ECC memory	32 bits per frame
on error	flip the bit back	drop, resend
used in	ECC DRAM, CPU caches, flash	Ethernet, zip, PNG

See also Object Storage: an erasure code (4 data + 2 parity shards) spread over 6 nodes, rebuilding up to 2 lost shards on a GET." — in its see-also / applications paragraph.

What the page leaves out

The page uses a single 4-bit block and at most two flipped bits. It leaves out longer Hamming codes (15,11), (31,26) and the general rule 2^r ≥ m + r + 1 for r check bits, the generator and parity-check matrices, interleaving against burst errors, and stronger codes that fix many errors, such as BCH, Reed–Solomon (CDs, QR codes) and LDPC (Wi-Fi, 5G, SSDs).