ECC for Flash: Hamming to LDPC

June 12, 2026 16 min read The Physics of Computing

eccldpcnanderror-correctionssdstorage

Contents

Raw NAND flash is, by any honest definition, broken hardware. A fresh TLC die fresh off the wafer will hand you pages with a handful of bit errors; the same die near the end of its rated life will hand you pages with hundreds of errors per kilobyte. No application could tolerate that, and no datasheet promises it directly. What the datasheet promises is an uncorrectable bit error rate (UBER) of one error in 10^15 or 10^16 bits — a number that exists only because a layer of error-correcting code sits between the cell array and your data, turning a raw bit error rate (RBER) of around 10^-3 into a corrected error rate fourteen orders of magnitude lower. The entire economics of flash — denser cells, more bits per cell, lower cost per gigabyte — is a bet that ECC can keep absorbing the worsening physics. This post traces that ECC from the trivial parity bit through Hamming and BCH to the soft-decision LDPC codes that ship in every modern SSD, and connects it back to the millivolts of read window that ECC ultimately spends its life fighting.

Why Raw NAND Is Unshippable

A NAND cell stores data as a threshold voltage (Vt), and reading is a comparison against reference levels in the valleys between Vt distributions. The physics of why those distributions widen, slide, and grow tails — cycling wear, retention loss, read disturb, cross-temperature shift — is covered in how data lives on platters and flash and the read window budget. The consequence for ECC is a single number: RBER, the fraction of bits that come back wrong on a raw read, before any correction.

RBER is not a constant. It is a function of program/erase cycles, retention time, temperature, read-disturb exposure, and which bit of the cell you are reading. A rough envelope for modern 3D TLC:

Condition	Approx RBER	Notes
Fresh SLC	< 1e-6	Trivially correctable
Fresh 3D TLC	~1e-4 to 1e-3	Already needs real ECC
TLC at end of rated P/E	~1e-3 to 1e-2	The design corner
3D QLC near retention limit	up to ~1e-2	The reason LDPC exists

The trend is monotonic and unforgiving. Every density step — MLC to TLC to QLC, planar to 3D NAND, and the QLC/PLC density endgame — packs more Vt states into the same voltage span, narrowing the valleys and pushing RBER up by roughly an order of magnitude per generation. The flash industry did not get away with this because cells got better. It got away with it because ECC got dramatically stronger, on exactly the schedule the physics demanded.

The job, stated precisely: take a per-bit error probability around 1e-3 and deliver a per-bit post-correction error probability around 1e-16. That is the gap ECC has to close.

Parity and Hamming: The Single-Bit Era

The simplest ECC is a single parity bit: XOR every data bit together, store the result, and on read recompute it. A mismatch tells you an odd number of bits flipped. It detects single-bit errors and corrects nothing. Useless for storage, but it establishes the core idea — spend redundant bits to learn something about errors.

Hamming codes are the first real step. By placing parity bits at power-of-two positions, each covering an overlapping subset of data bits, the recomputed parity (the syndrome) is a binary number pointing directly at the failing bit position. A Hamming(n, k) code protects k data bits with n - k parity bits and corrects exactly one error per codeword. Add one global parity bit and you get SECDED — single error correct, double error detect — the same scheme that protects DRAM in ECC RAM.

Hamming SECDED layout (positions are bit indices)

  p1 p2 d1 p4 d2 d3 d4 p8 d5 ... | p_overall
  ^  ^     ^                 ^      ^
  parity at powers of two        global parity = double-error detect

  Syndrome s = recomputed parity bits, read as a binary number:
    s == 0            -> no error (or undetected even-weight error)
    s != 0, p_ov flip -> single error at position s, correctable
    s != 0, p_ov ok   -> double error, detected but NOT correctable

This was enough for SLC NAND. SLC stores one bit per cell, two Vt states, an enormous valley between them, and an RBER low enough that one correctable error per 512-byte sector covered the failure rate with margin. Many early SLC and small embedded parts shipped with nothing more than a Hamming engine in the controller. The moment NAND went to MLC — two bits per cell, four Vt states, valleys cut to a third the width — Hamming was finished. A code that corrects one error cannot survive a medium that produces ten.

BCH: Correcting Tens of Errors

BCH codes (Bose-Chaudhuri-Hocquenghem) generalize Hamming to correct an arbitrary, designed number of errors t per codeword. They are cyclic codes built over a Galois field GF(2^m); encoding and syndrome computation are polynomial arithmetic in that field, and decoding runs a fixed pipeline — compute syndromes, solve for an error-locator polynomial (Berlekamp-Massey), then find that polynomial’s roots (Chien search) to locate the failing bits. The decode latency is bounded and the hardware is compact, which is exactly what a flash controller wants.

The price is parity overhead. To correct t errors over a GF(2^m) codeword you need roughly t * m parity bits. Concrete, real-world configurations:

Codeword data	Correction t	Parity bits	Field
512 B	8	~104	GF(2^13)
1 KiB	24	~336	GF(2^14)
1 KiB	~40	~560	GF(2^14)
2 KiB	~60+	~900+	GF(2^15)

Those parity bits live in the NAND page’s spare (out-of-band) area, which is sized for exactly this purpose. The defining property of BCH for our story is that it is a hard-decision code with a cliff: it corrects up to t errors perfectly and fails completely at t + 1. There is no graceful degradation, no use of the analog detail the NAND can actually provide. As MLC matured into TLC, controllers pushed BCH to t in the tens of bits per kilobyte, but the parity overhead and the hard cliff both became limiting. The valleys were closing faster than t * m parity bits could keep up. The industry needed a code that could squeeze information out of the read itself.

Hard Decision vs Soft Decision, and What “Soft Bits” Are

Here is the conceptual leap. BCH and Hamming consume hard bits: the cell either conducted at the reference voltage or it did not — a single 1 or 0 per bit. But the underlying physics is analog. A cell whose Vt sits a hair to the wrong side of a reference is barely an error; a cell deep into the neighboring distribution is confidently wrong. A hard read throws all of that confidence away.

Soft-decision decoding recovers it. Instead of one read at the nominal reference, the controller performs several reads at reference voltages stepped slightly around the nominal level. Each extra read carves the Vt axis into finer bins. A cell that flips its read result between adjacent reference points sits near the valley center — its value is uncertain. A cell that reads the same way across all the steps sits far from the boundary — its value is reliable.

     count
       ^         state A          state B
       |        ####            ####
       |       ######          ######
       |      ########        ########
       |     ##########      ##########
       +----R-2--R-1--R0--R+1--R+2-----------> Vt
                  |   |   |
   hard read uses only R0 (one comparison)
   soft read adds R-1, R+1 (and maybe R-2, R+2)

   Bin between R-1 and R+1  -> near valley -> LOW confidence -> |LLR| small
   Bin far outside          -> deep state  -> HIGH confidence -> |LLR| large

The output of those multiple reads is quantized into a log-likelihood ratio (LLR) per bit:

LLR(bit) = log( P(bit = 0 | reads) / P(bit = 1 | reads) )

  sign(LLR)  -> the decoder's best guess for the bit (0 or 1)
  |LLR|      -> confidence in that guess
               |LLR| = 0      -> coin flip, no information
               |LLR| large    -> near certain

This is what a “soft bit” physically is: not a fourth state of the cell, but a confidence value derived from where the cell’s Vt falls relative to several closely spaced reference reads. Controllers typically work with a small fixed LLR table — 3 to 4 bits of soft information per cell is common, meaning 1 hard read plus 2 to 6 additional sensing operations, mapped through a pre-characterized table that knows, for this NAND at this wear and retention point, what each bin’s reliability actually is. The LLR table is itself a calibration artifact, related to the factory NAND trim and Vt calibration work — get the table wrong and you feed the decoder confident lies.

The cost is latency. Every extra sense is more time on the bus and in the array. Hard read is the fast path; soft reads are spent only when needed.

LDPC: The Code That Uses the Soft Bits

LDPC (low-density parity-check) codes are linear block codes defined by a sparse parity-check matrix H — sparse meaning each parity check involves only a few bits and each bit participates in only a few checks. That sparsity is the whole point: it admits an efficient iterative decoder that passes probabilistic messages, not hard bits, between two sets of nodes.

Tanner graph (bipartite): variable nodes <-> check nodes

   v1   v2   v3   v4   v5   v6      <- variable nodes (one per coded bit,
    \   |  X  |   |  X  |   /            initialized with the bit's LLR)
     \  | / \ |   | / \ |  /
      c1      c2      c3            <- check nodes (one per parity equation)

  Belief propagation (sum-product / min-sum):
    1. variable nodes send current LLRs to their checks
    2. each check computes what it implies about each connected bit
    3. messages flow back; each bit updates its belief
    4. hard-decide, test H * x_hat == 0; if all checks satisfied, done
    5. else iterate (up to a max iteration cap)

Two properties make LDPC the right tool. First, it is capacity-approaching: with enough length and iterations, LDPC operates remarkably close to the Shannon limit, extracting near the theoretical maximum correction from a given amount of redundancy. Second, and decisively for flash, it consumes LLRs natively. Feed it hard bits and it behaves like a strong block code; feed it the soft LLRs from multiple reads and its correction strength climbs sharply, because belief propagation is designed to weigh uncertain bits less and confident bits more.

This gives flash controllers a tiered strategy instead of a cliff. The decode pipeline degrades gracefully:

Read pipeline (typical, latency increases top to bottom):

  1. Hard read at nominal Vt  ->  LDPC hard decode      (fast, common case)
  2. Read-retry: shift Vt refs ->  LDPC hard decode      (a few retries)
  3. Soft read: 3-4 bit LLRs   ->  LDPC soft decode      (slower, strong)
  4. Deep retry / RAIN recovery / read with neighbor-WL assist
  5. Report uncorrectable (UECC) to host

The trade-off is honest and real. LDPC encoders/decoders are far larger and more power-hungry than BCH engines, the soft-read path multiplies read latency, and LDPC has a error floor — a region at very low RBER where the failure rate stops dropping as fast, caused by small structural patterns (trapping sets) in H. Good code design pushes the floor below the UBER target, but it is a thing controller engineers measure and worry about. FAID and other advanced finite-alphabet decoders exist specifically to beat min-sum on the floor and on raw correction, claiming 10-15% RBER gain.

Read-Retry: Spending Latency to Save a Codeword

Read-retry is the controller’s first move when a hard LDPC decode fails. The Vt distributions have drifted — retention has slid the whole picture one way, cycling has widened the tails — so the nominal reference voltages are no longer centered in the valleys. Retry walks the reference voltages through a sequence of offsets, re-reading and re-decoding at each, hunting for the offset where the references land back in the valleys and the error count drops below what LDPC can correct.

Drifted distributions after retention loss:

   ideal ref ->   |        nominal R sits in the TAIL now
                  v        (lots of misread cells)
        ####    ##|##         ####
       ######  ##|####       ######
      ########.##|######.....########
   --------------|------------------------> Vt
                R0
        better:  R0 - delta  centers in the real valley

  Retry table: try R0-3d, R0-2d, R0-d, R0+d, R0+2d ... decode at each

Each retry is a full re-sense, so retries cost read latency directly, and a drive that is retrying constantly is a drive whose read window budget is nearly exhausted. Modern controllers shortcut the search using the LDPC syndrome itself — the number of unsatisfied parity checks after a failed decode estimates how far off the references are, letting firmware jump toward the right offset instead of scanning linearly. Only after retry and the soft-read path both fail does the controller escalate to die-level redundancy.

RAIN and Die-Level XOR: The Backstop Below ECC

ECC corrects bit errors within a codeword. It does nothing for a whole-page, whole-block, or whole-die loss — a wordline-to-wordline short, a failed plane, a block that programs and reads back as garbage. For those, controllers add a second, coarser layer: RAIN (Redundant Array of Independent NAND), the flash-internal cousin of RAID on disks.

The mechanism is parity by XOR. As pages are written across a stripe spanning multiple dies or planes, the controller XORs them together and stores the running result in a parity page. If any single member of the stripe later comes back uncorrectable from ECC, its contents are reconstructed by XOR-ing the surviving members against the parity page:

RAIN stripe, ratio 7:1 (7 data + 1 parity across 8 dies)

  die0   die1   die2   die3   die4   die5   die6   PARITY
  D0     D1     D2     D3     D4     D5     D6     P = D0^D1^...^D6

  die3 returns UECC after LDPC + retry exhaust:
     D3_recovered = P ^ D0 ^ D1 ^ D2 ^ D4 ^ D5 ^ D6

The stripe-to-parity ratio is a capacity-versus-protection knob. A tight ratio like 7:1 or 11:1 costs that fraction of usable capacity but survives a full die or plane failure; a loose ratio costs less and protects against less. Enterprise drives run tighter ratios than client drives because their UBER target is stricter and their failure consequences worse. RAIN is the layer that turns a catastrophic single-die failure from data loss into a recoverable event — and like all redundancy, it is overhead you pay for on every healthy write to insure against the rare bad one. It pairs naturally with the reliability physics and qualification work that bounds how often those die-level events actually happen.

The UBER Math: From RBER to a Reliability Promise

Now the connection that makes the whole stack a specification rather than a vibe. JEDEC JESD218 defines the UBER target a drive must meet over its rated life: 10^-15 for client SSDs, 10^-16 for enterprise. The question every flash architect must answer is: given my NAND’s RBER at the worst corner of the warranty, and my ECC’s correction capability, do I clear that target?

Model the bits in one codeword as independent with per-bit error probability equal to RBER. A hard-decision code correcting up to t errors fails when the codeword carries more than t errors. The codeword failure probability is the binomial tail:

Given:
  n     = codeword length in bits (e.g. 1 KiB data + parity ~ 9000 bits)
  p     = RBER (per-bit error probability)
  t     = correction capability (max errors the code fixes)

P(codeword fails) = sum over k = t+1 .. n of  C(n,k) * p^k * (1-p)^(n-k)

UBER ~= P(codeword fails) / n      (uncorrectable BITS per bit read)

Plug in numbers to feel the cliff. Take n = 9000, RBER p = 1e-3, so the expected errors per codeword is n*p = 9. A BCH code with t = 9 sits right at the mean — its failure probability is enormous, roughly 0.4, nowhere near any target. Push t to 40 and the tail beyond 40 errors (when the mean is 9) becomes vanishingly small; P(fail) drops below 1e-13 and UBER clears 1e-16 with margin. This is why correction strength had to climb into the tens of bits per kilobyte: you must place t far enough above the mean error count that the binomial tail falls below your UBER divided by n.

Two refinements matter in practice. First, the model assumes independent errors; real NAND has correlated failures (a bad wordline, a leaky cluster), which is precisely what RAIN backstops. Second, soft LDPC has no clean t — its failure probability is a smooth, steep function of RBER that you characterize empirically and that beats any equivalent-overhead BCH by giving the decoder the soft information. The architect’s real shipping criterion, stated plainly:

RBER(end of life, worst corner, worst page) must satisfy:
  P_codeword_fail( RBER, ECC scheme ) / n  <  UBER_target

If hard LDPC fails to clear it -> spend soft reads.
If soft LDPC still fails       -> the part doesn't qualify;
                                  reduce P/E rating, or strengthen ECC,
                                  or improve the NAND.

This is the loop that ties the entire post together. RBER is set by the read window physics. ECC strength and the soft-read budget set how much RBER you can absorb. UBER is the contractual output. When a vendor advertises “3000 P/E cycles at 1-year retention, UBER 1e-16,” they are asserting that the binomial tail closes at that corner with their LDPC and their RAIN — and the qualification flow exists to prove it across thousands of parts before the number goes on a datasheet.

Verdict

ECC is not an accessory bolted onto flash; it is the load-bearing wall that makes flash exist as a product. The arc from Hamming to LDPC is the story of the medium getting steadily worse — more bits per cell, narrower valleys, higher RBER every generation — and the code getting better fast enough to keep the UBER promise intact. Hamming bought the SLC era. BCH carried MLC and early TLC with a hard, predictable cliff. LDPC, by consuming the soft information that multiple-reference reads physically encode as LLRs, broke through to near-Shannon correction and gave controllers a graceful escalation ladder: hard decode, read-retry, soft decode, then RAIN. For a firmware engineer the practical mental model is a latency-versus-correction budget. Hard reads are cheap and common; soft reads and retries are expensive and rare; RAIN is the rare-event backstop; and the binomial UBER math is the referee that says whether the whole stack clears the line at end of life. The trade-offs are real and unglamorous — LDPC silicon is big and power-hungry, soft reads tax read latency and QoS tails, RAIN costs usable capacity, and the error floor is a thing you measure and fear. But the alternative is unshippable hardware. The next time a datasheet quotes UBER 1e-16, read it as what it is: a claim that the binomial tail closes, at the worst corner of the warranty, after the code has done everything the physics will let it.