所有型号的闪存都无法保证存储的数据会永久稳定，这时候就需要ECC（纠错码）去给闪存纠错。ECC能力的强弱直接影响SSD的使用寿命和可靠性。本章将简单介绍ECC的基本原理和目前主流的ECC算法——LDPC。

1 信号和噪声

用Code rate表示码率，用information bits表示有效信息长度，用channel use表示实际通信中传输的信息长度。Coderate的定义：Code rate=(information bits)/(channel use)。

Code rate可以反映冗余程度。Code rate越高，冗余越小，反之冗余越大。香农揭示了每一种实际的信息传输通道都有一个参数C，如果Coderate<C，那么有效信息传递的错误率可以在理论上趋近于0。但是如何趋近于0，就是纠错编码(error correction code)要做的事情了。

2 通信系统模型

SSD存入和读出信息也是一个通信系统。信息是用户写入的原始数据，经过SSD后端的发送器处理后转化为闪存的指令，信号就是闪存上存储的电荷，电荷存储时会有自身泄漏问题，在读的过程中会受到周围电荷的影响，这是闪存的信道特性，最后数据通过SSD后端的读取接收器完成读取过程。

有两种常见的信道模型——BSC（BinarySymmetric Channel，二进制对称信道）和BEC（Binary ErasureChannel，二进制擦除信道）。BSC出错【接收者收到的是0，但发送者可能发送的是1；同样，收到的是1，但发送者可能发送的是0】；BEC丢位【接收者如果收到0(1)，那么发送者发送的肯定是0(1)；如果传输发生错误，接收者则接收不到信息】。

SSD里的信道模型一般采用BSC，即认为闪存信号存在一定概率的位翻转。为了使信息从源头(source)在经过噪声的信道后能够准确到达目的地，我们要对信息进行编码，通过增加冗余的方式保护信息。信息源发出的信息可用k位的信息x表示，经过编码器(encoder)转化为n位信号c。这个从k位到n位的过程叫编码过程，也是添加冗余的过程。

3 纠错编码的基本思想

3.1 编码距离

一个编码集合里，大家不一定是均匀分布的，有些编码之间距离比较近，有些比较远，编码距离指的是最近的两个编码之间的距离。

解码的时候，一个最暴力的方法就是一一比较接收到的信号和所有有效编码之间的编码距离，选择编码距离最小的。所以编码距离的重要作用是指示编码纠错的位个数。

3.2 线性纠错码的基石——奇偶校验

利用奇偶校验可以构造最简单的校验码——单位校验码(single bit parity check code，SPC)。SPC可以探知任意单位的翻转。对于偶数个位翻转，SPC无法探知，而且校验方程无法知道位翻转的位置，所以无法纠错。

一个自然的想法是，增加SPC的个数，增加冗余的校验信息。同一个位被好几个校验方程保护，当它出现错误时就不会被漏掉。

3.3 校验矩阵H和生成矩阵G

多个校验方程可以表示为校验矩阵H。有了H就可以确定所有正确的码字。对于所有x=(x0,x1,x2,x3,x4,x5…)，只要满足HxT=0，x就是正确的码字。如果不满足，则x不属于正确的码字，认为在传输的过程中x出现了错误。H矩阵里每一行可以表示一个校验方程。行里的1的位置i表示信号中第i位参与校验方程。一般来说，编码长度为n位，有r个线性独立的校验方程，则可以提供k=(n-r)个有效信息位和r个校验位。

4 LDPC原理简介

4.1 LDPC是什么

LDPC全称是Low Density Parity-Check Code，即低密度奇偶校验码。LDPC的特征是低密度，也就是说校验矩阵H里面的1分布比较稀疏。

LDPC又分为正则LDPC(regular LDPC)和非正则LDPC(irregular LDPC)编码。正则LDPC保证校验矩阵每行有固定J个1，每列有固定K个1；非正则LDPC没有上述限制。

4.2 Tanner图

H矩阵可以直观地表示为Tanner图。Tanner图由节点和连线组成。节点有两种，一种叫b节点(bit node)，另一种叫c节点(check node)。Tanner图把编码和图论神奇地结合在了一起。有了Tanner图，LDPC的解码方法就比较好阐述了。

假设信号编码长度为n，其中每一个位用一个b节点表示。校验方程个数为r，每一个校验方程用一个c节点表示。如果某个b节点bi参与了某个c节点cj的校验方程，则用连线把b节点bi和c节点cj连起来。

5 LDPC解码

LDPC的解码方法有硬判决解码(hard decision decode)和软判决解码(soft decision decode)两种。本节将介绍一种经典的硬判决算法——Bit-f lipping算法，以及一种软判决算法——和积信息传播算法。

5.1 Bit-f lipping算法

Bit-f lipping算法的核心思想是：如果信号中有一个位参与的大量校验方程都校验失败，那么这个位有错误的概率很大。

校验矩阵的稀疏性把信号的位尽量随机地分散到多个校验方程中去。Bit-f lipping算法运用消息传递方法，通过不断迭代达到最终的纠错效果。

Bit-f lipping解码算法如下：给定一个n位信号y=(y1，y2，….yn)，校验矩阵H。画出H矩阵对应的Tanner图。n位信号对应n个b节点，r个c节点。
1)每个b节点向自己连接的c节点发送自己是0还是1。初始是第i个位发送初始值yi。
2)每个c节点收到很多b节点的信息，每个c节点代表一个校验方程。

• 如果方程满足，c节点将每个b节点的消息原封不动地发送回去。
• 如果校验失败，c节点将每个b节点发来的消息取反后，发送回去。
  3)每个b节点跟好多c节点相连，b节点收到所有来自c节点的消息后，采用投票法来更新这一轮输出的消息。参加投票的包含每个位的初始值。投票的原则是少数服从多数。
  4)b节点更新好后，停止条件：所有的校验方程满足或者迭代次数超过上限。如果停止条件不满足，则需要转到步骤1继续迭代。

一次更改一个还是一次更改多个，或者两者结合？因为校验矩阵的结构，如果同时改变很多b节点的话，可能无法收敛。这时可以将梯度下降法应用到Bit-f lipping算法中。通过构造目标函数（目标函数包括校验方程最小误差，以及与原信号最大相似）来更新b节点。最终的结论是，每次单个位翻转的收敛性好，但是处理比较慢，翻转多个的话会导致收敛性振荡，但是速度快。一个中间方案是，先进行多个位翻转，等校验方程失败的个数小到一定程度后，再进行单个位翻转。

5.2 和积信息传播算法（略）

从需要求的节点A看，总可以看到因子图是一棵树，而A是根节点，A的边缘分布可以看作消息层层传递的过程。我们的目的是求得每一个边缘概率P(Xi)。最终的P(Xi)=K f(Xi)，K为归一化因子。如果f(Xi=1)<f(Xi=0)，那么输出Xi为0，否则输出1。

最终，经过多次迭代（深度最大为因子图中最大深度树的2倍），得到所有节点的边缘概率P。算法结束。值得讨论的是，前边的算法假定Tanner图是无环的，每一个节点都可以拉出一棵树来。在现实中，这个假定是不成立的，但是该算法也有不错的表现，不过环对纠错的成功与否有着很大的影响。

6 LDPC编码

LDPC是一种以解码为特点的编码，由于LDPC的性质主要由H矩阵决定，一般要先确定H矩阵后，再反推生成矩阵G。H矩阵构建的时候，应当注意：
1)保持稀疏。每行每列里1的个数要固定，或者接近固定。
2)考虑生成矩阵的计算复杂度。
3)保持随机性。减少H矩阵里小环的个数。

下图展示了一个长为4的小环（b节点、c节点和连线组成的环）。显然这两个b节点共同参与了两个相同的校验方程。我们称之为双胞胎。对Bit-f lipping而言，假如它们之间有一个错误，我们将无法对错误进行定位。对和积算法而言，环越长，BP算法效果越好。

7 LDPC纠错码编解码器在SSD中的应用

在SSD主控芯片中实现高性能LDPC纠错码技术需要综合考虑以下几个方面：纠错能力、面积、功耗以及吞吐量。

首先，在纠错能力方面，为了保证SSD的数据可靠性，避免盘内数据丢失和损坏，SSD中不可修复的错误比特率(UBER)和平均故障间隔时间(MTBF)都需要满足极高的要求，比如：要求UBER小于10-17，要求MTBF大于100万小时甚至更高。

LDPC纠错码还有另外一个值得关注的问题：错误平层(Error Floor)的出现。为了保证满足当下数据可靠性的需求，LDPC解码器的错误平层需要码字错误率(CFR)保持在10-11以下。通常降低错误平层的方法可以分为两大类，一类是在构建LDPC校验矩阵时减少陷阱集或者停止集的产生，另一类是在解码算法中对错误平层采用特殊的处理方法。在SSD控制器中，这两种方法通常是结合使用的。

为了支撑SSD高速的数据读写访问，SSD主控中的纠错编解码模块需要提供对应甚至更高的数据吞吐率。为了在满足数据吞吐率要求的同时让设计更具可扩展性，通常在主控中会使用多个ECC核来并行处理数据，然而多核技术的应用会带来额外的系统同步控制复杂度。

LDPC作为一种递归迭代算法，在设计中可以考虑优化迭代收敛算法，即用更少的迭代次数完成解码。在这类思路的指引下，控制器就能在满足性能需求的前提下减少功耗。