固态硬盘纠错算法的前世今生

纠错编码算法(Error Correction Code, ECC)是传输过程中发生错误后能在接收端自行发现并纠正的码。早期被广泛应用于通信领域，在发送端完成数据编码，在接收端完成数据译码，保证数据的可靠传输。NAND Flash作为一种广泛使用的存储介质，容易受到PE次数、数据保存时间、温度和Cell间干扰等因素的影响，数据写入后再读出无法保证绝对的正确性，因此需要ECC算法做数据恢复。

在2D NAND Flash时代，SSD控制器一般采用BCH编码保护数据正确性，BCH的几个特性

1. 对于固定的码长和码率，有一组固定的生成多项式和校验多项式，不需要单独设计;

2. 有相对固定的编码和译码算法;

3. 当错误数据个数小于一个指定值时，可以100%恢复数据;当数据错误个数大于这个指定值时，100%不能恢复数据;

4. BCH编码只能接收硬信息，即一个有效数据只能用1 bit表示;

但是随着3D NAND Flash技术的逐步成熟，3D NAND Flash表现出了更好的可靠性。因此，原本采用2D MLC的产品纷纷转投3D TLC(可靠性对比： 2D MLC > 3D TLC > 2D TLC)，对SSD主控的ECC编码提出了更高的要求，因此，具备更强纠错能力的低密度奇偶校验编码(Low Density Parity Check, LDPC)越来越多的被采用。

相对于BCH，LDPC具备以下特性：

1. 对于固定的码长和码率，需要单独设计编译码使用的矩阵(通常指校验矩阵);

2. 有多种解码算法，但是最好的纠错算法计算复杂度太高，无法硬件化，需要权衡算法特点和译码精度，简化算法;

3. 可以接收软信息(即一个有效数据可以用多个 bit表示)，这是LDPC取代BCH的主要原因;

4. 译码成功或失败没有绝对的界线，即可能在只错几个bit的情况下无法成功纠错，但可以成功完成200 bit错误的数据译码;

5. 相同码率情况下，码长越长，纠错能力越强;

详细解释一下以上5个特性：

1. 低密度奇偶校验码的低密度是指其校验矩阵的稀疏性(在一个只有“0”元素和“1”元素的矩阵中，“1”元素的比例很低)。LDPC编码和译码都可以利用校验矩阵，矩阵的低密度意味着编译码算法的低复杂度、低运算量。对于固定码长和码率的LDPC码，校验矩阵有很多种，但是设计一个运算量小，复杂度低且纠错能力强的校验矩阵成为LDPC编码应用的一个难点。

LDPC校验矩阵H

2. 麻省理工学院Robert Gallager于1963年在博士论文中提出LDPC码，但因其复杂的译码算法不易实现，并没有被广泛采用。1981年，Tanner提出了用图模型来描述码字的概念，从而将LDPC码的校验矩阵对应到被称为Tanner图的双向图上，采用Tanner 图构造的LDPC码，通过并行译码可以显著地降低译码复杂度。

校验矩阵H对应的Tanner

此后，越来越多的LDPC译码算法出现，其中最流行的是比特翻转算法(Bit Flipping Algorithm)和最小和算法(Min-Sum Algorithm)。同时也出现了很多基于以上2种纠错算法的变种算法，用较小的代价提高了译码精度。

下图描述了一个编码后数据位“1101”，在信道上传输后变为“1001”后接收端的比特翻转译码的过程。

经过一次迭代后，错误bit被纠正。

3.软信息是用多bit表示一个bit的值，即等价于可以用多位精度表示一个信息的置信度。

用硬信息表示一个信息，只有“0”或“1”。而软信息更精确的表达了一个信息的置信度，软信息可以有“0.1”、“0.4”、“0.65”、“0.99”等表达方式。有了软信息，在相同码率下译码器可以纠正更多的错误。

但是存储不同于通信领域，存储器读出的数据只能是0或者1。因此，软信息的获取只能通过改变存储器读方式，多次读取才能获得。多次读取同一个信息必然造成读性能的下降，因此，在SSD控制器上，尽可能减少使用软信息做译码的概率。

4. LDPC是一种概率译码算法，在不同的错误率的情况下均有一个译码成功概率，并且这个概率具备一个明显的特点。当待译码数据错率低时，LDPC译码失败概率很低，可以低至1E-15，但是很难做到0失败，主要原因是对于每个矩阵都存在一个陷阱集，当陷阱集中包含的位置的点发生数据错误，LDPC便无法成功译码。随着错误率逐渐增加，译码失败概率会快速增加到接近100%失败。

5.对于BCH和LDPC，在相同码率下，码长越长，纠错能力越强。对于市场上流行的3D TLC Flash的页大小(页大小决定纠错算法码率)，我们比较了2KB/4KB BCH和2KB/4KB LDPC硬判决译码的纠错能力。当码长增加时，相同的译码算法以及相同的码率下，纠错能力提升了近50%。长码长ECC算法的应用，更好的提高了纠错算法的能力，推迟了SSD主控启用LDPC软判决译码的使用，减少软判决译码带来的负面影响(性能和功耗方面)。

总结：

数据正确性是SSD最基本的要求，纠错编码保证了数据万无一失。随着更多新的Flash结构出现，纠错编码算法也在逐步演进。LDPC算法最大限度的保证了数据的正确性。并且，随着越来越多SSD主控采用4KB LDPC，更好的延长了SSD的寿命。