Error detection and correction

Parity, Hamming distance, and ECC

11 min read

Error-detecting and error-correcting codes add redundant bits to data so that bit flips can be caught (parity) or even located and repaired (Hamming codes), at the cost of extra storage or bandwidth.

Builds onBinary numbers Truth tables

Bits are not perfectly safe. A wire picks up noise, a memory cell weakens, a stray particle flips a stored 1 to a 0. If the data is just raw binary, a flip is silent: the receiver has no way to know the value it read is not the value that was sent. Error codes fix this by adding redundant bits, extra bits computed from the data, so that not every bit pattern is a legal message. A flip turns a legal pattern into an illegal one, and that is the giveaway.

Imagine a teacher who announces a rule before a vote: "there should always be an even number of hands up." If she counts an odd number, she knows immediately that someone miscounted, but she cannot tell *who*. That is exactly a parity bit: enough redundancy to know a mistake happened, not enough to locate it. To pin down which hand is wrong you need more checks, which is the step up from detection to correction.

Parity: one extra bit

The simplest code adds a single parity bit to each data word. With even parity, you choose the parity bit so the whole word (data plus parity) holds an even number of 1s; with odd parity, an odd number. The parity bit is just the XOR of all the data bits, since XOR counts oddness: it is 1 exactly when the number of 1s is odd.

parity = d0 ⊕ d1 ⊕ d2 ⊕ ... (even parity: this makes the total number of 1s even)

Worked example with even parity: the data 1011 has three 1s, an odd count, so the parity bit must be 1 to make the total even. You transmit 1011 plus parity 1. If any single bit flips in transit, the count of 1s becomes odd, the parity check fails, and the receiver knows the word is corrupt. The small generator below computes the parity bit for three data bits as their XOR.

An even-parity generator for three data bits: P = D0 XOR D1 XOR D2. Open it in the lab and toggle the inputs: P is 1 whenever an odd number of the data bits are 1, the extra bit that makes the data-plus-parity word have an even number of 1s.

One XOR tree, generator and checker

That equation, parity = d0 XOR d1 XOR d2 XOR ..., is an XOR reduction: a whole word folded down to a single bit by XOR. Because XOR is associative and commutative, you can pair the bits in any order and any grouping and always land on the same answer, so the reduction can be a chain (as in the generator above) or a balanced XOR tree (shallower, so the signal settles in fewer gate delays). Either shape computes the same value: the word's parity, 1 when an odd number of bits are 1 and 0 when an even number are. This is the bridge worth remembering: an XOR tree over the data bits is a parity generator.

(d0 ⊕ d1) ⊕ d2 = d0 ⊕ (d1 ⊕ d2) (grouping does not matter, so a tree works)

The neat consequence is that the generator and the checker are the same circuit. To encode, XOR the data bits and append the result as the even-parity bit. To check a received word, feed the identical reduction every received bit, the data and the parity bit together: a clean even-parity word always folds down to 0 (its 1s are even in number, and the XOR of an even count of 1s is 0), so a 0 means the check passed and a 1 is the error flag. A parity checker is just a parity generator with the incoming parity bit wired in as one more input.

check = d0 ⊕ d1 ⊕ ... ⊕ dn ⊕ p (0 = parity holds, 1 = error detected)

Encode 1011 with even parity: p = 1 XOR 0 XOR 1 XOR 1 = 1, so the transmitted word is 10111, now carrying four 1s.
Check the clean word: 1 XOR 0 XOR 1 XOR 1 XOR 1 = 0. The reduction is 0, the count of 1s is even, the word passes.
One bit flips in transit, giving 11111: the reduction is 1 XOR 1 XOR 1 XOR 1 XOR 1 = 1. A single flip toggled the one-bit reduction from 0 to 1, so the checker raises the error flag (a parity mismatch), though the flag says nothing about which bit moved.
A second bit also flips, giving 01111: the reduction toggles back to 0 and the corruption slips through, which is exactly why parity is blind to an even number of flips.

Parity is cheap and catches a lot, but notice its limits. It detects any single bit flip, but it cannot tell you which bit flipped, so it cannot repair anything. Worse, it misses an even number of errors: if two bits flip, the count's evenness is unchanged and the check passes, hiding the corruption. Detection without location is the floor; correcting an error needs strictly more redundancy.

Hamming distance: how much a code can do

The power of a code is measured by Hamming distance: the number of bit positions in which two codewords differ. (1011 and 1001 differ in one position, so their distance is 1.) What matters is the code's minimum distance d, the smallest distance between any two legal codewords. To slip from one legal codeword to another undetected, errors must flip at least d bits, which gives two clean rules:

a code of minimum distance d detects up to (d - 1) errors and corrects up to floor((d - 1) / 2) errors

min distance d	errors detected	errors corrected
1	0	0
2	1	0
3	2	1
4	3	1

What each minimum distance buys (the theoretical maxima). Distance 2 is a single parity bit: detect one error, correct none. Distance 3 is the basic Hamming code: correct one error. Distance 4 supports SECDED (correct one, detect two). Each row's correct count is floor((d-1)/2).

A single parity bit has minimum distance 2: any two distinct valid words differ in at least two places (the data differs, and the parity follows). That is why parity detects one error (d - 1 = 1) but corrects none (floor(1/2) = 0). To correct a single error you need distance 3, which means enough check bits to not just notice a flip but pinpoint it.

The Hamming code: locating the bad bit

A Hamming code reaches distance 3 by placing parity bits at the power-of-two positions (1, 2, 4, 8, ...) and filling the rest with data. Each parity bit checks exactly those positions whose index includes its bit. The classic Hamming(7,4) carries 4 data bits and 3 parity bits in positions 1 to 7:

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

Coverage in Hamming(7,4): p1 checks every position whose number has the 1s-bit set, p2 every position with the 2s-bit set, p4 every position with the 4s-bit set. Data sits in positions 3, 5, 6, 7; parity in 1, 2, 4. Each is set for even parity over the positions it checks.

The clever part is decoding. On receipt, recompute each parity check; the checks that fail, read as a binary number (p4 p2 p1), spell the position of the wrong bit. That number is called the syndrome: if it is 0, no single error; otherwise it points straight at the bit to flip. Worked example with data 1011:

Place data in positions 3, 5, 6, 7: the word is p1 p2 1 p4 0 1 1 (positions 1-7).
Set each parity for even coverage: p1 over {3,5,7} = {1,0,1} is even, so p1 = 0; p2 over {3,6,7} = {1,1,1} is odd, so p2 = 1; p4 over {5,6,7} = {0,1,1} is even, so p4 = 0. The codeword is 0110011.
Now a flip in transit corrupts position 5: the received word is 0110111.
Recompute: check 1 over {1,3,5,7} = {0,1,1,1} is odd, fails (c1 = 1); check 2 over {2,3,6,7} = {1,1,1,1} is even, passes (c2 = 0); check 4 over {4,5,6,7} = {0,1,1,1} is odd, fails (c4 = 1).
Syndrome c4 c2 c1 = 101 is binary 5: position 5 is wrong. Flip position 5 back and the data is recovered, with no retransmission needed.

SECDED: correct one, detect two

A plain Hamming code corrects one error but is fooled by two: with two flips the syndrome points confidently at the *wrong* position and "corrects" a good bit, making things worse. The fix is to add one overall parity bit across the entire Hamming codeword, lifting the minimum distance to 4. Now if the syndrome is nonzero but the overall parity still checks out, that mismatch flags a double error the code cannot fix but can at least report. This single-error-correct, double-error-detect scheme is called SECDED, and it is what protects server ECC memory.

Where this is used

Redundant codes are everywhere data is stored or moved. ECC RAM uses SECDED so a single flipped memory bit (a real, if rare, event from background radiation) is corrected silently. Storage (disks, SSDs, optical discs) leans on stronger codes like Reed-Solomon and LDPC that correct whole bursts of errors. Transmission uses lightweight detection (a CRC checksum that flags a bad packet for resend) or forward error correction (enough redundancy to repair errors at the receiver, where resending is impractical, as in deep-space links). The common thread is the trade in the definition: spend extra bits, buy reliability.

Common mistakes. Parity only catches an odd number of flips: two errors cancel and slip through, so parity is not a guarantee, just a cheap check. Three more traps: detection is not correction (a parity bit tells you *that* something is wrong, never *which* bit, which needs minimum distance 3 or more); the Hamming syndrome only locates the bad bit if there is at most one error (two errors send it to the wrong position, which is exactly why SECDED adds an overall parity to flag that case); and the detect/correct maxima in the table are not simultaneous: a distance-4 code does SECDED (correct one *and* detect two), not correct-one-and-also-detect-three.

Try it

Using even parity, what parity bit is appended to the 7-bit data word 1101001? Then a single bit flips in transmission: what can the receiver determine, and what can it not?

Error codes are how digital systems stay trustworthy despite imperfect hardware: a few redundant bits turn silent corruption into something you can detect, and with enough of them, repair. The same idea you just applied by hand scales up to the memory and storage every program depends on, where ECC quietly fixes flipped bits you never see. With binary, hexadecimal, signed numbers, and these codes, the Number & logic foundation is complete, the language the rest of the machine is built in.

Frequently asked

What is a parity bit?

A parity bit is one extra bit added to a data word so that the total number of 1s is even (even parity) or odd (odd parity). It equals the XOR of all the data bits. If a single bit flips, the count's evenness changes and the parity check fails, so the receiver knows the word is corrupt, though it cannot tell which bit changed.

What is the difference between error detection and error correction?

Detection means knowing that an error occurred (a parity bit does this for a single flip); correction means also knowing which bit is wrong so you can repair it without resending. Correction needs more redundancy: a minimum Hamming distance of 3 to fix one error, versus distance 2 to merely detect one.

What is Hamming distance?

Hamming distance is the number of bit positions in which two equal-length words differ. A code's minimum Hamming distance d (the smallest distance between any two legal codewords) sets its power: it detects up to d - 1 errors and corrects up to floor((d - 1) / 2).

How does a Hamming code correct an error?

It places parity bits at the power-of-two positions, each checking the positions whose index includes its bit. On receipt you recompute the checks; the failing ones read as a binary number called the syndrome, which is the position of the bad bit. Flip that bit and the data is restored, with no retransmission, as long as only one bit was wrong.

What is ECC memory and SECDED?

ECC (error-correcting code) memory adds check bits to each stored word so single-bit flips are corrected automatically. It uses SECDED (single-error-correct, double-error-detect): a Hamming code plus one overall parity bit, giving minimum distance 4, so it repairs any single-bit error and at least flags any double-bit error rather than silently mis-correcting it.

Every lesson here builds toward one thing: a working CPU, from the transistor up.

Open the free lab →