LDPC (NAND ECC)
An LDPC code is an error-correcting linear block code defined by a sparse parity-check matrix.
In NAND, repeated sensing can supply confidence information for iterative decoding; the code family alone does not specify the recovery policy.
In the 2011 simulation, BCH dimensions (n,k)=(9152,8256) and LDPC dimensions (9118,8225) give different exact rates that both round to 0.9021. The tested LDPC code with hard decisions was only slightly better than the BCH baseline, while one extra bit of reliability from additional reads recovered almost all of the gain of full soft information. [2] For four-level cells, six reads recovered more than half of the gap between three-read hard decoding and full soft precision, with diminishing returns per read. [3]
With a rate-8/9 code over 4 KB, soft decoding with six extra sensing levels tolerated about three times the raw bit error rate of BCH at a failure target of 1e-15, while hard-decision LDPC tolerated only slightly more. Seven-level sensing took about 125 µs and transferring the results about 80 µs, against about 8 µs of decoding. Trying hard decisions first still lengthened reads by 25 to 120% at 10,000 program/erase cycles, with a 28.8% hard-decoding failure probability. [5]
With 83 µs per hard read and 213 µs per soft read, a 28.8% fallback rate gives an average of 83 + 0.288 x 213 = about 144 µs. Read thresholds that maximise mutual information also minimise frame errors for a well-designed code, but not for a code with a high error floor from small absorbing sets. [3]
Relations
- related
- NAND flash, Solid-state drive (SSD), Bad block management, Reed–Solomon codes (storage), NAND read-retry, Soft-decision decoding, Log-likelihood ratio, Bit error rate, Error-correcting code, Codeword (storage ECC), Raw bit error rate, Uncorrectable bit error rate, SSD controller, Code rate
Advantages
- Combining look-ahead sensing, progressive sensing and data-placement interleaving reduced the worst modeled read-response-time increase from over 100% to below 20% in the studied traces. [5]
Limitations
- The best code at one read precision is typically not the best at another, so code and quantisation have to be designed together. [3]
Citations
- Wang, Courtade, Shankar and Wesel. Soft Information for LDPC Decoding in Flash: Mutual-Information Optimized Quantization. IEEE GLOBECOM 2011, sections II-IV.
- Wang et al. Enhanced Precision Through Multiple Reads for LDPC Decoding in Flash Memories. Author manuscript arXiv:1309.0566v4, 2014, sections IV and V.D.
- Zhao, Zhao, Sun, Zhang, Zhang and Zheng. LDPC-in-SSD: Making Advanced Error Correction Codes Work Effectively in Solid State Drives. USENIX FAST 2013.
Further reading
Sources & caveats
- The 2011 and 2014 papers have a co-author at a chip company (Inphi), which also supported the 2014 work with a gift; the 2013 study is university work.
- All three results are simulations on modelled or specifically measured chips with codes designed by the authors.
- Latencies and the 28.8% failure probability are from 25 nm planar MLC devices of the time and one simulator, not from current devices.
- Arithmetic: 8,256 / 9,152 and 8,225 / 9,118 both round to 0.9021; 55 + 20 + 8 = 83 µs and 125 + 80 + 8 = 213 µs; the 144 µs average ignores queueing and lower pages and lies within the paper's 25 to 120% range.