《一种适用于NAND闪存的LDPC译码算法》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

一种适用于NAND闪存的LDPC译码算法

范文

摘要：由于NAND闪存具有读写速度快、效率高、功耗低等特点，因此被广泛应用于存储领域。为了提高闪存存储的可靠性，提出一种适用于NAND闪存的LDPC译码算法对其进行纠错。基于LDPC码的BP译码简化算法，结合分层算法与归一化最小和（NMS）算法，提出一种改进的行分层最小和算法。仿真结果表明，改进译码算法在不降低译码性能的前提下，减少了迭代次数，加快了译码收敛速度，更有利于硬件电路的实现。

关键词：NAND闪存;LDPC码;分层算法;最小和算法

DOI：10. 11907/rjdk. 182762 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2019）007-0084-04

LDPC Decoding Algorithm for NAND Flash Memory

YU Bin

（School of Communication Engineering， Hangzhou Dianzi University， Hangzhou 310018， China）

Abstract： NAND flash memory is widely used in the field of storage due to its characteristics of fast read and write speed， high efficiency and low power consumption. A LDPC decoding algorithm for NAND flash memory is proposed in this paper， the aim is to improve the reliability of flash memory storage. An improved line hierarchical minimization algorithm is proposed. Its based on BP decoding algorithm， combined with hierarchical algorithm and normalization minimization algorithm， and BP decoding algorithm based on LDPC code. Simulation results show that the improved decoding algorithm without reducing the decoding performance can reduce the number of iterations， speed up the decoding convergence and is more suitable for the implementation of hardware circuits.

Key Words： NAND flash memory; LDPC code; layered algorithm; min-sum algorithm

作者簡介：于彬（1993-），男，杭州电子科技大学通信工程学院硕士研究生，研究方向为微电子、数据存储。

0 引言

近年来，存储技术得到了飞速发展，闪速存储器[1]（Flash Memory）由于具有非易失性、低能耗、抗震动、存储容量大、寿命长等特性得到了广泛应用。NAND 闪存作为存储介质的固态盘（Solid-State Drive，SSD），具有高性能、低功耗等特点[2]，已逐步应用于军事、航空等多个领域，是存储系统发展的主要趋势之一。然而，随着Flash工艺深入到25nm甚至以下，且内部结构从SLC发展到MLC与TLC，虽然单位存储容量越来越大，但数据差错率也越来越高，需要重点研究如何保障NAND闪存的可靠性[3]。因此，低密度奇偶校验（Low-Density-Parity-Check，LDPC）码开始进入人们视野[4]。LDPC码具有很强的随机纠错能力，以及并行快速译码等特点，但与通信领域的应用特点不同，存储领域需要更高的编码率，且译码收敛速度更快、硬件空间有限，为LDPC码在存储领域的应用带来了很大挑战。因此，寻找适用于NAND闪存的LDPC码具有重要意义[5]。

近年来，研究人员将加权比特翻转（WBF）译码算法应用于闪存纠错领域[6]，但在复杂度降低的情况下，译码性能也损失严重，之后又通过将翻转标志引入WBF译码算法，实现并行加权比特翻转译码[7]，解决了不易正确收敛的问题，但译码性能仍达不到标准。与LDPC比特翻转译码算法相比，采用最小和算法可以提升译码性能，更适用于对闪存的纠错[8]。本文在归一化最小和（NMS）算法基础上[9]，设计一种基于行分层的分层修正最小和算法[10]，在不增加复杂度的前提下，提高了译码收敛速度，并提升了解码器吞吐率。

1 LDPC码基本概念

1.1 基本概念

LDPC码[11]是线性分组码的一种，主要由[（n-k）×n]的校验矩阵H 确定，再根据校验矩阵得到[k×n]的生成矩阵G。其中，k表示信息比特长度，n表示码长。校验矩阵H是低密度奇偶校验码，矩阵中1的数目远小于0的数目，且占比很少。根据每行与每列中1的数目可以将LDPC码种类分为规则和非规则的LDPC码。如果每行与每列中1的数目都为固定整数，则称为规则LDPC码，否则为非规则LDPC码。

LDPC码可以用稀疏校验矩阵表示，也可以用Tanner图[12]表示。例如[（6，2，3）]规则码的校验矩阵H为：

[H=100011010101001110]

其对应的Tanner图如图1所示。

图1 H矩阵Tanner图

Tanner图中存在环，即从某个节点出发再回到该节点构成的闭合路径，所经过边的数目即为环长。其中最短环长称为LDPC码的围长（girth）。短环（如四环和六环）的存在会降低LDPC译码性能，即纠错性能，主要由于环的存在破坏了消息传递的独立性，造成某节点信息被多次重复利用，减缓了译码收敛速度，从而降低了性能，环长越小则性能越差。因此，在构造校验矩阵时，一般围长不能太小[13]。

1.2 LDPC译码算法

LDPC码误码率较低，但译码器复杂，占用面积相对较大。当其应用于NAND闪存时，LDPC码的译码算法应具备较快的译码速度与较低的计算复杂度。

在软判决译码算法中，置信传播（Belief Propagation）算法[14]最为典型，其译码性能相比传统纠错码得到了大幅提高，其结果接近香农极限。在BP算法中，变量节点与校验节点之间传递的信息是个概率的LLR（Log Likelihood Ratio）值[15]。例如：[L（Pi）]表示比特i的信道初始化数据，也即对数似然比，[L（rji）]表示校验节点外的信息数据，[L（qij）]表示变量节点外的信息数据，[L（Qi）]表示变量节点i的后验概率数据[16]。

对数域BP算法译码迭代具体步骤如下：

（1）初始化。计算信道传递给变量节点的初始化概率似然比消息[L（Pi）]，i=1，2，…，n，对于每一个变量节点i及其相邻的校验节点[j∈C（i）]，[C（i）]表示与变量节点i相连的校验节点集合[Ci={j：hji=1}]。设定变量节点传向校验节点的初始消息：

[L（0）（qij）=L（Pi）] （1）

（2）迭代处理。

步骤1：校验节点消息处理。对于所有校验节点j及其相邻的变量节点[i∈R（j）]，[R（j）]表示与校验节点j相连的变量节点集合[Rj=i：hji=1]。第l次迭代时，计算变量节点传向校验节点的消息。

[L（l）（rji）=2tanh-1i′∈Rj＼itanh12L（l-1）（qij）]? （2）

步驟2：变量节点消息处理。对于所有的节点变量i及其相邻的校验节点[j∈C（i）]，第l次迭代时，计算校验节点传向变量节点的消息。

[L（l）（qij）=L（Pi）+j′∈Ci/jL（l）（rji）]? （3）

步骤3：译码判决。对所有变量节点计算硬判决消息。

[L（l）（Qi）=L（Pi）+j∈CiL（l）（rji）]? （4）

若[L（l）（Qi）>0]，则[ci=0]，否则[ci=1]。

（3）迭代停止判断。若[HcT=0]或达到最大迭代次数，则运算结束，否则返回进行下一次迭代。

虽然LLR-BP算法对BP算法作了相当程度的简化处理，但在每次迭代的校验节点更新过程中仍需要进行乘法、指数和对数运算，导致计算量较大，硬件实现过程复杂。最小和（Min-Sum，MS）算法[17]采用求最小值与相加操作替换了LLR-BP算法中非线性双曲函数的反函数计算，降低了BP算法复杂度，减少了计算量，易于进行软件仿真与硬件设计。

LLR-BP算法中对检验节点的处理可表示为：

[L（rji）=2tanh-1i∈Rj/itanh12L（qij）=]

[i∈Rj/isgn（L（qij））？mini∈Rj/iL（qij）]? （5）

然而，最小和算法在简化计算的同时，在性能上也造成了一定损失。因此，提出两种修正最小和算法解决该问题，分别是引入归一化因子的归一化最小和（Normalized MS，NMS）算法，以及引入偏移因子的偏移最小和（Offset MS，OMS）算法[18]。这两种修正算法能够在不显著增加计算复杂度的前提下获得接近BP算法的性能。译码其它过程不变，而是仅对校验节点消息处理的计算公式作了修正，分别如式（6）、式（7）所示。

[L（rji）=α？i∈Rj/isgn（L（qij））？mini∈Rj/iL（qij）] （6）

[L（rji）=i∈Rj/isgn（L（qij））？maxmini∈Rj/iL（qij）-β，0] （7）

式（6）中，[α] 为归一化因子，[0<α<1];式（7）中，[β]为偏移因子，[0<β<0.5]。

2 行分层最小和算法（RLMS）

上文所述算法都是非常经典的LDPC译码算法，但其通常收敛速度较慢，为了获得较高带宽，需要付出很大的硬件代价。因此，为了平衡带宽、性能、面积等方面，本文采用Layer算法[19]。RLMS（Row-Layer Min-Sum）算法即是其中一个典型，其属于串行算法，在相同带宽下硬件代价较小，同时在运算中利用计算出的新LLR代替旧的LLR值，从而获得更快的收敛速度，并且性能上与NMS算法相比几乎没有损失。

LDPC码通过变量节点和校验节点进行消息传递与迭代译码。在上述传统软判决译码算法中，信息传递是以矩阵为整体进行并行传递的[20]。先计算完成所有行的行运算，一起传递到变量节点并更新信息，如图2所示，然后进行列运算，将更新的信息并行地传给变量节点，如图3所示。

图2 变量节点并行传递信息到校验节点

图3 校验节点并行传递信息到变量节点

这种并行传递方法无法及时更新变量节点信息，因而使信息利用时间滞后，导致迭代收敛速度变慢，增加了迭代次数。对于硬件电路模块而言，迭代次数多，也即意味着一次译码所需时间更长，吞吐率下降。

为了达到更高的吞吐量，本文采取行分层的消息传递结构，即每完成一行的行运算，立即变更变量节点信息，并采用新的变量节点信息进行下一行的行运算。

如图4所示，该结构可大大降低信息反馈的滞后，从而增加收敛速度，使平均迭代次数下降20%～50%。采用分层消息传递结构后，对式（3）、（4）、（6）进行修改，分层译码算法如下：

[L（l）（qij）=L（l-1）（Qi）-L（l-1）（rji）]? （8）

[L（l）（rji）=α？i∈Rj/isgn（L（l）（qij））？mini′∈Rj/iL（l）（qij）] （9）

[L（l）（Qi）=L（l）（Pi）+L（l）（rji）] （10）

分层算法的信息计算顺序与传统译码算法有一定差别，首先更新变量节点，然后对校验节点进行更新并计算后验LLR值，之后再判决后验LLR。因为RLMS算法对行结构并未造成影响，只对列结构造成了影响，所以没有影响译码迭代中的校验节点，只需对变量节点进行更新，并对后验LLR值进行修改即可。

[L（Qi）]信息减去[L（rji）]信息即得到更新前的[L（qij）]信息，对[L（qij）]信息进行校验节点更新，得到更新后的[L（rji）]信息，再用更新后的[L（rji）]信息加上更新前的[L（qij）]信息，得到更新后的后验[L（Qi）]信息。

RLMS算法增加了变量节点更新次数，从而提高了译码进程的收敛速度与译码速度。该算法不需要存储变量节点到校验节点的信息，从而节省了存储器空间，更适用于对NAND闪存的纠错[21]。

3 仿真结果与分析

3.1 仿真条件

本文采用PEG随机构造法[22]构造准循环（Quasi-Cyclic，QC）LDPC码，该码的H矩阵结构具有一定规律性，同时还具备优良的纠错性能。该结构可以简化硬件电路实现过程[23]，提高并行速度，并加快译码收敛速度，更适用于对NAND闪存的纠错。

3.2 性能比较

本文构造的校验矩阵为[（256×7）×（256×72）]的矩陣，即为（18432，16640）码，基于Matlab仿真将本文提出的RLMS算法与传统归一化最小和算法的输出误帧率（Frame-Error Rate，FER）进行比较，如图5所示。在具有相同输入信噪比（Signal Noise Ratio，SNR）的情况下，输出的FER远小于归一化因子[α=0.875]的最小和算法，略大于[α=0.75]的最小和算法，在更有利于硬件电路实现的情况下，纠错性能并没有明显下降。

RMLS算法在具备优良译码纠错性能的同时，收敛速度更快，译码平均迭代次数显著减少。在Matlab仿真平台下，对以上3种译码算法进行迭代次数对比，如图6所示。在具有相同输入信噪比的情况下，RLMS算法的平均迭代次数明显减少，也即意味着解码器电路的吞吐率得到了明显提升。

根据以上仿真结果可以得到，RLMS串行算法在不增加译码复杂度且不损失译码性能的条件下，加快了收敛速度，提升了解码器硬件电路吞吐率，更适用于对吞吐率要求较高的NAND闪存中。

图5 不同译码算法下的输出误帧率

图6 不同译码算法下的平均迭代次数

4 结语

综上所述，基于分层算法与最小和算法改进的行分层最小和算法适用于硬件电路的实现，可减少迭代次数，加快译码收敛速度，以提升解码器硬件电路的吞吐率，满足NAND闪存对高吞吐率的要求。未来可对最小和算法的归一化因子进行优化，如加入两个因子进行校正、根据迭代中传输信息值的变化动态规定[α]因子大小等。

参考文献：

[1] 赵啟鹏. 基于NAND闪存的安全U盘FTL算法研究[J]. 软件导刊，2017，16（4）：38-41.

[2] MICHELONI R，MARELLI A，ESHGHI K. Inside solid state drives （SSDs）[M]. Berlin：Springer， 2013.

[3] 周天伟. NAND闪存的软硬判决纠错码应用研究[D]. 西安：西安电子科技大学，2014.

[4] 李芳苑. 用于NAND闪存的LDPC码研究[D]. 广州：华南理工大学，2013.

[5] 彭福来，于治楼，陈乃阔，等. 面向NAND Flash存储的纠错编码技术概述[J]. 计算机与现代化，2017（11）：35-40.

[6] 刘晓健，赵春明，吴晓富.? 改进型并行比特翻转算法[J].? 东南大学学报：英文版，2009，25（4）：423-426.

[7] 刘原华，张美玲. LDPC码的改进迭代比特翻转译码算法[J]. 电讯技术，2012，52（4）：488-491.

[8] 张旋，慕建君，焦晓鹏. 一种MLC闪存存储系统的比特翻转译码算法[J]. 西安电子科技大学学报：自然科学版，2017，44（5）：75-80，146.

[9] FOSSORIER M P C，MIHALJEVIC M，IMAI H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. IEEE Transactions on Communications，1999，47（5）：673-680.

[10] 云飞龙，朱宏鹏，吕晶，等. 一种基于QC-LDPC码的低复杂度分层迭代译码器[J]. 通信技术，2015，48（11）：1228-1233.

[11] GALLAGER R G. Low-density parity-check codes[J]. IRE Transactions on Information Theory，1962， 8（1）： 21-28.

[12] TANNER R M. A recursive approach to low complexity codes[M].? Piscataway：IEEE Press，1981.

[13] 王启玮，战兴群，严凯. LDPC码的编译码设计与研究[J]. 计算机测量与控制，2013，21（3）：728-731.

[14] 詹尹，李宏伟，梁丹亚. 一种LDPC码改进型BP译码算法[J]. 科学技术与工程，2013，13（31）：9366-9370.

[15] 张春生，苏开友，付静. LDPC码在高速移动环境下的编译码实现[J]. 软件导刊，2013，12（2）：46-48.

[16] 姜超. NAND闪存的LDPC码比特翻转译码算法研究[D].? 西安：西安电子科技大学，2017.

[17] 陈正康，张会生，李立欣，等. LDPC 码最小和译码算法的整数量化[J]. 系统工程与电子技术，2015 （10）：2371-2375.

[18] 马汇淼，马林华，张嵩，等. 基于整数运算的LDPC码改进最小和译码算法[J]. 电视技术，2013，37（17）：197-199，235.

[19] 倪俊枫，甘小莺，张海滨，等. 改进的分层修正最小和LDPC译码算法及译码器设计[J]. 系统工程与电子技术，2008，30（12）：2531-2535.

[20] KIM J， CHO J， SUNG W. A high-speed layered min-sum LDPC decoder for error correction of NAND Flash memories[C]. IEEE International Midwest Symposium on Circuits & Systems，2011：1-4.

[21] JUNG Y，CHUNG C， KIM J， et al. 7.7 Gbps encoder design for IEEE 802.11 n/ac QC-LDPC codes[C]. 2012 International SoC Design Conference （ISOCC），2012： 215-218.

[22] HU X Y， ELEFTHERIOU E， ARNOLD D M. Regular and irregular progressive edge-growth tanner graphs[J].? IEEE Transactions on Information Theory， 2005， 51（1）：386-398.

[23] ZIED S A， SAYED A T， GUINDI R. Configurable low complexity decoder architecture for quasi-cyclic LDPC codes[C]. Primosten：International Conference on Software，Telecommunications and Computer Networks， 2013.

（責任编辑：黄健）

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。