LDPC编解码初探

目前SSD中ECC纠错代码主要两种BCH和LDPC。不过，随着SSD对ECC纠错技术要求越来越高，BCH纠错码开始有些吃力，所以，LDPC纠错码是发展趋势，也是最新最主流的纠错码。

为何需要LDPC？

我们先回顾一下NAND闪存的基础知识。在这里以MLC NAND为例。在MLC NAND中，有四个Vt level. 如下图，

随着P/E cycles的增加，MLC NAND的vt电压分布就会变大变宽，如下图，

当P/E cycle到了一定的数值之后，MLC NAND不同vt level之间就会有交叉，这样的话，就会引起数据读取错误，这时，就需要请出LDPC纠错码了。

LDPC编码

LDPC，是Low Density Parity Check Code的简称，翻译为中文就是“低密度奇偶校验码”。在1963年，LDPC第一次出现在R.G.Gallager博士发表的论文之中。LDPC码是一种稀疏校验矩阵线性分组码。为何称为“稀疏”呢？因为校验矩阵中的1要远小于0的数目，这样做的好处就是，译码复杂度低，结构非常灵活。

在LDPC编码中，会用到一个叫做H矩阵的校验矩阵(Parity Check Matrix)，比如，我们来看一个交单的H矩阵：

为了可以更加直观的理解H矩阵，可以借助Tanner图，来表示H矩阵：

左侧V1~V7是变量节点，右侧C1~C3是校验节点。变量节点和校验节点之间的连接线称为沿(edge)，也代表这H矩阵中的1. 每个节点上连接线(edge)的数目称为节点维度(Degree).

LDPC编码分为正则编码和非正则编码。正则编码中，横向和纵向中1的个数是固定的。非正则编码中，横向和纵向中1的个数不固定。举一个例子，正则LDPC编码矩阵：

在这个正则H矩阵中，横向维度Dr=4, 纵向维度Dc=3. Codeword长度=20.

与校验H矩阵对偶的矩阵，称为G矩阵，也是生成矩阵。构建优异的H校验矩阵，是不同SSD主控商实现LDPC的核心内容，每家都有各自的专利。

LDPC解码

在SSD内部的LDPC解码过程中，主要包括了两方面内容：硬解码(Hard Decode)和软解码(Soft Decode). LDPC解码的方法就是收到码字之后，与校验矩阵H相乘，如果是0矩阵，则说明收到的是正确码字。反之，则不正确码字，再根据相乘结果进行进一步纠错解码。

硬解码(Hard Decode):

信息传递(Messag passing)是LDPC硬解码常用的方法。校验节点和可变节点之间传递信息，进行迭代，直至所有的奇偶校验归0，则解码成功。

举个解码的例子：

迭代1：第一次信息传递迭代之后，Hard decode解码，此时n0,n4,n6仍为1.

迭代2：第二次信息传递迭代之后，Hard decode解码，此时n0仍为1.

迭代3：第二次信息传递迭代之后，Hard decode解码，奇偶校验归0.

软解码(Soft Decode):

软解码的原理是调整不同read level，根据读取结果后，判断bit是1或者0的概率，然后根据1或者0概率实现软解码, 如下图。

结语

本文我们简单的阐述了为何需要LDPC，LDPC编解码的基本原理。小编在此抛砖引玉，欢迎各位看官拍砖讨论。