Error Detection and Correction
Extra bits that catch (and sometimes fix) corrupted stored or transmitted data.
Description
Stored and transmitted bits can flip. Parity adds one bit to detect any single-bit error. Hamming codes add several check bits placed at power-of-two positions so the syndrome points directly at the bad bit, enabling single-error correction (and, with an extra parity bit, double-error detection — SECDED).
- Even parity: append a bit so the total number of 1s is even.
- Detects any single (odd) bit error; cannot locate or fix it.
- Parity bit = XOR of all data bits.
- Two flipped bits go undetected (even count).
- Cheap: one extra bit per word.
- Check bits sit at positions 1, 2, 4, 8, … (powers of two).
- Each check bit covers a fixed subset of data positions.
- On read, recomputed checks form a syndrome.
- A non-zero syndrome's value = the position of the flipped bit → flip it back.
- Add one overall parity bit to also detect double errors (SECDED).
At a glance
What
Redundant check bits added to data to detect and/or correct bit errors.
Why
Memory and links occasionally flip bits; silent corruption is unacceptable.
How
Parity = XOR of data bits. Hamming = multiple overlapping parity checks → a syndrome.
Where
ECC RAM, storage, communication links, spacecraft electronics.
When
Whenever data integrity matters more than a few extra bits.
Think of it like…
Parity is a single lookout shouting 'something's wrong'. A Hamming code is several overlapping lookouts whose combined report pinpoints exactly which soldier fell out of line.
Parity
- Even parity: append a bit so the total number of 1s is even.
- Detects any single (odd) bit error; cannot locate or fix it.
- Parity bit = XOR of all data bits.
- Two flipped bits go undetected (even count).
- Cheap: one extra bit per word.
Hamming code (SEC / SECDED)
- Check bits sit at positions 1, 2, 4, 8, … (powers of two).
- Each check bit covers a fixed subset of data positions.
- On read, recomputed checks form a syndrome.
- A non-zero syndrome's value = the position of the flipped bit → flip it back.
- Add one overall parity bit to also detect double errors (SECDED).
Capability
| Scheme | Detect | Correct |
|---|---|---|
| Parity (1 bit) | 1-bit error | no |
| Hamming (SEC) | 1-bit | 1-bit |
| SECDED | 2-bit | 1-bit |
Hamming check-bit count
| Data bits | Check bits (2^k ≥ m+k+1) |
|---|---|
| 4 | 3 |
| 8 | 4 |
| 16 | 5 |
| 32 | 6 |
Real-world applications
The 5 Whys
- 1
Why check bits? Bits flip in memory and on links.
- 2
Why parity? Cheapest single-error detection.
- 3
Why Hamming? Overlapping checks locate the bad bit.
- 4
Why power-of-two positions? So the syndrome reads out as the error's address.
- 5
Root cause: structured redundancy converts 'an error exists' into 'this exact bit is wrong'.
Cheat sheet
Working principle
- Parity = XOR of data bits. Hamming = multiple overlapping parity checks → a syndrome.
- Redundant check bits added to data to detect and/or correct bit errors.
Formulas & Boolean expressions
- Even parity P = d₀ ⊕ d₁ ⊕ … ⊕ dₙ₋₁
- Hamming: 2^k ≥ m + k + 1
- Syndrome = position of error bit
- Parity bit = XOR of all data bits.
- A non-zero syndrome's value = the position of the flipped bit → flip it back.
- 4 = 3
- 8 = 4
- 16 = 5
Key facts
- Even parity: append a bit so the total number of 1s is even.
- Check bits sit at positions 1, 2, 4, 8, … (powers of two).
Why it exists
- Root cause: structured redundancy converts 'an error exists' into 'this exact bit is wrong'.