Error Correction in SSD #
BCH has served as de facto SSD ECC algorithm for years, now replaced by LDPC, which features a multi-stage complex decoding process. The Quasi-Cyclic LDPC is efficient thanks to hardware implementation: shift register-based circuits 1. Reed-Solomon Code RS (255, 247)
(247 bytes of data, 8 bytes of parity, corrects 4 bits per 512B) is also adopted.
LDPC Read #
The MLC SSD cell is sensed with multiple threshold voltages, the sensed data is transferred to LDPC decoder in the controller to calculate its log-likelihood ratio. If the decoding fails, another threshold voltage is attempted.
See Yu Cai et al. 3, sec 5.1.2. for full LDPC walk-through
Hard decoding first applies a fixed threshold voltage. If it contains uncorrectable error, soft sensing uses multiple threshold voltage to iteratively identify which bit is most likely erroneous.
Error Correcting Code Theory #
The goal of error correction is to find a mapping from length-$k$ data to length-$n$ codeword such that the minimum Hamming distance between two codewords is maximized (so that it tolerate more errors)
- Hamming code has small distance and practical encoding/decoding time
- Hadamard code has large distance but its rate is very low
- Concatenated error correction code: can get the best of both world