# Error detection and correction

*Parity, Hamming distance, and ECC*

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.

Group: Number & logic
URL: https://digiwleea.wleeaf.dev/learn/error-codes/

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](https://digiwleea.wleeaf.dev/learn/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.

> **TIP:** 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 `1`s; with **odd parity**, an odd number. The parity bit is just the [XOR](https://digiwleea.wleeaf.dev/learn/xor/) of all the data bits, since XOR counts oddness: it is `1` exactly when the number of `1`s is odd.

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

Worked example with even parity: the data `1011` has three `1`s, 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 `1`s 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.

_Circuit diagram: 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](https://digiwleea.wleeaf.dev/learn/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 XOR d1) XOR d2 = d0 XOR (d1 XOR 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 `1`s are even in number, and the XOR of an even count of `1`s 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 XOR d1 XOR ... XOR dn XOR p   (0 = parity holds, 1 = error detected)
```

1. Encode `1011` with even parity: `p = 1 XOR 0 XOR 1 XOR 1 = 1`, so the transmitted word is `10111`, now carrying four `1`s.
2. Check the clean word: `1 XOR 0 XOR 1 XOR 1 XOR 1 = 0`. The reduction is `0`, the count of `1`s is even, the word passes.
3. 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.
4. 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.

> **KEY:** 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`:

1. Place data in positions 3, 5, 6, 7: the word is `p1 p2 1 p4 0 1 1` (positions 1-7).
2. 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`.
3. Now a flip in transit corrupts position 5: the received word is `0110111`.
4. 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).
5. 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.

> **WARN:** **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.

**Q (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?

**A:** Count the `1`s in `1101001`: there are four, an even number, so the even-parity bit is `0` (the total is already even). After a single flip the count of `1`s becomes odd, so the parity check fails and the receiver **knows an error occurred**. But parity carries no position information, so it **cannot tell which bit flipped** and **cannot correct it**, it can only ask for the word to be resent. Locating the bit would require a Hamming-style code with extra check bits.

> **KEY:** 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](https://digiwleea.wleeaf.dev/learn/ram/) 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.

### FAQ

**Q:** What is a parity bit?

**A:** A parity bit is one extra bit added to a data word so that the total number of `1`s 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.

**Q:** What is the difference between error detection and error correction?

**A:** 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.

**Q:** What is Hamming distance?

**A:** 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)`.

**Q:** How does a Hamming code correct an error?

**A:** 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.

**Q:** What is ECC memory and SECDED?

**A:** 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.