腾讯云网站解决方案帮您轻松应对建站成本高/网络不稳等常见问题

搜搜吧

查看: 56|回复: 0

[资讯] 固态硬盘纠错算法的前世今生

[复制链接]
  • TA的每日心情
    奋斗
    昨天 11:35
  • 签到天数: 70 天

    [LV.6]常住居民II

    超级VIP贵宾会员

    1892

    主题

    1965

    帖子

    6639

    积分

    Rank: 1

    UID
    21335
    威望
    -100
    贡献
    2337
    在线时间
    51 小时
    注册时间
    2018-12-6
    发表于 2019-1-10 13:51:55 | 显示全部楼层 |阅读模式
    推广者专属福利,新客户无门槛领取总价值高达2775元代金券,每种代金券限量500张,先到先得。

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

    9eddacff0f02dae08c715a27db06f680.jpg-wh_651x-s_2149031913.jpg

    在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编码应用的一个难点。

    8d208b2597b46051adafa765bea247a3.jpg

    LDPC校验矩阵H

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

    185c1fa61bc8eba3f8bc269507f88a53.jpg

    校验矩阵H对应的Tanner

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

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

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

    5bcc0c4d13038cdc51b289c258f11076.jpg

    c58ecef40486579bb73753980ebe881a.jpg

    f012f993461704c16339981d6fff26e7.jpg

    d6f3bd1b8bc73f8f25405dfdedc335d6.jpg

    2a3ae3a06848dcc16516cc0ba1dc23ff.jpg

    427ef75140bc0a03fd1e6627550a537b.jpg-wh_600x-s_2837375479.jpg

    45d1d7e8033caf1dd21dbd0f20265162.jpg-wh_600x-s_1173972271.jpg

    bd60d01d1749a41b3836332acce35ab9.jpg-wh_600x-s_4167181416.jpg


    822b6ecc254f8f10c0cd63a963882f2d.jpg-wh_600x-s_2173113215.jpg


    f5214be7accef8751a29af5cff068cae.jpg-wh_600x-s_3993899551.jpg

    df178a8361e70f6b2ee3ca94f3b05ba1.jpg-wh_600x-s_3740797631.jpg



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

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

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

    6e02c9517e743a3c397cb7cecc6d0624.jpg

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

    46f4a93ccc767f3db5b3bcf2d27bfb4e.jpg-wh_600x-s_1714635123.jpg

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

    cad5e69171c267fea2adbb668f530a32.jpg-wh_600x-s_1402399651.jpg

    总结:

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


    楼主热帖排行榜
    搜搜吧社区温馨提示:
    搜搜吧(www.sosoba.org)十分重视网络版权及其他知识产权的保护,针对网络侵权采取如下版权政策:
    1、本站有理由相信网友侵犯任何人的版权或作品,(图文,文字,下载,视频,非法传播),本站有权不事先通知即删除涉嫌侵权的作品和内容
    2、本站将采取必要的网络技术手段,确认为侵权作品或内容的用户有权进行警告、屏蔽、删除的行为,尽可能的防止侵权行为的发生
    3、搜搜吧影视资源均收集自互联网,没有提供影片资源存储,也未参与录制上传,若本站收录的资源涉及您的版权或知识产权或其他利益,我们会立即删除
    4、搜搜吧,删帖,投诉,举报,侵权,若本站侵犯您的权益,附上身份及权利证明,请直接发送邮件到 kefu-sosoba@qq.com 我们将在一个工作日内删除
    soso搜搜吧社区是聚合百度搜索,搜狗搜索,360搜索,新闻,教育,站长,广告,娱乐,影视,微信,网盘,营销,手机,汽车,游戏,论坛综合为一体的大型门户社区www.sosoba.org
    关闭

    搜搜吧社区公告上一条 /1 下一条

    Powered by www.sosoba.org X3.4© 2013-2019 搜搜吧社区 小黑屋|手机版|地图|关于我们|腾讯云代金券|soso吧社区
    广告服务/项目合作: kefu-sosoba@qq.com  侵权举报邮箱: kefu-sosoba@qq.com  搜搜吧建站时间:创建于2013年07月23日
    免责声明:本站所有的内容均来自互联网以及第三方作者自由发布,版权归原作者版权所有,搜搜吧不承担任何的法律责任,若有侵权请来信告知,我们立即删除!
    推荐使用:chrmoe谷歌浏览器,搜狗浏览器,QQ浏览器,360极速浏览器,360安全浏览器,猎豹浏览器,火狐浏览器,世界之窗,百度浏览器,Safari浏览器,ios,Android

    GMT+8, 2019-7-19 05:20 , Processed in 1.140625 second(s), 15 queries , Gzip On, MemCache On.

    快速回复 返回顶部 返回列表