LDPC algorithm for SSD

NAND闪存中的错误检测和校正

当前的信息时代强调了无论是存储，检索，传输还是分析数据，不仅需要速度，而且还要求准确性。考虑到每分钟内生成的关键信息量，即使是最轻微的错误也可能带来灾难。随着闪存几何尺寸的缩小，错误率也会增加，需要更强大的纠错算法来确保闪存设备的可靠性。

坏块

坏块是具有一个或多个无效位的块。它们可能不可用或较弱，并且容易出错。它们甚至可能出现在新设备中，并且可能在设备的生命周期内不断扩展。

NAND闪存存储设备中有两种类型的坏块：

• 初始坏块。 NAND闪存设备可能附带许多坏块。在设备出厂之前，会映射坏块的位置，并且通常会实施坏块管理算法，其中通过读取闪存设备中的所有备用区域来创建坏块表在工厂的测试和验证过程中会识别出无效的块。坏块表将保存在好块中，因此设备可以在重新启动（Micron）时加载它。
• 新增或后期坏块。随着设备严格使用，在正常使用中，由于正常使用期间的损耗，数据块中的数据可能会丢失或损坏，从而导致读/写干扰错误，保留错误和其他问题。因此，损坏的块导致存储的数据无法访问，应用程序或操作系统可能无法打开。随着坏块的增加，驱动器容量降低，性能降低，最终导致设备故障。

NAND闪存性能下降和位错误

纠错码用于检测和纠正位错误。在闪存的早期，使用了个位错误代码，但是随着比例缩放变得越来越普遍，单元的大小减小了，每个单元的比特数增加了。以下因素影响闪存性能下降和误码率的上升。

• 编程/擦除（P / E）周期。编程(写入)和擦除的恒定周期要求对NAND单元施加高压，从而在隧穿氧化层上造成应力并削弱隧穿氧化层。

​

图1. NAND闪存单元上的编程（写入）和擦除操作需要施加高电压，这会在隧道氧化物上产生应力。随着P / E周期的增加，隧穿氧化层变弱，导致电子从浮栅泄漏，而NAND闪存单元性能下降

• 每个单元拥有更多位。为了提高密度，新的闪存技术已使一个单元中可以存储更多位，从而缩小了电压阈值（V_T）分布之间的差距，从而导致电压偏移，并由于单元间干扰而导致误码。

图2. 每个单元存储的更多位提供更高的密度/容量，但同时也增加了单元间干扰，因为单元之间更加紧凑。对一个单元的读取或写入可能会影响其他相邻单元，并导致误码。

ATP NAND闪存设备中的错误检测和纠正

纠错码(ECC)是用于纠正NAND闪存中的错误的技术，可恢复由于误码而损坏的数据。内部ECC机制可以检测/纠正一定数量的错误。

其他闪存产品采用的ECC的一个示例是汉明代码。该算法于1950年发明，以其发明者Richard Hamming命名，可以检测和纠正1位错误，但只能检测不纠正2位错误。由于其有限的纠错能力，它易于实现，并且广泛用于单级单元（SLC）闪存中，该闪存结构更简单，只需要单比特ECC。流行的汉明码是7、4，其中，在7位块中，只有4位由数据组成，其余3位是纠错码。

下面是在2 KB页面上使用2048字节用户数据的汉明代码的示例实现。 （在页面大小超过512字节的闪存设备中，数据分为512字节的部分， 每个部分使用一个汉明码表示512字节。

图3. 2 KB页面的汉明代码实现示例， 每个512 KB节的汉明码存储在备用区域中。

市场上的某些产品仅使用简单的汉明码，而ATP产品则采用可纠正多个位错误的高级ECC。

以下部分介绍了应用于ATP闪存设备的错误检测和纠正机制：

Reed-Solomon算法

Reed-Solomon算法由麻省理工学院的林肯实验室的工程师Irving Reed和Gustave Solomon于1960年发明，Reed-Solomon算法涉及将多余/冗余数据添加到数字数据块中。它通常用于硬盘驱动器和光盘，以及NAND闪存中，通常用于处理NAND闪存的位翻转。当一个单元上的操作由于彼此之间构建的存储单元太近而在另一单元上造成干扰时，就会发生位翻转。当发生位翻转时，一个单元的浮栅可能由于另一个单元的干扰而获得（被编程）或失去（被擦除）电子。

Reed-Solomon对符号进行正确编码，因此被认为非常适合于错误集中在一起的应用程序。Reed-Solomon算法广泛用于纠正单个页面中的多位错误，但在处理大的消息块时性能可能很差，当块大小增加一倍时，编码或解码数据的时间大大增加。

流行的Reed-Solomon码是带有8位符号的RS（255，247）。每个代码字包含255个代码字字节，其中247个字节是数据字节，而8个字节是奇偶校验字节。解码器可以纠正代码字中的任何4个符号错误。

目前，一些ATP flash产品使用512字节上的4字节编码实现Reed-Solomon编码。这意味着这些产品上的ECC机制可以每512B纠正至少4位错误。但是，在最佳情况下，只要这32位错误位于相同的4个符号之内，它最多可以校正每512B 32位错误。

BCH (Bose, Chaudhuri, Hocquenghem) 算法

BCH编码于1959年由Alexis Hocquenghem发明，并于1960年由Raj Bose和D.K. Ray-Chaudhuri独立开发。BCH码可以纠正多位错误，并且可以处理随机错误和突发错误。BCH编码的主要优点是可以使用一种称为“综合征解码”的方法轻松地解码。BCH编码要求低冗余度，广泛应用于卫星通信、光盘驱动器和条形码。

与Reed-Solomon算法具有更强大的纠错能力，但需要大量系统资源来实施相比，BCH算法因其提高的效率，能够检测高度集中和广泛分散的错误而变得流行起来。另一个优点是编码和解码技术相对简单，并且BCH代码需要少量的冗余。 

LDPC（低密度奇偶校验）

LDPC代码，也称为Gallagher代码，以纪念其开发者Robert G. Gallagher，是一种强大的错误纠正算法，首次提出于1962年在麻省理工学院的博士论文，但直到大约10年前才得到广泛的应用。它们具有解码软位数据和硬位数据的能力，因此在企业界越来越多地被使用。在Gallagher的论文中，低密度奇偶校验码被定义为“线性二进制块，其感兴趣的奇偶校验矩阵的1密度较低” 这意味着1比0要少。

LDPC相对于其他算法的优势：

• 低解码复杂度
• 在解码过程中同时使用NAND闪存中的硬位和软位信息
• 短块展示出良好的性能
• 提供长块的“近容量”性能。 （近容量是指香农极限，指的是数据通过接近或接近零误差的信道发送的最大速率）

表1. 样本LDPC奇偶校验矩阵

图4. Tanner图显示了表1中给定奇偶校验矩阵的LDPC码的图形表示，并有助于描述解码算法。 “校验节点”代表奇偶校验位的数量，“变量节点”代码中的位数。仅当位包含在奇偶校验中时，边缘才将位节点连接到校验节点。

总结

下表提供了本文讨论的ECC算法的比较。

（来源：NAND闪存中的纠错码）

表2. ECC机制的比较

随着NAND闪存光刻技术的发展，单元的几何尺寸缩小，每个单元存储更多的位，密度增加，但错误位也增加。 为了确保其工业闪存产品的可靠性，ATP采用了先进的错误检测和纠正技术。

更多信息，请访问ATP网站或联系ATP代表/经销商。