Flash存储中的纠错编码

康 旺 张有光 金令旭 王名邦

(北京航空航天大学 电子信息工程学院，北京 100191)

因闪存(Flash memory)具有非易失性、高密度、高存储速度、低功耗、防震等诸多优良特性而备受人们青睐，随着移动通信的发展以及便携式设备的普及，闪存的应用也越来越广泛，成为当前市场上最主流的固态存储器之一.闪存通常由若干闪存块(block)组成，闪存块由若干物理页(page)组成，而物理页又由若干基本的存储胞元(cell)组成.闪存根据胞元内部结构的不同可分为“或非(NOR)”型和“与非(NAND)”型两种，而根据胞元可存储比特(bit)数目的不同又可以分为SLC(Single-Level Cell)型和MLC(Multi-Level Cell)型两种，SLC型Flash的胞元状态只有两个，只能存储一个比特信息，而MLC型胞元状态有多个(4～256或者更多)，可以存储多个比特信息［1］.本文只讨论 MLC NAND Flash.

NAND Flash以页为单位进行读写操作，且在重写之前需对目标区域进行擦除，而以块为单位进行擦除，且擦除次数是有限的(SLC为10万次左右，MLC为1万次左右)，因此，提高Flash的生命周期是当前研究热点之一，也是Flash大规模普及面临最严重的挑战之一.目前的研究方案有很多，涉及不同的层次，其中采用磨损均衡的方式以平衡各个块的擦除次数主要是考虑设计一个良好的文件系统，该方案易于操作也比较有效，但是其会带来额外的数据擦除［2］;而采用存储编码(storage coding)通过对存储的数据进行编码，以控制存储状态转移，从而提高存储单元的重写次数，减小块的擦除次数，如 floating codes［3］，buffer codes［4］， multidimensional Flash codes［5］， rank modulation［6］等，其同样会带来系统设计上的难度，目前难以应用于实际系统;另外一种方案就是结合纠错编码、坏块管理等方式把坏块重新利用，从而提高Flash的生命周期［7］，本文主要考虑这种方式.

Flash中存在的另一个挑战是存储数据的可靠性，随着擦除次数的增加，胞元的可靠性会降低，而且读写电路的误差以及外界环境引入的噪声会使得存储数据产生差错，存储系统一般通过错误校验与纠错(ECC，Error Checking and Correction)模块来保证数据的可靠性，写入数据时，对存储数据进行编码，读取数据时检测差错并进行纠正，如汉明编码、BCH码、LDPC码等.另外还有文献考虑把ECC与存储编码联合起来设计的编码方案［8］，既提高系统可靠性，同时又提高系统的生命周期.

针对目前Flash中的可靠性与寿命两个典型问题提出了一种基于正交映射的编码方法，研究分析发现，该方法不仅具有纠错和提高寿命的能力，还能够提供分布式多用户共享以及历史数据恢复等实际应用中的解决方案.

1 Flash存储系统结构框架

典型的Flash存储系统结构框架［2］如图1所示，存储技术设备层(MTD，Memory Technology Device)作为底层功能模块提供对Flash存储单元最基本的读、写、擦除等操作;闪存映射层(FTL，Flash Translation Layer)作为上层文件系统与存储单元之间的中间层，提供逻辑块地址(LBA，Logic Block Address)到物理块地址(PBA，Physic Block Address)之间的映射，不同的存储系统根据实际应用需求采用不同的映射方法，典型的映射方式有基于页地址映射和基于块地址映射［2］等;Flash控制器(Flash controller)是Flash存储管理相当重要的一个模块，包括磨损均衡(WL，Wear Leveling)、垃圾回收(GC，Garbage Collection)、错误检验与纠正(ECC，Error Checking and Correction)、存储编码(SC，Storage Coding)、坏块管理(BBM，Bad Block Management)等，这些模块对Flash存储系统的稳定性与可靠性提供保障.本文在典型系统结构的基础之上，构建了一个正交映射编码模块(OMCL，Orthogonal Mapping Coding Layer)，该模块提供了一种基于正交映射的纠错编码方法.

图1 典型的Flash存储系统结构

2 基于正交映射的纠错编码

2.1 纠错编码原理

考虑一个Q元(N，M，d)码C，其包含有M个码字，每个码字{q，q∈Ω}N长度为N，取自于 Q元集合 Ω ={0，1，…，q－1}，任意两个码字之间的汉明距离为d.如果Q=2，则C是一个二进制码.编码过程即通过一个编码函数εC:M→C，把消息集合M中的M=|M|个消息一一映射为码C中的M个码字，即εC(m，m∈M).

由于环境噪声、电路误差以及Flash的物理特性，码字中的某个或多个元素可能发生错误或擦除，这里的错误指的是码字中某些不知位置的元素发生了改变，但仍属于集合Ω，而擦除指的某些可知位置的元素变成了不可识别的符号(如Flash胞元由于电压过冲超过了可识别的电压范围)，这里用“?”表示.根据编码理论［9］，最小汉明距离为DH(，)=d的纠错码可以纠正t个错误，同时检测e个错误时，满足如下不等式:

2.2 正交映射函数与序列

设函数集合F为

若满足:

这里Ki为某个不等于0的常数，则称F在x∈［T1，T2］为正交函数集.如果在F之外，不存在另外一个非零函数与F中每一个函数都正交，则称F为完备正交函数集，如三角函数集、沃尔什(Walsh)函数集等.如图2a所示为 t∈［0，T］的8阶沃尔什函数集.

定义正交函数序列fi(n)为正交函数在其定义域内的N个离散采样序列，其满足:

典型的正交函数序列有雷徳麦彻(Rademacher)序列，沃尔什(Walsh)序列等.如图2b所示为采样数N=23时的8阶沃尔什序列，雷徳麦彻序列与沃尔什序列都能很方便地通过哈达玛矩阵进行快速生成、扩展与相互转化.

图2 沃尔什正交函数集与序列

2.3 基于正交序列映射的纠错编码

考虑消息序列集合M，本文提出了一种基于正交序列映射的纠错编码(正交映射码)C，其编码函数εC:M→C把M中M=|M|个消息映射为正交函数序列集中的相应序列;解码函数用相应的正交函数序列与信道输出序列相乘即可恢复原始信息.考虑一个q元(N，M，t)正交映射码C，其中每个码字长度为N，包含M个码字，能纠正t个错误.

例1 如图3所示，为考虑二进制消息序列，以沃尔什序列作为映射序列的(4，4，2)码.

图3 一个正交映射编码示例

例1是一个简单的基于沃尔什序列的映射编码，码长为4，存在4个码字，可纠正2个错误.由图3可以看到，这个映射过程其实类似于多用户扩频通信中地址码的分配［10］，但是由于Flash存储结构不同于无线信道，这个过程不能简单地直接应用到Flash当中.第3节介绍如何结合MLC NAND Flash的结构特点，将这种正交映射机制应用到Flash当中，最后给出正交映射编码在Flash中的应用原理以及系统结构框架，同时分析这种码的纠错能力.

3 Flash中的正交映射编码

3.1 Flash中的正交映射编码原理与系统结构

根据Flash中的存储结构以及操作特性，可以构建正交映射编码的系统结构如图4所示.图中FTL模块提供逻辑地址到物理地址的映射，正交映射编码模块提供基于正交序列映射的纠错编码构造方法.设每个块由P个页组成，可把P个页分成M个超页(super page)［11］，每个超页由K个普通页组成，同时为每个普通页分配一个唯一的正交映射序列，当有信息数据m1经过FTL映射后需要存储到Flash中的某个页时，假设当前超页为空页(free page，即可以直接写入数据的页)，则直接把m1通过正交映射编码后的数据(记为c1)存入当前超页中的某个普通页(记为p1)，然后当有新数据或者更新数据m2到来，则把p1的数据c1放入缓冲区，再把m2进行正交映射编码后的数据c2与c1进行叠加，存入下一个普通页(记为 p2)，而把p1标记为脏页(dirty page，即不可写入数据，需要进行擦除后才能继续使用的页)，依此进行操作.因此，在一个超页中，只存在一个普通页是有效页(active page，即包含有效数据的页)，当某个超页没有空页时，需要对该超页的数据进行整理并转存，这涉及磨损均衡与垃圾回收过程，这里不做讨论.

图4 正交映射编码系统结构

读取数据时，把有效页读入缓存区中，然后根据相应的正交映射序列恢复出原始数据，由于正交映射序列的正交性，最后总能根据每个数据分配的正交映射序列还原出相应的原始数据，并能纠正部分错误.本文提出的正交映射编码是一个并行编码的过程，可以利用并行结构进行处理，从而提高系统效率与处理速度.

例2 如图5所示，考虑沃尔什序列作为正交映射编码的映射序列，只考虑一个超页，其包含4个普通页，对应4个沃尔什序列.本例简单地描述了正交映射编码和解码过程.

3.2 正交映射编码的解码与纠错能力

设正交映射序列长度为N，每个超页包含K个普通页，对应K个正交映射序列，由3.1节可知，当前超页中唯一有效页存储的数据为

这里1≤k≤K.

当要恢复某一页pi(1≤i≤k)的原始数据时，用该页对应的正交映射序列进行如下解码过程:

图5 正交映射编解码示例

对正交映射序列进行归一化即可恢复原始数据.

设Flash中每个存储单元具有πq个状态，这里 πq={0，1，…，q－1}为一个状态集合，考虑正交映射编码(N，M，t)，若每个超页包含K个普通页，则M=K.从编码过程可知，任意两个码之间的汉明距离为

因此根据编码理论，其可以纠正(DH－1)/2个错误.而且，在目前应用的Flash中，πq的状态数目(≤256)是有限的，这也决定了超页的大小以及码的个数，即M=K≤q/2.

4 正交映射编码的典型应用

4.1 分布式多用户共享存储

如第3节所述，考虑如图4所示的正交映射编码结构，同样采用超页作为存储单元.假设有K个用户共享同一块存储空间，通过上层应用程序以及文件系统的调用，需要多用户进行共享存储时，在图4的基础上，只需修改正交映射编码模块，使其为每个用户分配不同的正交映射序列fi(N)，0≤i≤K－1即可，其他的操作类似于第3.1节，这样，由于fi(N)之间的正交性，K个用户可以对同一存储空间进行操作，而不会干扰其他用户的数据，而且不需要进行加密即可在一定程度上实现用户彼此之间数据的安全性.随着物联网和云存储的发展，该方法经过扩展可为分布式多用户共享存储提供一种解决方案.

4.2 历史数据恢复

同样基于第3节中图4所示的编码结构，根据上层应用程序的需求，只需修改正交映射模块，当每一次数据写入或者更新时，为每一个数据版本分配一个正交映射序列，即使对同一个逻辑地址区的数据进行修改或者误删除，当需要恢复到历史数据版本时，不需要额外的工具或者操作，只需获取到历史数据版本对应的正交序列，即可无差错的恢复出历史数据，其基本的操作过程类似于第3.1节.当然，由于超页大小的限制，最多只能恢复出K层历史数据.

4.3 坏块利用

在传统的 Flash中，由于擦除次数的限制(MLC，一般为1万次;SLC为10万次)，工艺制作水平的约束，以及环境因素的影响，存储胞元很容易发生毁坏，而在Flash应用中，只要一个胞元发生毁坏，则整个存储块也不能使用，称之为坏块，当坏块的比率达到一定水平时，则整个Flash也不能使用，一般通过坏块管理模块进行坏块查找和管理，坏块的存在大大影响系统的性能与存储数据安全.提高Flash的生命周期也是目前急需解决的一个实际问题.

正交映射编码可以从两个层次解决坏块问题，第1个是胞元层次，即使某个胞元毁坏，仍然可以利用这个块进行数据存储，因为坏的胞元位置是已知的，所以在进行读写操作时，可以忽略这个位置的数据，而利用正交映射编码的纠错能力进行数据纠错即可;第2个是页层次，可以根据编码模块与坏块管理模块之间的交互获得坏页的位置，从而在进行正交映射编码时，忽略这个页的映射序列.这两种方式都能有效地利用坏块，从而提高Flash的生命周期.

5 结论

基于MLC NAND Flash的结构特征与操作特性，提出了一种应用于MLC NAND Flash存储器的正交映射编码方法，在保持整体结构不变的基础上，只需修改编码模块，即可实现错误校验与纠正、多用户共享存储、历史数据恢复、坏块利用等多种实际应用需求.该方法在提高系统可靠性与生命周期的同时，为分布式多用户共享存储以及数据恢复提供了一种解决方案.在本文工作的基础上，只需对传统控制器进行简单的修改，即可开发一个适用于多种应用场景的闪存控制器，这有待未来更进一步的研究.

References)

［1］ Micheloni R，Croppa L，Marelli A.Inside NAND flash memories［M］.Heidelberg，Germany:Springer，2010:19 －89

［2］ Chang Y H，Hsieh JW，Kuo T W.Endurance enhancement of flash memory storage systems:an efficient static wear leveling design［C］//The 44th Design Automation Conference.New York:ACM/IEEE，2007:212－217

［3］ Jiang A X，Bohossian V，Bruck J.Floating codes for joint information storage in write asymmetric memories［C］//IEEE International Symposium on Information Theory.Nice，France:IEEE ISIT，2007:1166 －1170

［4］ Bohossian V，Jiang A X，Bruck J.Buffer coding for asymmetric multi-level memory［C］ //IEEE International Symposium on Information Theory.Nice，France:IEEE ISIT，2007:1186 －1190

［5］ Yaakobi E，Vardy A，Siegel P H，et al.Multidimensional flash codes［C］ //The 46th Annual Allerton Conference on Communication，Control，and Computing.Urbana Champaign:IEEE，2008:392－399

［6］ Jiang A X，Mateescu R，Schwartz M，et al.Rank modulation for flash memories［J］.IEEE Transactions on Information Theory，2009，55(6):2659 －2673

［7］ Kuzntsov A V，Vinck A H.On the general defective channel with informed encoder and capacities of some constrained memories［J］.IEEE Transactions on Information Theory，1994，40(6):1866－1871

［8］ Cassuto Y，Schwartz M，Bohossian V，et al.Codes for multilevel fish memories:correcting asymmetric limited magnitude errors［C］//IEEE International Symposium on Information Theory.Nice，France:IEEE ISIT，2007:1176 －1180

［9］ Huang Q，Lin S，Ghaffar A K.Error-correcting codes for flash coding［C］//Information Theory and Applications Workshop.La Jolla:IEEE ITA，2011:1 －23

［10］ Pickholtz R，Schilling D，Milstein L.Theory of spread spectrum communications-a tutorial［J］.IEEE Transactions on Communications，1982，30(5):855 －884

［11］ Jung J，Suh S B，Yoo C.Spread programming using orthogonal code for alleviating bit errors of NAND flash memory［C］ //International Conference on Consumer Electronics.Las Vegas:IEEE，2010:83 －84