Error-Correcting Codes: From Hamming to Reed-Solomon

Noise is the default condition of the universe, and reliable data storage and transmission are the exceptions that require engineering effort to achieve. Every bit you store on DRAM is sitting in a capacitor that leaks charge and can be flipped by a cosmic ray. Every byte you transmit over Wi-Fi passes through a channel that adds thermal noise, multipath interference, and occasional burst errors. The engineers who built the systems you depend on solved this problem with a branch of mathematics called coding theory — the study of how to add structured redundancy to data so that errors can be detected and corrected without retransmission or data loss.

This post works through the key ideas: why simple parity is not enough, how Hamming distance quantifies the error-correction capability of any code, the Hamming(7,4) code worked out completely by hand, why ECC RAM matters at data center scale, Reed-Solomon codes and why they dominate applications that face burst errors, CRCs and the distinction between detection and correction, LDPC codes in modern wireless and NVMe, and erasure coding in distributed storage. The math appears in code blocks where it illuminates — the goal is genuine understanding, not intimidation.

Parity: The Minimal Case and Its Limits

The simplest redundancy scheme is a single parity bit appended to a data word. For even parity, the extra bit is chosen so that the total number of 1s in the codeword is even. For a 7-bit ASCII character 0b1000001 (the letter A), the parity bit is 0; the transmitted byte is 0b10000010.

Data:           1 0 0 0 0 0 1
Parity bit:     0   (count of 1s = 2, already even)
Transmitted:    1 0 0 0 0 0 1 | 0

The receiver checks whether the parity holds. If a single bit is flipped in transit, the parity is violated, and the receiver knows an error occurred. That is all parity can do: detect an odd number of errors. It cannot tell you which bit was flipped, so it cannot correct anything. Two errors leave parity intact and are therefore invisible. For light detection workloads — say, a human typing data where any error is cause for a retransmit — parity is cheap and adequate. For a DRAM module running a data center, it is not enough.

The fundamental limitation of parity is that it has a minimum Hamming distance of 2. To understand why that matters, we need to understand Hamming distance.

Hamming Distance: The Key Concept

The Hamming distance between two binary strings of equal length is the number of positions in which they differ. It is written d(u, v).

1
2
3
4
5
6

def hamming_distance(u: str, v: str) -> int:
    """Count differing bit positions between two codewords."""
    assert len(u) == len(v)
    return sum(a != b for a, b in zip(u, v))

hamming_distance("1010101", "1001100")  # -> 3

For a code — a set of valid codewords — the minimum distance d_min is the smallest Hamming distance between any two distinct codewords. Minimum distance determines what the code can do:

• Detect up to t errors: requires d_min >= t + 1.
• Correct up to t errors: requires d_min >= 2t + 1.

The intuition is geometric. Imagine each codeword as a point in binary n-space. If d_min >= 2t + 1, then every valid codeword has a “correction sphere” of radius t around it, and no two spheres overlap. When an error moves a received word by at most t positions from a valid codeword, it still lies inside exactly one sphere, and you know which codeword was intended.

A single parity bit achieves d_min = 2. It detects one error but corrects nothing. To correct single-bit errors in n-bit data, you need d_min = 3. Richard Hamming, working at Bell Labs in the 1940s, derived the minimum number of parity bits needed for this: with r parity bits, you can protect 2^r - r - 1 data bits. That relationship gives us the Hamming code family.

Hamming(7,4): Worked Out by Hand

The Hamming(7,4) code encodes 4 data bits using 3 parity bits, producing a 7-bit codeword. It has d_min = 3 and corrects any single-bit error. This is the simplest nontrivial single-error-correcting code.

The 7 bit positions are numbered 1 through 7. Positions that are powers of 2 — positions 1, 2, and 4 — are parity bits. The remaining positions — 3, 5, 6, 7 — carry the data.

Position:  1   2   3   4   5   6   7
           P1  P2  D1  P4  D2  D3  D4

Each parity bit covers a set of positions determined by the binary representation of the position numbers:

P1 (pos 1 = 0b001): covers positions 1, 3, 5, 7  (bit 0 of position index is 1)
P2 (pos 2 = 0b010): covers positions 2, 3, 6, 7  (bit 1 of position index is 1)
P4 (pos 4 = 0b100): covers positions 4, 5, 6, 7  (bit 2 of position index is 1)

Encoding example: encode data bits D1 D2 D3 D4 = 1 0 1 1.

Place data bits at their positions:

Position:  1    2    3    4    5    6    7
           P1   P2   D1   P4   D2   D3   D4
           ?    ?    1    ?    0    1    1

Compute each parity bit (even parity over its covered positions):

P1 covers positions {1, 3, 5, 7} → data bits at 3,5,7 are 1,0,1 → XOR = 0 → P1 = 0
P2 covers positions {2, 3, 6, 7} → data bits at 3,6,7 are 1,1,1 → XOR = 1 → P2 = 1
P4 covers positions {4, 5, 6, 7} → data bits at 5,6,7 are 0,1,1 → XOR = 0 → P4 = 0

1
2
3
4
5

data = {3: 1, 5: 0, 6: 1, 7: 1}  # D1..D4 placed at positions 3,5,6,7

p1 = data[3] ^ data[5] ^ data[7]  # 1 ^ 0 ^ 1 = 0
p2 = data[3] ^ data[6] ^ data[7]  # 1 ^ 1 ^ 1 = 1
p4 = data[5] ^ data[6] ^ data[7]  # 0 ^ 1 ^ 1 = 0

The encoded codeword (positions 1–7): 0 1 1 0 0 1 1

Position:  1   2   3   4   5   6   7
Codeword:  0   1   1   0   0   1   1
           P1  P2  D1  P4  D2  D3  D4

Syndrome decoding: suppose bit 5 is flipped during transmission. Received word: 0 1 1 0 1 1 1.

Position:  1   2   3   4   5   6   7
Received:  0   1   1   0   1   1   1
                        ^--- flipped

The receiver recomputes parity checks. Each check should produce 0 if no error occurred in its covered positions. Instead, we get a syndrome:

1
2
3
4
5
6
7

received = {1:0, 2:1, 3:1, 4:0, 5:1, 6:1, 7:1}

s1 = received[1] ^ received[3] ^ received[5] ^ received[7]  # 0^1^1^1 = 1  (error!)
s2 = received[2] ^ received[3] ^ received[6] ^ received[7]  # 1^1^1^1 = 0  (ok)
s4 = received[4] ^ received[5] ^ received[6] ^ received[7]  # 0^1^1^1 = 1  (error!)

syndrome = s4*4 + s2*2 + s1*1  # = 1*4 + 0*2 + 1*1 = 5

The syndrome value — treated as a binary number — gives the position of the flipped bit directly: position 5. Flip bit 5, and the data is recovered. This is the elegance of Hamming codes: the syndrome encodes the error position in binary, so no lookup table is needed.

ASCII layout of Hamming(7,4):

     ┌──────────────────────────────────┐
     │  P1  P2  D1  P4  D2  D3  D4     │
     │  [1] [2] [3] [4] [5] [6] [7]    │
     │   |   |   |   |   |   |   |     │
     │  P1───────────────────────┘ ─── covers {1,3,5,7}
     │  P2──────────────────┘     ─── covers {2,3,6,7}
     │             P4──────────┘  ─── covers {4,5,6,7}
     └──────────────────────────────────┘

The Hamming(7,4) code has an overhead of 3/7 ≈ 43 percent. More data bits push that overhead down: Hamming(15,11) adds 4 parity bits to 11 data bits — only 27 percent overhead while still correcting any single-bit error. This is the SECDED (Single-Error-Correct, Double-Error-Detect) family used in ECC RAM, typically with one extra parity bit that detects (but does not correct) two-bit errors.

Why ECC RAM Matters at Scale

DRAM stores each bit as a charge on a capacitor measured in femtofarads. The capacitor leaks. Refresh cycles compensate, but between refreshes, sufficient charge can drain to flip the bit — or cosmic ray ionization can deposit enough charge to flip it the other way. These events are called soft errors or Single Event Upsets (SEUs).

The rate seems negligible: studies from the 2000s measured roughly 1 error per gigabyte per month in consumer DRAM, or about 10^-9 per bit-hour. The problem is scale. A server with 512 GB of DRAM has:

512 * 1024 * 1024 * 1024 * 8 bits = ~4.4 * 10^12 bits

Expected errors per month:
  4.4e12 bits * (1 error / (1e9 bit-hours)) * (24 * 30 hours/month)
= 4.4e12 * 7.2e-4
≈ 3.2 errors per month

A single uncorrected DRAM bit flip in a kernel data structure can crash the OS, corrupt a filesystem, or — more insidiously — silently produce wrong results in a scientific computation. Bianca Schroeder’s seminal 2009 study of Google’s production fleet found that DRAM errors were far more common than vendors admitted, with some DIMMs showing error rates orders of magnitude higher than the nominal specification.

ECC RAM adds one SECDED check byte per 8-byte word (a 72-bit chip select instead of 64-bit), implemented on the memory controller using exactly the Hamming scheme described above. Single-bit errors are silently corrected; double-bit errors cause a Machine Check Exception rather than a silent corruption. For production servers, ECC is not optional — it is the baseline. The ZFS homelab guide on this site makes this point in the context of filesystem integrity: ZFS checksums catch corruption that survives ECC (multi-bit errors, wrong-address writes, controller bugs), but ECC is what prevents the DRAM holding the kernel page cache from silently corrupting data before ZFS ever sees it.

For TrueNAS deployments, the TrueNAS SCALE deep dive notes ECC as a hard requirement before any discussion of pool configuration. The reason is not paranoia: a file server without ECC running ZFS will appear to be working correctly until a DRAM bit flip corrupts a block in the ARC, which ZFS then writes back to disk with a valid checksum on the bad data.

Reed-Solomon: Polynomial Codes Over Finite Fields

Hamming codes are binary: they work over the field GF(2) where addition is XOR. Reed-Solomon codes work over larger finite fields — typically GF(2^8), where each “symbol” is a byte. This moves from single-bit error correction to burst-error correction, which is the regime that matters for CDs, DVDs, QR codes, and RAID 6.

The key idea is polynomial interpolation. Given k data symbols, treat them as coefficients of a degree-(k-1) polynomial over GF(2^8). Evaluate that polynomial at n distinct points to produce n codeword symbols. Because a polynomial of degree k-1 is uniquely determined by any k of its evaluations, you can recover the original data from any k of the n codeword symbols — even if n-k symbols are lost entirely.

Data: k symbols  →  Polynomial p(x) of degree k-1 over GF(2^8)
Encode: evaluate p(x) at points α^0, α^1, ..., α^(n-1)  →  n codeword symbols
Decode: given any k of the n evaluations, recover p(x)  →  original k symbols

This is not just error-correction; it is erasure correction. An erasure is an error whose location you already know (a scratched CD sector, a failed RAID disk). Correcting erasures is strictly easier than correcting errors of unknown position, because with erasures you only need k evaluations — any k out of n — to reconstruct the polynomial.

Burst Errors and Why Binary Codes Are Poor at Them

A hard disk scratch or a CD surface defect does not flip one bit: it obliterates a contiguous block — many bytes in a row. A binary code like Hamming can correct t individual bit errors, but a 100-bit burst error (100 consecutive flipped bits) overwhelms it completely. Reed-Solomon operates on symbols (bytes), so a 100-bit burst that destroys 13 bytes contiguously looks like 13 symbol erasures — and RS(255,223) handles up to 32 symbol erasures. That is the design match: use byte-level codes for media that fails in byte-sized bursts.

CD cross-interleaved Reed-Solomon (CIRC) layout (simplified):

 Audio samples (16-bit stereo, 44.1 kHz)
     │
 ┌───▼──────────────────────────────────────────┐
 │  C2 (inner code): RS(32,28) — corrects 2 bytes  │
 │  Each 24-byte data frame → 28+4=32 symbols    │
 └───────────────────────────┬──────────────────┘
                             │ interleaver (4-frame delay)
 ┌───────────────────────────▼──────────────────┐
 │  C1 (outer code): RS(28,24) — corrects 2 bytes  │
 │  Handles burst errors the interleaver spreads │
 └──────────────────────────────────────────────┘

The interleaver between the two RS stages is crucial. It scatters adjacent bytes across 4-frame windows so that a physical scratch — which hits contiguous bytes on the disc — is dispersed into isolated symbol errors when the interleaver undoes its work. The combination of interleaving and two-level RS is why a badly scratched CD still plays: the decoder can tolerate 4000 consecutive erroneous bits (approximately 2.5 mm of scratch length) without audible artifacts.

Reed-Solomon in QR Codes

QR codes divide their data capacity into three zones: data codewords, Reed-Solomon error correction codewords, and structural patterns. At “medium” correction level (about 15 percent of codewords recoverable), a QR code tolerates roughly 15 percent of its surface being obscured before decoding fails. This is why QR codes can carry a logo overlaid in the center: the logo occupies part of the code area, but the RS redundancy absorbs it as erasures.

RAID 6 and Erasure Coding

RAID 6 extends RAID 5 (one XOR parity disk) with a second parity disk using a different calculation, typically the Reed-Solomon style P+Q scheme. P is the standard XOR parity; Q is computed using GF(2^8) polynomial arithmetic with a different generator. Together, P and Q allow recovery from any two simultaneous disk failures.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# RAID 6 P+Q parity (simplified GF(2^8) concept)
# P: bitwise XOR of all data disks (Hamming-style)
# Q: weighted XOR using powers of a primitive element alpha

def compute_parity(data_disks: list[bytes]) -> tuple[bytes, bytes]:
    n = len(data_disks[0])
    p = bytes(n)
    q = bytes(n)
    for i, disk in enumerate(data_disks):
        p = bytes(a ^ b for a, b in zip(p, disk))          # P = XOR
        gf_coeff = gf_pow(ALPHA, i)                         # alpha^i in GF(2^8)
        q = bytes(a ^ gf_mul(gf_coeff, b)                   # Q = sum(alpha^i * d_i)
                  for a, b in zip(q, disk))
    return p, q

The Shannon information theory post on this site provides the theoretical underpinning: Shannon’s channel capacity theorem establishes the theoretical maximum rate at which error-free communication is possible over a noisy channel. Reed-Solomon codes approach this bound for channels with known erasure patterns. The queueing theory and capacity planning post connects to similar themes about modeling reliability under uncertainty: just as queueing theory asks “how much headroom do I need to avoid saturation under bursty load,” coding theory asks “how much redundancy do I need to survive bursty errors.”

CRCs: Detection Without Correction

A Cyclic Redundancy Check (CRC) is a hash computed by treating the data as a polynomial over GF(2) and dividing by a fixed generator polynomial. The remainder of that division — typically 16 or 32 bits — is the CRC. It appended to the data; the receiver recomputes it and compares.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def crc32(data: bytes, poly: int = 0xEDB88320) -> int:
    """CRC-32 (IEEE 802.3 polynomial, reflected bit order)."""
    crc = 0xFFFFFFFF
    for byte in data:
        crc ^= byte
        for _ in range(8):
            if crc & 1:
                crc = (crc >> 1) ^ poly
            else:
                crc >>= 1
    return crc ^ 0xFFFFFFFF

CRCs have useful algebraic properties:

• CRC-32 detects all single-bit errors.
• CRC-32 detects all burst errors of length <= 32 bits.
• CRC-32 detects ~99.9999998% of longer burst errors (any specific error pattern has a 1-in-2^32 chance of being missed).

What CRCs do not do: correct errors. They identify whether the data is intact, but a CRC failure requires a retransmit or a failure signal — there is no path back to the original data from the CRC alone. This makes CRCs the right tool for integrity checking with retransmit capability: TCP segments, Ethernet frames, ZIP files, PNG chunks, Git objects. When retransmission is not possible (archived data, storage without a backup), you need error-correcting codes, not CRCs.

LDPC Codes: Near-Shannon Performance in Practice

Low-Density Parity-Check (LDPC) codes were invented by Robert Gallager in 1960 and largely ignored for three decades until computers became fast enough to run the iterative decoding algorithm. They are now the dominant forward-error-correction scheme in 802.11n/ac/ax Wi-Fi, 10GbE, and NVMe SSDs.

The “low-density” refers to the parity check matrix H: each row has only a small number of 1s (the parity equations are sparse). Decoding uses belief propagation, an iterative message-passing algorithm on a bipartite graph connecting variable nodes (bits) to check nodes (parity constraints). At each iteration, each node updates its belief about the correct value based on messages from its neighbors. The algorithm converges — usually in tens of iterations — to either the correct codeword or a decoding failure.

Belief propagation (sketch):
  Initialize: each bit node holds a log-likelihood ratio from the channel
  Iterate:
    Check-to-variable messages: "given all my other connected bits, here is
      my belief about this bit's value"
    Variable-to-check messages: "given my channel observation and all other
      connected check nodes, here is my belief"
  Until: all parity checks satisfied (success) or max iterations reached

LDPC codes come within a fraction of a dB of the Shannon limit for AWGN channels — the theoretical maximum. For 802.11ax (Wi-Fi 6), rate-5/6 LDPC codes protect MCS11 (1024-QAM 5/6) transmissions at the high end of the modulation table. For NVMe SSDs, LDPC codes in the NAND controller compensate for the increasing raw bit-error rates of fine-geometry (sub-10 nm) flash cells, which may have raw BERs of 10^-3 to 10^-2 that the LDPC code reduces to effectively zero at the protocol level.

The tradeoff with LDPC is decoder complexity. Belief propagation is an iterative algorithm with variable latency; error floors can cause decoding failures at low BER if the code graph has short cycles. Hardware LDPC decoders in NVMe controllers are significant silicon investments. For Wi-Fi baseband chips, they account for a material fraction of the power budget at high data rates.

Erasure Coding in Distributed Storage

Erasure coding generalizes Reed-Solomon to distributed storage: instead of protecting against bit errors on a single medium, it protects against entire node or disk failures. The encoding is the same polynomial interpolation concept — split k data chunks into n codeword chunks such that any k of the n suffice to reconstruct the original — but deployed across n distinct storage nodes.

Ceph supports multiple erasure code profiles. The default is Jerasure with Reed-Solomon over GF(2^8), configurable as (k, m) where k is the number of data chunks and m is the number of parity chunks. Common production configs:

1
2
3
4
5
6
7

# Ceph erasure code profile: 4 data + 2 parity = tolerates 2 node failures
ceph osd erasure-code-profile set myprofile \
  k=4 m=2 plugin=jerasure technique=reed_sol_van

# 8+3 for high-capacity tiering (3 failures tolerated, 27% overhead)
ceph osd erasure-code-profile set archive \
  k=8 m=3 plugin=jerasure technique=reed_sol_van

Overhead is (n-k)/n = m/n. For k=4, m=2: 2/6 = 33 percent overhead. Compare to 3-way replication: 200 percent overhead. For cold storage tiers with large objects (backups, video archives), erasure coding cuts storage cost by a factor of 3 relative to triple replication while providing equivalent or better durability.

Amazon S3 uses a proprietary variant internally. The publicly documented implementation uses a 14+6 scheme for some storage classes: 14 data shards distributed across availability zones plus 6 parity shards. Losing 6 entire shards (which might correspond to an entire AZ) still permits reconstruction.

The cost of erasure coding versus replication is read amplification and partial-write overhead. Reading a single object from an erasure-coded pool may require fetching k shards from k different nodes and decoding them — k network round-trips instead of 1. Writing a small update to a large erasure-coded object requires reading the full stripe, computing new parity, and writing k+m shards — the “read-modify-write” penalty. Replication is better for hot data with small random writes; erasure coding is better for cold, write-once, read-sequentially data.

Erasure coding storage overhead comparison:

  Replication 3x:   data ─► [copy1] [copy2] [copy3]
                    overhead: 200%   failure tolerance: 2 nodes

  EC(4,2) 6 shards: data ─► [D1][D2][D3][D4][P1][P2]
                    overhead: 50%    failure tolerance: 2 nodes

  EC(8,3) 11 shards:data ─► [D1..D8][P1][P2][P3]
                    overhead: 37.5%  failure tolerance: 3 nodes

Verdict

The hierarchy of error correction in a modern data stack is layered. At the hardware level, DRAM uses SECDED Hamming codes to silently correct the bit flips that happen continuously in any large memory array. At the channel level, LDPC codes push Wi-Fi and NVMe toward the theoretical limit of the Shannon bound. At the media level, Reed-Solomon codes handle the burst errors that binary codes cannot: CD interleaved CIRC, QR code zones, RAID 6 P+Q parity. At the integrity level, CRCs provide cheap detection with the assumption that retransmission is available. At the distributed storage level, erasure coding extends the polynomial interpolation of Reed-Solomon to multi-node failure tolerance with fraction of the overhead of full replication.

Parity is not wrong — it is a special case of all of these. It is the point on the curve where redundancy is one bit and correction capability is zero. Everything else is moving along that curve, trading compute for the ability to recover from a noisier world. The practical decisions — which code to use, how much overhead to accept, whether to optimize for random errors or burst errors or erasures — are engineering tradeoffs, but they all rest on the same geometric intuition: spread valid codewords far apart in Hamming space, and errors that move you a short distance still land you close to the right codeword.

Sources

• Hamming, R. W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal 29(2): 147–160. The original paper.
• Reed, I. S., & Solomon, G. (1960). “Polynomial Codes Over Certain Finite Fields.” Journal of the Society for Industrial and Applied Mathematics 8(2): 300–304.
• Gallager, R. G. (1960). Low-Density Parity-Check Codes. MIT doctoral dissertation.
• Schroeder, B., Pinheiro, E., & Weber, W. (2009). “DRAM Errors in the Wild: A Large-Scale Field Study.” ACM SIGMETRICS 2009. Google’s empirical study of production DRAM error rates.
• Moon, T. K. (2005). Error Correction Coding: Mathematical Methods and Algorithms. Wiley. Comprehensive graduate-level treatment with worked examples.
• Lin, S., & Costello, D. J. (2004). Error Control Coding (2nd ed.). Prentice Hall. The standard reference text.
• Plank, J. S. (2009). “The RAID-6 Liberation Codes.” USENIX FAST 2008. Concrete GF(2^8) RAID 6 implementation.
• IEEE 802.11ax-2021 (Wi-Fi 6 standard). Section 27.3.12: LDPC encoding procedure.
• Ceph documentation: Erasure Code Plugin – Jerasure. https://docs.ceph.com/en/latest/rados/operations/erasure-code-jerasure/
• Peterson, W. W., & Brown, D. T. (1961). “Cyclic Codes for Error Detection.” Proceedings of the IRE 49(1): 228–235. Foundation paper for CRCs.