MLC型NAND闪存中基于MI异构的Polar码优化

张司琪， 孔令军， 张顺外， 张 南

1.南京邮电大学通信与信息工程学院，南京210003

2.中国航天系统科学与工程研究院工程科技发展战略研究所，北京100048

近年来，固态硬盘以其读写速度快、轻便等优点在NAND Flash 中应用广泛，同时也为大数据开辟了新的发展之路[1].多级单元（multi-level-cell, MLC）型NAND Flash 技术的出现一方面增大了存储密度，单位比特的成本降低；另一方面闪存封装尺寸的减小也缩短了存储单元间的距离，单元间干扰（cell-to-cell interference，CCI）的影响会降低闪存存储系统的可靠性.而传统的纠错码——BCH 码无法满足MLC 型闪存的差错控制需求，因此利用新型纠错码改善高密度存储系统中数据的耐久度与可靠性成为现阶段闪存研究的重点之一[2].

Polar 码由Arikan 于2009 年提出，是目前唯一一种能被严格证明在编译码复杂度较低的情况下达到香农极限的线性分组码[3]，因其具有容量限可达、构造方式明确等优点而成为最优信道编码方案的候选之一，为MLC 型NAND 闪存的差错控制技术开辟了一个新的方向.然而，关于MLC 型NAND 闪存信道的polar 码构造优化的研究不多[4-5].文献[4]提出了一种称为自校验的高效多策略ECC 方案，其中硬解码器设计用于校正MLC 闪存初始阶段的大多数错误码字，而软解码器旨在纠正包含大量错误的码字.文献[5]将polar 码应用于MLC型NAND 闪存信道的多策略预编码方案，并比较polar 码的二进制输入硬判决译码、量化软判决译码和软判决译码三种译码算法的性能，然后提出了一种利用逐步最大互信息量来获取量化边界值的方案.文献[6]提出了一种基于多级存储阈值电压的polar 设计方法，并与传统的polar 码构造方法进行了比较.本文在对MLC 型NAND 闪存信道特性的深入分析基础上，利用MLC 型NAND 闪存信道和AWGN（additive white Gausian noise）信道的差异性，将LLR 转换成互信息量（mutual information, MI），获取闪存信道下等效的方差，然后基于先前的巴氏参数法构造polar.同时在一定的码长和码率下，分析了polar 码的不同构造法对MLC型NAND 闪存信道的误码性能.

1 MLC 型NAND 闪存信道模型

一个NAND 闪存芯片由多个块构成，每个块有多个页，每页包含若干个存储单元.NAND 闪存中的存储单元可表现出擦除态或编程态，其阈值电压被分成多个量化级来表示数据.MLC 型闪存采用格雷映射表示存储单元的4 个状态，MLC 型存储单元中4 个不同的阈值电压Vmin、V1、V2、Vmax分别表示数据符号“11”“10”“00”“01”,Vmin和Vmax分别为处于擦除状态和最高写入电压对应的编程状态的存储单元阈值电压平均值.MLC 型存储单元中用bi（i ∈{0,1}）表示第i个比特，b0为最低有效位（least significant bit, LSB），b1为最高有效位（most significant bit, MSB）.

将基于编程干扰（programming noise, PN）、单元间干扰以及数据驻留噪声（data retention noise, DRN）对MLC 型NAND 闪存信道进行建模[7-9].在理想状况下，经过擦除和编程操作之后得到MLC 型闪存单元阈值电压分布的统计如图1(a)所示.

1.1 MLC 阈值电压模型

在多级存储单元中，擦除态存储单元的阈值电压分布P11(v)可以拟合成高斯分布，有

式中，Vmin和σe分别为存储单元阈值电压的平均值和标准方差，v为已知阈值电压.闪存存储不同的数据是通过不同的阈值电压映射得到的，一般采用逐步增量脉冲编程（incremental step pulse programming, ISPP）技术来精准控制存储单元的电压值.编程操作以页为单位，每进行一次编程操作，闪存单元的阈值电压增加Vpp，其阈值电压不断逼近校验电压Vp.因此，编程状态的MLC 型NAND 存储单元阈值电压Pu(v)呈现出均匀分布，建模公式为

式中，Vp={V1,V2,Vmax}，Vpp的值设为0.3.

除此之外，编程状态的阈值电压也会受到编程干扰的影响，编程干扰Ppn(v)可拟合成高斯分布，即

式中，σpn为编程干扰的标准方差，编程状态的阈值电压Pp(v)可以看成是式(2)和(3)的卷积，即

式中，Pp={P10,P00,P01}，经过PN 干扰后MLC 闪存单元阈值电压的统计图如图1(b)所示.

1.2 单元间干扰（CCI）

单元间干扰是由相邻单元之间的寄生电容耦合产生的，而由CCI 导致的电压改变量VCCI可以表示为

式中，∆Vk为相邻单元阈值电压的偏移量，γk为电容耦合率.MLC NAND 闪存中采用奇偶位线结构，偶字线的MLC 单元会受到5 个相邻单元的CCI 影响，而奇字线的MLC 单元会受到3 个相邻单元的CCI 影响[10]，其中垂直方向的电容耦合系数γy=0.080，水平方向的电容耦合系数γx=0.100，对角线方向的电容耦合系数γxy=0.006.文献[11]利用单元预编码技术可以消除CCI，但是这种技术对处于擦除态的存储单元效果不大.擦除态存储单元的建模近似采用高斯拟合，其阈值电压的平均值由Vmin转化成

1.3 数据驻留噪声

数据驻留噪声与PE 及存储数据的停留时间有关，其阈值电压分布函数可以表示成[12]

其中平均值为

标准方差为

式中，ur={ur11,ur10,ur00,ur01}，σr={σr11,σr10,σr00,σr01},Vs={Vmin,V1,V2,Vmax},x0,Xt,Yt,θi,θ0是参数，T表示数据驻留时间，P表示闪存的编程/擦除循环次数.数据驻留噪声对存储单元的阈值电压分布影响为

存储单元其他状态的阈值电压Pi(v)为

式中，Pi ∈{P10,P00,P01}，Vi ∈{V1,V2,Vmax}，σi ∈{σ10,σ00,σ01}，v为已知阈值电压，经过DRN 干扰后MLC 型闪存单元阈值电压的统计图如图1(c)所示.

2 Polar 码编译码原理

Polar 码是一种被证明可达香农极限的线性新型纠错码.对于N=2n个独立的二进制输入信道W（其中n为自然数），polar 码对其进行信道组合操作和信道分离操作，从而得到N个相互依赖的极化信道.当N →∞时，一部分信道的容量将会趋于1（即通过该部分信道传输的比特一定会被正确接收），而其余信道的容量将趋于0（即完全无法在信道上可靠地传输比特），基于此理论，通信过程中选择容量趋于1 的信道上传输承载信息的自由比特，而在容量趋于0 的信道上传输对收发端都已知的固定比特（即冻结比特）.

2.1 Polar 码编码

依照polar 码P(N,K,A,uAc) 的参数形式，N为码长，码率可以表示为K/N，设A是集合{1,··· ,N}的长度为N的子集，uA用来存放信息位；Ac是A的补集，uAc用于描述已知的冻结比特，一般都取0.长度为N的polar 码的编码过程由待传输的信息序列=(u1,u2,··· ,uN)与生成矩阵GN相乘完成[13]，即

式中，GN=BNF⊗n，F⊗n是核心矩阵的n次Kronecker 张量积.式(11)可进一步表示为

式中，GN(A)是由集合A对应生成矩阵GN的行向量所构成的子矩阵.

图1 各种干扰情况下的MLC 闪存单元阈值电压统计Figure 1 MLC flash cell threshold voltage statistics with different noise interference

2.2 Polar 码译码

Polar 码的冻结位对于编译码两端是已知的，因此polar 码译码实际上是对信息位的译码.polar 码的译码算法主要有连续消除（successive cancellation, SC）算法，置信传播（belief propagation, BP）算法[14]等.其中BP 算法是基于Tanner 图实现具体译码过程的，详细步骤如下：

步骤1初始化.

步骤2传递与更新.首先每个校验节点与子节点分别传递消息给父节点，各个父节点利用接收到的消息更新本节点的消息；然后父节点将更新后的消息又传递给子节点，各个子节点继续更新本身的消息.

步骤3迭代终止.子、父节点根据收到的消息将每次迭代后的最终消息进行硬判决，译码成功则不再迭代，否则进行下一次迭代直至最大迭代次数.

BP 算法具有并行运算的优点，与SC 译码算法相比，译码速度较快，因此本文采取BP算法作为polar 码的译码算法.

3 基于MI 异构的polar 码优化

本文借助蒙特卡罗方法，利用大量随机信息建立MLC 型闪存的概率模型，经过噪声（CCI、DRN 等）的干扰，统计MLC 存储单元各个状态的阈值电压分布.将一随机序列经过MLC 型闪存信道后的LLR 值ϕ计算出：和P(ϕ|x=1)=1−P(ϕ|x=0)，通过式(13)得到其对应的互信息量I(ϕ,X)

然后在传统的AWGN 信道中以互信息量I(ϕ,X)得到等价的方差δe.本文正是利用所获得的新方差计算存储单元比特的巴氏参数值实现一对polar 码的构造.巴氏参数可用来衡量极化后存储单元比特的存储可靠性，定义为

式中，巴氏参数越小，该存储单元比特的数据可靠性就越高.每存储单元比特的巴氏参数值计算公式为

本文采用一种近似的方法计算巴氏参数的迭代初始值

式中，δe为LLR 分布的等效方差，C(δe)是根据已知δe利用Ungerboeck 集分割方式并计算存储单元比特的容量.

已知码率R和码长N，将提出的polar 码构造方法应用到MLC 型NAND 闪存信道中，其详细算法如下.

算法1基于MI 异构的polar 构造算法

输入：码率R，码长N，最大迭代次数Nite-max，随机信息l

初始化计算冻结比特数K ←N(1−R)；

将随机信息l传送至MLC 闪存信道，得到LLR 值ϕ；

由式(13)计算I(ϕ,X)；

基于MI 重新拟合使ϕ在AWGN 信道下服从高斯分布，得到其在AWGN 信道下等效的方差δe；

基于式(15)∼(16)以及新方差δe可获取所有存储单元比特的巴氏参数值；

将得到的进行降级排序，选取前K个单元比特作为冻结比特位来实现对polar 码的优化构造.

该polar 码优化方法通过利用MLC 闪存信道的特性，与传统的AWGN 信道之间建立联系，以MI 来重新拟合信道的LLR 信息并使其呈现高斯分布，而MLC 闪存信道与AWGN 信道间的差异性能用MI重新拟合方法来计算，因此传统的polar 码构造方法不再适用于MLC闪存信道.

文献[5]中采用的基于最大互信息的优化方法利用最大化MLC 存储信道的输入与输出之间的互信息量，其中根据MLC 闪存单元的最高有效位和最低有效位计算互信息量来获取读取电压值RN.而本文提出的优化方法[15]采用非均匀量化，在靠近阈值电压分布的交叠处（即易发生错误的区域）设置感知电压，并且通过阈值电压来计算熵值H(v)，公式为

然后设置熵值H(RN)=θ(θ ∈[0,1])，获取重叠区的读取电压RN，提高易发生错误区感知电压的精度并实现良好的polar 码纠错能力.

4 仿真结果

为了研究MLC 型闪存信道中存储数据的耐久度和可靠性，本文以提出的基于MI 异构的polar 码构造方案进行数据仿真，来验证其BER(bit error rate)和FER(frame error rate)性能.其中polar 码码长N= 2 048，采用BP 译码算法并且设置最大迭代次数Nitemax= 50.本文中MLC 型闪存信道噪声考虑CCI、PN 和DRN 干扰，设置如下参数：Vmin= 1.40，σe=0.35，V1= 2.60，V2= 3.20，Vmax= 3.93，σpn= 0.05，x0= 1.4，Xt= 0.000 055，Yt=0.000 235，θi=0.62，θ0=0.32，T=6 h.

图2 为码率R= 0.75 的polar 码基于不同的构造方法的BER 性能曲线，同时与文献[5]进行了实验对比.高斯近似法构造的polar 码性能最差，当误码率BER=1×10−5时，本文优化的polar 码比巴氏参数法构造的polar 码能增加1 000 次的擦除次数.相比于文献[5]中方法构造的polar 码，本文提出的方法构造的polar 码在误码率性能上有1 个数量级的提升.

图3 和4 分别为码率R=0.80 的polar 码基于不同的构造方法的BER 和FER 性能曲线.图3 表明当误码率约为2×10−5时，新构造的polar 码拥有23 200 次的擦除次数，比巴氏参数法构造的polar 码和蒙特卡罗法优化的polar 码分别增加2 000 和6 800 的擦除次数.图4 显示当P= 2.1×104时，本文优化的polar 码比巴氏参数法构造的polar 码和蒙特卡罗法构造的polar 码在误码率上分别有1 个和2 个数量级的提升.当P <2.5×104时，本文提出的优化方法构造的polar 码比文献[5]优化方法构造的polar 码在误码率性能上至少提升半个数量级.

比较图5 和6 可以看出，当码率R增长至0.85，本文提出的polar 码仍优于其他方法构造的polar 码.当P >1.5×104时，改进的polar 码至少比巴氏参数法构造的polar 在性能上有1 个数量级的提升，而蒙特卡罗法优化的polar 码也会优于巴氏参数构造的polar 码.本文提出的优化方法构造的polar 码比文献[5]优化方法构造的polar 码在误码率性能上的表现趋于吻合.

图2 MLC 型NAND 闪存信道中码率R=0.75 的polar 码BER 性能比较Figure 2 BER performance comparison of polar codes in MLC NAND flash channel(R=0.75)

图3 MLC 型NAND 闪存信道中码率R=0.80 的polar 码BER 性能比较Figure 3 BER performance comparison of polar codes in MLC NAND flash channel(R=0.80)

图4 MLC 型NAND 闪存信道中码率R=0.80 的polar 码FER 性能比较Figure 4 FER performance comparison of polar codes in MLC NAND flash channel(R=0.80)

图5 MLC 型NAND 闪存信道中码率R=0.85 的polar 码BER 性能比较Figure 5 BER performance comparison of polar codes in MLC NAND flash channel(R=0.85)

图6 MLC 型NAND 闪存信道中R=0.85 的polar 码FER 性能比较Figure 6 FER performance comparison of polar codes in MLC NAND flash channel(R=0.85)

从图2～6 可以看出，随着码率的增加，本文提出的优化方法构造的polar 码与文献[5]中的优化方法构造的polar 码在误码率性能上趋于一致.当码率升高时，MLC 闪存单元的交叠区发生错误的比特数增加，polar 码的纠错能力也会下降.

5 结 语

根据MLC 闪存信道的特性，本文提出了一种基于MI 异构的polar 优化方法.该方法基于MI 对MLC 闪存信道的LLR 分布重新拟合，得到与闪存信道等效的方差从而进行polar 码的优化构造.仿真结果表明本文构造的polar 码性能优于传统方法构造的polar 码，且比蒙特卡罗法构造的polar 码有多达2 个数量级的性能提升.此外，本文提出的优化方法也可以应用到3 层存储单元（trinary-level-cell, TLC）闪存、4 比特单元（quad-level-cell, QLC）闪存等高密度存储系统中.