A server's memory holds data for months. Every so often a particle strike flips a stored bit. There is no other copy to fetch and no sender to ask for a resend: the memory is the source. Detecting the error is not enough; the bit must be put right, on the fly, on every read, without slowing every access down.

How can a code correct an error, and tell when it cannot?

The obvious answer, and why it breaks

The obvious answer is to detect with parity and recover by fetching the data again. That works for a cache holding a clean copy of memory. It cannot work for memory itself, or for a cache holding the only up-to-date copy of a line. Those need a code that carries enough redundancy to locate the flipped bit, so it can be flipped back.

The idea: a syndrome that points at the error

A Hamming code places check bits so that each data bit is covered by a unique combination of checks. When the receiver recomputes the checks, the pattern of failures, the syndrome, is the binary number of the flipped bit's position. Flip that bit back, and the error is corrected. That gives distance 3: correct one.

Adding one overall parity bit over everything gives distance 4 and the SECDED property (single error correct, double error detect). The decoder combines the two pieces of evidence:

Build it: SECDED encode and decode

The model encodes all 16 four-bit values with the (8,4) extended Hamming code, then tries every single-bit and every double-bit error on every code word.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

"""SECDED: Hamming (7,4) plus an overall parity bit, the (8,4) extended Hamming code.

Encode 4 data bits into 8. On decode, the 3-bit syndrome points at a flipped bit
(positions 1 to 7) and the overall parity says whether an odd number of bits
flipped:
  syndrome 0, parity ok      -> no error
  syndrome != 0, parity bad  -> single error at that position: correct it
  syndrome 0, parity bad     -> the overall parity bit itself flipped: correct it
  syndrome != 0, parity ok   -> two errors: detected, not correctable
"""
from itertools import combinations, product


def encode(d):
    d1, d2, d3, d4 = d
    w = [0, d1 ^ d2 ^ d4, d1 ^ d3 ^ d4, d1, d2 ^ d3 ^ d4, d2, d3, d4]   # index 1..7; 0 unused
    w[0] = sum(w[1:]) % 2                                              # overall parity in position 0
    return w


def decode(w):
    s = 0
    for pos in range(1, 8):
        if w[pos]:
            s ^= pos
    parity_bad = sum(w) % 2 == 1
    if s == 0 and not parity_bad:
        return "ok", w
    if parity_bad:
        fixed = list(w)
        fixed[s] ^= 1                         # s == 0 means the overall parity bit
        return "corrected", fixed
    return "double", None


singles = doubles = 0
for d in product((0, 1), repeat=4):
    w = encode(d)
    assert decode(w) == ("ok", w)
    for i in range(8):
        bad = list(w); bad[i] ^= 1
        status, fixed = decode(bad)
        assert status == "corrected" and fixed == w
        singles += 1
    for i, j in combinations(range(8), 2):
        bad = list(w); bad[i] ^= 1; bad[j] ^= 1
        assert decode(bad)[0] == "double"
        doubles += 1
print(f"data 1011 encodes to {''.join(map(str, encode((1, 0, 1, 1))))} (overall parity first, then positions 1-7)")
print(f"{singles} single-bit errors: all corrected; {doubles} double-bit errors: all detected")
print("PASS: SECDED corrects every single error and detects every double error")

It prints:

data 1011 encodes to 00110011 (overall parity first, then positions 1-7)
128 single-bit errors: all corrected; 448 double-bit errors: all detected
PASS: SECDED corrects every single error and detects every double error

All 128 single errors (16 words × 8 positions) are corrected back to the original, and all 448 double errors (16 × 28 pairs) are reported as uncorrectable, never miscorrected. A triple error, which SECDED does not promise to handle, can look like a single error and be miscorrected: the guarantee stops at distance 4.

Try it

Where ECC sits, and what it costs

The cost is check bits (8 per 64 for SECDED, 12.5%), an encoder on writes, a decoder on reads (adding logic, often a pipeline stage, to every read), and read-modify-write for partial writes, because the code covers the whole word (lesson 5.9).

How real systems chose

• Server memory uses ECC DIMMs storing 72 bits per 64 data bits for SECDED (and stronger schemes on high-end systems).

• Caches often use parity on clean, re-fetchable data and ECC where dirty data may be the only copy.

• Interconnects may carry ECC end to end with the data rather than re-encoding at every hop (lesson 10.14).

What breaks

A memory controller (illustrative) logged corrected single-bit errors but nothing acted on them. One location had a weak cell that flipped often; eventually a second flip in the same word happened between reads, producing an uncorrectable error and a crash. Periodically reading and rewriting memory (scrubbing) corrects single errors before a second one can join them, and tracking repeat offenders identifies failing parts.

Key takeaways

• A Hamming syndrome names the position of a single flipped bit; flipping it back corrects the error.

• An overall parity bit gives SECDED: correct one, detect two, never miscorrect a double.

• Use ECC where data has no other copy; log, scrub and escalate, and budget the decoder's latency.

Related topics

• Part 10 overview: Reliability and Recovery

• RTL course: Memory Reliability