MLC存储信道下的双层LDPC码优化设计

侯文涛，张顺外，孔令军

(1.南京邮电大学 通信与信息工程学院，江苏 南京 210003;2.金陵科技学院 网络与通信工程学院，江苏 南京 211169)

0 引言

近年来，大数据和云存储的发展给信息领域带来了诸多风险和挑战，传统的存储技术不能适应当前高集成度、低功耗快速集成电路技术的发展。非易失存储(Non-Volatile Memeory,NVM)技术尤其NAND存储技术具有高读写速度、高集成度和体积小等优点，成为当前研究的热点[1]。

多层式存储(Multi-level Cell，MLC)高密度技术凭借存储容量大、单位存储成本低及功耗小等特点受到广泛的关注。然而，随着存储密度的增大和单元尺寸的减小，导致MLC型NAND闪存的可靠性降低。简单来说，一个闪存单元的重复编程次数是有限的，如果超过某个特定次数，闪存单元就不能执行写入操作。未来将会不断地缩小闪存单元的尺寸，也会加入更多的信息比特到每个存储单元中，因此有效的P/E循环次数会不断地降低，同时在存储数据进行读取判决时更容易出现错误。因此，解决读写时延加长、P/E次数减少等主要问题以及实现数据的可靠性存储正成为现阶段存储领域研究的重点[2]。

当闪存单元的擦除次数达到一定阈值后，其存储数据的性能急剧下降，此时纠错功能显得尤为重要。传统的纠错码受限于其纠错能力，无法满足MLC型NAND闪存中数据可靠性存储的要求。本文结合MLC存储信道的特性，设计了一种适用于MLC闪存中双层低密度奇偶校验(Low-Density Parity-Check，LDPC)码的编译码算法，提升MLC存储使用期内不同阶段的系统性能，实现延迟控制，提高系统的存储效率。仿真结果表明，所提出的方法相比于常规的纠错算法有更好的性能，降低了译码算法的复杂度。

1 相关工作

1.1 存储信道下的纠错码

信道编码可有效地改善存储可靠性、延长其使用寿命[3]。博斯—乔赫里—霍克文黑姆(Bose-Chaudhuri-Hocquenghem,BCH)码,因为编译码算法复杂度较低、纠错能力良好，在可靠性存储中得到了很好的应用[4-6]。为了进一步提升BCH码的性能，一些学者也提出了通过级联的方法[7]和平面优化算法[8]来降低复杂度，都取得了很好的性能提升。然而，随着TLC等高阶存储器的出现，传统的纠错码受限于其纠错性能及高复杂度，无法进一步满足数据可靠性存储的要求。因此，容量限可达的极化码(Polar codes)以及逼近香农限的LDPC 码凭借更强的纠错性能在MLC型NAND闪存中的应用引起了广泛的关注[9-15]。

LDPC码是一种基于稀疏校验矩阵的线性分组码，由Gallager于1962年首次发现。其校验矩阵中的1远小于 0的数目，其译码复杂度和最小码距都只随码长呈现线性增加，且相同码率下，LDPC码的纠错性能优于BCH码[16]，使得LDPC码在MLC型NAND闪存中的应用成为当前研究的热点。文献[11-12]针对LDPC的实现工作致力于减少由细粒度内存感知精度引起的延迟开销，为了解决潜在的BP解码的延迟，Aslam等[13-15]提出了几种改进的BP算法，降低了复杂度和收敛性能。

与通信领域不同，面向Flash存储的基于信道编码理论，借助差错控制技术可以保证存储系统的数据可靠性。LDPC码不仅要求在保证高编码率的同时达到低误码率，还要求编译码尽可能简单以能够在VLSI中实现。QC-LDPC作为一种结构化的LDPC码，由于其生成矩阵的循环性，硬件实现简单，成为存储领域中比较受欢迎的一种LDPC码。文献[17]通过减少奇偶校验矩阵中权重为2的列的数量和优化代码图的结构，提升了纠错性能。文献[18]构建了一种基本矩阵，是根据NAND闪存改进的外部信息传输(EXIT)图方法优化的度序列的QC-LDPC码，具有低复杂度的QC编码器结构和易于并行化的原型图解码器结构，可以方便地生成速率兼容的原型LDPC码族。

1.2 双层LDPC码

双层LDPC码最早在DF中继通信系统中提出[18]。Peyman提出了2类双层LDPC码：双层删减码和双层加长码，分别用于源节点向目的节点的信道以及中继节点向目的节点的信道中使用。源节点向目的节点传输信息，利用中继节点辅助源节点向目的端传输额外的校验位，在目的端译码时借助2组校验位进行译码，该方法能够提高系统的整体性能。将存储系统与中继系统进行类比。由于单元间干扰对MLC不同页之间的影响不同，导致其同一单元不同页受到的噪声影响也不同。因此，可以将上页和下页分别等效为中继通信系统的源节点与中继节点。在下页中加入额外校验位对上页译码进行辅助，使噪声干扰较强的上页获得更好的译码性能。

2 主要任务

2.1 MLC闪存信道模型

NAND闪存的基本数据存储单元是浮置栅单元，简称为存储单元(Cell)。通过对浮置栅单元进行充电，使其电压值达到不同的阈值范围以表示不同的数据来进行数据存储。对MLC闪存中2 bit/Cell的单元，阈值电压被分成4个电压区间，电压层级分别为1，2，3，4，每个电压层级对应的数据分别用11，10，00，01表示。每个存储单元中存放的数据由2个比特联合组成，分别为最高有效比特(Most Significant Bit,MSB)和最低有效比特(Least Significant Bit,LSB)。闪存以块(Block)为最小单位执行擦除操作，而读写操作的最小单位为页(Page)。MSB构成闪存存储的下页(Lower Page,LP)，上页(Upper Page,UP)则由相应的LSB组成。MLC型NAND闪存的电压层级如图1所示。

图1 MLC型NAND闪存的电压层级Fig.1 Voltage level of MLC NAND flash

由于各种电路级噪声的影响，所期望的阈值电压信号受到严重干扰，带来严重的数据可靠性问题。本文将编程噪声、随机电报噪声(RTN)、数据驻留噪声和小区间干扰作为主要的信号退化成分，对MLC闪存信道进行建模，如图2所示。

图2 闪存信道模型Fig.2 Flash memory channel model

其阈值电压表示为：

V=VP+{nu+np+I+nRTN+nret} ，

(1)

式中，VP∈{Vs11,Vs10,Vs00,Vs01}为目标电压水平集合；Vs11为擦除状态电压；Vs10，Vs00，Vs01表示编程状态的3个电压；nu，np分别为理想编程操作后出现的与状态相关的编程噪声分量，其中与状态相关的ISPP噪声nu只对编程化的状态存储单元产生影响，在迭代编程与验证方法下，通过一系列程序和验证电压脉冲，将每个编程状态配置为各自的验证电压级别VP，这些电压脉冲被应用于电池的控制门。采用这种编程方式，程控状态存储单元对应的阈值电压信号在[0,Vpp]趋向于均匀分布[16]：

(2)

式中，Vpp表示采用ISPP技术对每一次编程操作阈值电压的增加值。

编程噪声同时影响擦除状态和编程状态的单元，主要由NAND闪存制造工艺变化造成，可以用高斯分布函数[17]来表示:

(3)

式中，σp，σe为噪声方差参数。

I表示单元间干扰，由相邻存储单元间的寄生耦合电容的存在而产生，由CCI导致的电压改变量VCCI可以表示为[18]：

(4)

nRTN表示随机电报噪声，由于反复出现的P/E循环产生了陷阱，这些陷阱位点捕获带点粒子产生了阈值电压的波动，这种无意识的电压信号波动增加了NAND闪存通道的噪声方差。这种电路级阈值电压失真称为随机电报噪声(RTN)。本文用零均值高斯分布函数对RTN进行建模：

(5)

式中，σw随PE周期变化。

nret表示数据驻留噪声随时间的变化，由存储单元中数据的变化而导致。数据驻留错误与P/E和存储数据的停留时间有关，其阈值电压分布函数如下：

(6)

式中，方差σrs和均值urs如下：

urs=(VP-x0)×[At(PE)αi×Bt(PE)αo]×ln (1+T)，

(7)

σrs=0.3|urs|，

(8)

式中，At，Bt，αi，αo，x0为常数分布参数。

2.2 双层LDPC码的设计

面向Flash存储的LDPC码不仅要求在保证高编码率的同时达到低误码率，还要求编译码尽可能简单以能够在VLSI中实现。本文采用QC-LDPC码作为MLC型NAND闪存信道的信道编码方案。为保证双层LDPC码的译码性能，在设计时要求校验矩阵中无短环的存在。双层LDPC码的Tanner图如图3所示。

图3 双层LDPC码的Tanner图Fig.3 Tanner graph of Bilayer LDPC code

图3所示的双层LDPC的Tanner图可以用(Uα∪Lβ∪Vv)来表示，其中，Uα={u1,u2,…,uk1},是上层子图的校验节点,Lβ={l1,l2,…,lk2}是下层子图的校验节点，Vv={v1,v2,…,vN}是变量节点。虚线表示为双层LDPC码的短环，构造双层LDPC码，要确保双层LDPC码的Htwo无短环、无停止距离，使Hup|K2*N,Hlow|K1*(N-K2)也满足无短环。

给定一个QC-LDPC码的移位索引矩阵:

(9)

式中，Ps,t=asbt∈GF(p),0≤s≤j-1,0≤t≤k-1,a≠b∈{2,3…p-1}。参数a,b,p,j,k确定后，一个QC-LDPC码的校验矩阵就可以生成，根据如下判决公式，可得到无短环的充要条件[19]：

(10)

式中，1≤s≤j-2,2≤s′≤j-1,1≤t≤k-2,2≤t′≤j-1,s

2.3 双层LDPC码的编、译码

双层LDPC码的编码需借助上层矩阵Hup及下层矩阵Hlow分别获取校验比特K1及额外校验比特K2。式(11)中，Htwo为双层LDPC码的校验矩阵，Hup和Hlow分别为上层矩阵和下层矩阵，N为双层LDPC码的码长，K1和K2分别表示上层LDPC码和下层LDPC码的校验比特长度，X为双层LDPC码的码字：

(11)

式中，Hzero|K1*K2为全0矩阵，用于匹配双层LDPC长度。

(12)

(13)

由式(12)可得：

(14)

(15)

下层LDPC码的额外比特K2为：

[x1,x2,…,x(N-K1-K2),c1,c2,…,cK1]T。

(16)

针对MLC信道的特性，需对MLC闪存的上下2页数据分别进行编码，具体步骤如下：

① MLC上页数据编码。使用双层LDPC校验矩阵Htwo的上层矩阵Hup对上页数据bitup进行编码，得上页校验比特K1。

② MLC上页数据额外校验比特编码。使用双层LDPC校验矩阵Htwo的下层矩阵Hlow对上页数据bitup+上页校验比特K1进行编码，得到上页额外校验比特K2，存放至MLC下页。

③ MLC下页数据编码。为保证MLC上下页码长相同，需对下页数据进行编码，得到下页数据的校验比特K3,其长度为|K1-K2|。

④ 对MLC的上、下页数据进行MLC闪存编码，得到对应电压阈值。

编码过程及各部分长度如图4所示。

经过MLC闪存信道后，其译码过程由两部分组成：阈值电压向码字的映射及码字的译码，具体如下。

① 对MLC信道电压进行门限电压的感测，根据电压值判定上下页数据的似然比。初次判定时采用低精度电压感测，以降低读取系统的延迟。

② 对MLC下页进行译码，得到MLC下页数据及额外校验比特K2的译码值。若译码失败，感测精度后再次译码，直到预定精度或译码成功。若成功，存储额外校验比特K2信息。

③ 用上层校验矩阵Hup对MLC上页数据进行译码。若译码成功则输出结果，否则读取存储的额外校验比特K2。

④ 对读取额外校验比特K2的MLC上页数据进行双层LDPC码译码，若失败则提高感测精度直到预定精度，否则译码成功。

图4 MLC信道双层LDPC编码流程Fig.4 Bilayer LDPC encoding process in MLC channel

需要注意的是，以上是在单独的MLC上页译码失败后才进行双层LDPC码的使用，因此系统的复杂度并不会因为引入额外校验比特后而急剧上升，其具体流程如图5所示。

图5 MLC信道双层LDPC译码流程Fig.5 Bilayer LDPC decoding process in MLC channel

3 算法仿真

3.1 仿真参数及矩阵设计

本文对提出的MLC信道下双层QC-LDPC码优化算法进行数值仿真，以验证方法的有效性。重点评估加入额外校验比特位的上页传输性能。在解码过程中，共同使用来自MLC上页的码字信息和下页中正确译出的额外校验比特位。需要特别注意的是，仿真认为上页译码时能够完全正确地从下页中获取额外校验比特。

选取的LDPC码的码长N=2 808,码率R1=3/4，R2=5/6。采用BP译码算法，设置最大迭代次数为25和50，具体参数如表1所示。

表1 仿真参数

根据式(10)，a=3，b=11，p=234，经验证，符合无短环条件。

(17)

(18)

式中，

(19)

(20)

(21)

(22)

最终译码双层LDPC矩阵形式如下：

(23)

3.2 性能分析

图6和图7分别为不同迭代次数下码率R为3/4，5/6的MLC闪存上层信息的误码率和误帧率性能比较。可以看出，擦除次数P/E较低时，同一码率的情况下采用本文算法的双层QC-LDPC相较于传统的单层QC-LDPC码，误码率与误帧率得到显著提高。在10-5的误码率时，能够获得约额外4 000次的擦除周期，大大提高了MLC闪存的使用寿命。然而，随着P/E擦除次数的增多，信道内干扰加强，本算法与单层LDPC码算法性能相近。

(a) MLC闪存上层误码率(N=2 808,iter=25)

(a) MLC闪存上层误帧率(N=2 808,iter=25)

为了比较本算法设计的双层LDPC码对BP译码算法延迟复杂度的影响，图8和图9分别提供了码率R=5/6时最大迭代次数为25次和50次时的性能对比和平均迭代次数曲线。

图8 不同迭代次数下MLC闪存上层误码率 (N=2 808,R=5/6)Fig.8 BER of upper layer of MLC flash with different iterations (N=2 808,R=5/6)

图9 MLC闪存上层平均迭代次数 (N=2 808,R=5/6)Fig.9 Average iteration numbers of upper layer of MLC flash (N=2 808,R=5/6)

由图8和图9可以看出，在擦除次数较低时，相同的最大迭代次数下，本文所提出的双层LDPC码相比于单层LDPC码，平均迭代次数显著降低，大大降低了译码的复杂度和延时。此外，提高最大迭代次数，双层LDPC码的性能提升优于单层LDPC码，且平均迭代次数的增加较少。综上所述，本文提出的算法在复杂度和性能上都优于常规的单层LDPC码。

4 结束语

本文提出了一种基于双层LDPC的MLC信道下的编码方案，通过添加额外校验比特的方式提高MLC闪存的译码性能和降低译码复杂度，并通过合理地设计QC-LDPC码的校验矩阵，在避免短环的前提下，获得具有更大的最小距离的QC-LDPC矩阵。仿真结果表明，所提出的算法与单层LDPC码相比，在误码率为10-5时，能够获得约额外4 000次擦除周期的提升。此外，本算法要求额外校验比特能够完全正确译出，在实现上存在一定困难。下一步将寻找合适的下页译码算法来保证获取到额外校验比特的正确性以及高码率下无短环的校验矩阵的参数。