LDPC编解码初探

痛定思痛。 2022-06-03 10:09 208阅读 0赞

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

# 为何需要LDPC？ #

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

![4a32000a5ba28a87004b][]

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

![4a35000a5c3bbe245158][]

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

![4a32000a5bb73aabfba1][]

# LDPC编码 #

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

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

![50ec0001227dbd5fded2][]

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

![50ed00012478372ca2c7][]

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

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

![4a32000a5d04ce8280b1][]

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

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

# LDPC解码 #

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

硬解码(Hard Decode):

![4a35000a5f7773a81d69][]

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

举个解码的例子：

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

![4a35000a5fac2ef28dfb][]

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

![4a34000a608fbbc5ce58][]

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

![4a35000a5fe624bfcb42][]

软解码(Soft Decode):

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

![4a36000798d90c101bdf][]

# 结语 #

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

精彩推荐:

*  [浅析PCI配置空间][PCI]  
    
 *  [步入新时代 | PCIe 4.0带来了哪些惊喜？][_ PCIe 4.0]
 *  [PCIe SSD飞入寻常百姓家靠什么？][PCIe SSD]  
    
 *  [SCM+MLC/TLC NAND混合SSD性能探究][SCM_MLC_TLC NAND_SSD]  
    
 *  [浅析企业级SSD Multi-Stream Write技术][SSD Multi-Stream Write]  
    
 *  [企业级SSD发展趋势][SSD]  
    
 *  [2D NAND和3D NAND横向对比][2D NAND_3D NAND]  
    
 *  [第二代3D TLC NAND原厂级深度评测][3D TLC NAND]
 *  [为QLC保驾护航 | 慧荣科技亮出最新LDPC技术][QLC_ _ _LDPC]
 *  [SSD固态硬盘接口种类多，你了解多少？][SSD 1]  
    
 *  [写放大机制与影响因素详解][Link 1]
 *  [详解SSD之垃圾回收GC][SSD_GC]
 *  [SSD为什么需要Trim？][SSD_Trim]  
    
 *  [OP详解: 谁“偷”走了SSD的容量？][OP_ _SSD]
 *  [SSD性能优化之4K对齐][SSD_4K]
 *  [文件系统全记录回顾][Link 2]  
    
 *  [快来看，SATA秘籍惊现江湖！！！][SATA]
 *  [PCIe最全科普贴流出！不说了，赶快Mark！][PCIe_Mark]
 *  [独家发布 | Linux NVMe Driver学习笔记大合集][_ Linux NVMe Driver]  
    
 *  [存储随笔《NVMe专题》大合集及PDF版正式发布！][NVMe_PDF]

更多精彩内容，敬请关注头条号【存储随笔】获取更多活动内容。

# 同时，也可以关注[微][Link 3]信公众号: 存储随笔，Memory-logger.  #

![SouthEast][]

[4a32000a5ba28a87004b]: http://p3.pstatp.com/large/4a32000a5ba28a87004b
[4a35000a5c3bbe245158]: /images/20220603/da9196360eb043be9ff525718c01f72c.png
[4a32000a5bb73aabfba1]: /images/20220603/44c7f7ed591948a3aa277accba71ece9.png
[50ec0001227dbd5fded2]: /images/20220603/6cc6710133734d5997702093cf14f0f5.png
[50ed00012478372ca2c7]: /images/20220603/94153e85293946929c5970613de18e6d.png
[4a32000a5d04ce8280b1]: http://p3.pstatp.com/large/4a32000a5d04ce8280b1
[4a35000a5f7773a81d69]: http://p9.pstatp.com/large/4a35000a5f7773a81d69
[4a35000a5fac2ef28dfb]: /images/20220603/a8b28552fa254be6ba9926b28249a849.png
[4a34000a608fbbc5ce58]: http://p9.pstatp.com/large/4a34000a608fbbc5ce58
[4a35000a5fe624bfcb42]: /images/20220603/fab627f42f9847f0a51c6bbb35c05b53.png
[4a36000798d90c101bdf]: http://p3.pstatp.com/large/4a36000798d90c101bdf
[PCI]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484877&idx=1&sn=da7ee4d0920540af845ca6c610b33c86&chksm=972ef494a0597d820d29a9ab072e8583202c629d34e8f255b1eb10de3c1d73d6eee1417eddf9&scene=21#wechat_redirect
[_ PCIe 4.0]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484818&idx=1&sn=9a70c7831effea2df5076b4770f2f0d9&chksm=972ef4cba0597dddcd2c79811880759190a7fde5adcbd96184e5970b6e32a406425e794c4ea4&scene=21#wechat_redirect
[PCIe SSD]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484750&idx=1&sn=9907280aa354260b49a1fc69a12cad7d&chksm=972ef417a0597d01b75a85af61175f04e1ed5c693684daec19ffc1e1a831b1e59a417d1a1b1a&scene=21#wechat_redirect
[SCM_MLC_TLC NAND_SSD]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484629&idx=1&sn=71b5a506c12c6504b240e4185c8c33af&chksm=972ef58ca0597c9a40e792755bfb382a399f68e7589de7780a875b9f9e562bdcc468bba99ec7&scene=21#wechat_redirect
[SSD Multi-Stream Write]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484600&idx=1&sn=d4f6b65efbfd5d3ef43ad98aa39a634f&chksm=972ef5e1a0597cf75b4cb2f41829005ad72a549958c22ce39355d3b8e00a42131ff7a8521e59&scene=21#wechat_redirect
[SSD]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484599&idx=1&sn=4c9fd79dba8cf2b9f6c3a29f26056be6&chksm=972ef5eea0597cf8319a5717e4d79a2cf6dbc5ba727b2a19c66a50b95112d073b79112939e63&scene=21#wechat_redirect
[2D NAND_3D NAND]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484482&idx=1&sn=58eec127e48d766f5d728c8eeca18d8d&chksm=972ef51ba0597c0d1677174c5118ac37e30cc2ccee51b3eebe349df1d8ee89c5f401aa312283&scene=21#wechat_redirect
[3D TLC NAND]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484556&idx=1&sn=91cffd77a58e8089e615a573b52b7aac&chksm=972ef5d5a0597cc3377eba5b7a32b4e4e50c18ad844d22de2a1a3ec758e39229fa50e84cae53&scene=21#wechat_redirect
[QLC_ _ _LDPC]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484571&idx=1&sn=3ed15cf84b0e8105b481d0d704de93d5&chksm=972ef5c2a0597cd4629124a88debdd1d932c1844483cf14050a1f4b65d344f2cd4ed17b666e9&scene=21#wechat_redirect
[SSD 1]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247483733&idx=1&sn=422dd9187ac79c43b6dd3627bae5b0ba&chksm=972ef00ca059791a30e7c6bd44e4a670e69f3f2a50b3bc8e320a6aec460deb60df570695d1b7&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484525&idx=1&sn=00c313d29064a9458116fabc6d002b77&chksm=972ef534a0597c2264df88d3fd8c15d3ccbe33294f4f512be870b30f5cd02115ae5ac5dfe02f&scene=21#wechat_redirect
[SSD_GC]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247483752&idx=1&sn=a7a7209337cc5ef3d3ebefda2591bda0&chksm=972ef031a0597927f5af5c437354a933c04f224cf9f1a0a6f1939db45e7c3d58219442b2f0a4&scene=21#wechat_redirect
[SSD_Trim]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247483713&idx=1&sn=46cd747745744b91aa72c9a36498c0b9&scene=21#wechat_redirect
[OP_ _SSD]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247483683&idx=1&sn=d3cb7b4a444ca5ada9d518c57f07c534&scene=21#wechat_redirect
[SSD_4K]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247483732&idx=1&sn=e8f666496e12cdac227db7f8a399b09b&chksm=972ef00da059791bd7edf9d195e5d68f810602a3a681202575f9dc11e803ed30342b6f83194d&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484486&idx=1&sn=f1917921241cafd83cf9ec3198dfaa2d&chksm=972ef51fa0597c097fdc9f522ecbd57a687bf4a6aa828ccb37d959a8138ed9e893d199580ef0&scene=21#wechat_redirect
[SATA]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484134&idx=1&sn=7764b6f8f9b51c0f79108baa03d65735&chksm=972ef3bfa0597aa99a56b08c316bfed5428e31c965926eec1fe51587d0a76528ae37f3d03ad3&scene=21#wechat_redirect
[PCIe_Mark]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484347&idx=1&sn=b2b1a1c818bf842ee361f09a630271eb&chksm=972ef2e2a0597bf433112814add8fdb44e3cb60bdf75f6fa58683fbc1fbd3f8b3be639962bd3&scene=21#wechat_redirect
[_ Linux NVMe Driver]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484503&idx=1&sn=b11975186d4e647069d5341a4af705a7&chksm=972ef50ea0597c189cc458b60f6670c64968515537537dcada98359f64b3fa326c29ead8f330&scene=21#wechat_redirect
[NVMe_PDF]: http://mp.weixin.qq.com/s?__biz=MzIwNTUxNDgwNg==&mid=2247484399&idx=1&sn=9a7612489ba72d94e17304c7476d271f&chksm=972ef2b6a0597ba07c4dd45996602b9d891cc195478e3643b6bd32ff57c0b3f1c2f7ee98b69c&scene=21#wechat_redirect
[Link 3]: http://lib.csdn.net/base/wechat
[SouthEast]: /images/20220603/dab68fc2d2ed492a8294d6e2ceb070ca.png