一种纠单个闪存单元移位错误码的译码方法

慕建君，赵 鹏，焦晓鹏

(西安电子科技大学 计算机学院，陕西 西安 710071)



一种纠单个闪存单元移位错误码的译码方法

慕建君，赵 鹏，焦晓鹏

(西安电子科技大学 计算机学院，陕西 西安 710071)

通过利用置换来表示闪存单元数据的等级调制编码方案，可有效地提高闪速存储设备所存储数据的可靠性，而成为闪速数据存储系统差错控制编码的一个重要技术．基于置换码的交织，提出了一种可以纠单个闪存单元等级“移位错误”的等级调制纠错码的构造方法． 在深入分析置换理论性质的基础上，给出了该等级调制纠错码的相应译码方法．

置换码;闪存;等级调制;纠错码

近10年以来，对置换码(permutation codes)的研究受到了许多学者的普遍关注[1-3]．置换码经历了一次强力的复苏，这主要是由于陆续发现了置换码在电力线数据传输[4]和多级闪存[5]等领域的新应用．

闪存面临的一个主要问题是存储单元数据的可靠性． 闪存中所存储的数据可能受到电荷泄漏、读/写干扰、数据保持噪声(data retention noise)和随机电报噪声干扰的影响而遭到损坏[6]． 由于闪存设备中所产生错误的特殊性，所以RS(Reed-Solomon)码和BCH(Bose-Chaudhuri-Hocquenghem)码等经典的差错控制编码方法不能有效地纠正这些错误[7]． 为了提高闪速存储设备的可靠性，利用置换来表示闪存单元电位的等级调制(rank modulation scheme)方法．文献[5]中提出了一种基于等级调制的差错控制编码方案，开辟了闪速数据存储系统差错控制编码技术的新方向．

对于具有n个单元闪存的等级调制编码方案，设ci(i=1， 2， …， n)表示该闪存第i个单元的电荷等级(简称单元等级)，n个单元等级的排序可以编码为集合{1， 2， …， n}上的一个置换(a1， a2， …， an)，使得 ca1> ca2> …> can．等级调制编码方案中闪存数据的存储是以单元电荷值的相对等级的形式存储，而不是以电荷的绝对值的形式存储． 等级调制编码方案可以纠正闪速存储设备中单元等级的“相邻对换错误(adjacent transposition error)”． 但是，受闪存单元的位置和电荷量以及其他因素影响而导致电荷泄露速度的不同，从而可能产生单元等级的“移位错误(translocation error)”． 闪存单元等级的移位错误使得与这个单元电荷值相对大小有关的一系列其他单元的等级排列顺序发生改变，从而导致闪存设备中所存储的数据发生错误．

对于等级调制纠错编码的研究，除了基于等级调制的低密度校验码(Low-Density Parity-Check codes，LDPC)的构造和译码算法[8]以及局部等级调制码的构造方法[9]外，目前主要是针对闪速存储系统中具有各种“特殊错误类型”特点的等级调制纠错码进行了一些研究． 基于Lee度量空间中完备球包，文献[10]提出了纠单个Kendallτ错误的等级调制纠错码; 基于Kendallτ距离度量，文献[2]中理论分析了纠闪存单元等级“相邻对换错误”的等级调制纠错码码字个数的上界和下界． 基于切比雪夫距离度量，文献[11-12]分别独立提出了“有限大小错误(limited magnitude error)”等级调制纠错码的构造方法; 基于Ulam距离度量，文献[13]中提出了纠闪存中单个单元等级“移位错误”的等级调制纠错码的构造方法和译码方法．

但是，对于实际获取的闪存单元等级的码字置换η=(2， 1， 5， 4， 3， 6， 8， 7)，利用文献[13]中提出的纠单个单元等级“移位错误”的等级调制纠错码的译码方法无法进行译码． 笔者针对闪速存储系统中单元等级“移位错误”，借助置换码的一些性质，利用置换交织手段，提出了一种可纠正这种单个单元等级“移位错误”的等级调制纠错码的构造方法，并给出相应的译码方法．

1 置换理论

定义1 设i，j∈[n]，将恒等置换I[n]=(1， …， i-1， i， i+1， …， j-1， j， j+1， …， n) (i

对于集合[n]上的一个置换π=π(1)， π(2)， …， π(n)，如果i π(j)，则称(i， j)为排列 π(1)π(2)…π(n) 的一个逆序对．一个排列(或置换)包含的逆序对的总个数称为该排列(或置换)的逆序数，记为N(π)．

对于每个i∈[n]，定义两个置换π∈Sn和τ∈Sn的乘积为(π∘τ)(i)=πτ(i)．任意一个置换 π∈ Sn都可以表示成若干对换的乘积．表示成偶数个对换乘积的置换(或逆序数N(π)为偶数的置换)叫做偶置换，表示成奇数个对换乘积的置换(或逆序数N(π)为奇数的置换)叫做奇置换．根据这些定义容易得到置换的如下两个性质[14]．

引理1 对于集合[n]上的置换π=π(1)， π(2)， …， π(n)(或排列 π(1)π(2)…π(n))，该置换(或排列)的逆序数 N(π)= π(1)后面比π(1)小的数的个数+π(2)后面比π(2)小的数的个数+…+ π(n-1) 后面比 π(n-1) 小的数的个数．

引理2 集合[n]上的一个置换π与一个对换(i， j)乘积后一定改变原来置换π的奇偶性．

对于置换π∈Sn和子集P⊆[n]，通过保留π中属于P的元素而去掉其他所有元素后得到的置换称为π在P上投影πP．例如，对于 π= (4， 6， 3， 1， 2， 5)和 P= {2， 4， 6}，π在P上投影 πP= (4， 6， 2)．

定义2 对于不同的i，j∈[n]，I[n]=(1， …， i-1， i， i+1， …， j-1， j， j+1， …， n) (i

当j

引理3 设i， k∈[n]，k>i且k-i>2，φ(i， k)和φ(k， i)分别为集合[n]上置换的一个“右移位”和一个“左移位”．设∘表示置换的合成运算．对于集合[n]上的给定置换 π= π(1)， …， π(i-1)， π(i)， π(i+1)， …， π(k)， π(k+1)， …，π(n)，则有 π∘ φ(i， k+1)∘ φ(k， i)= π∘ (i， k+1)，即集合[n]上一个“右移位”φ(i， k+1) 和一个“左移位”φ(k， i)的乘积等价于集合[n]上一个“对换”(i， k+1)．

证明 由定义2知

则有

因此，等式π∘φ(i， k+1)∘φ(k， i)=π∘(i， k+1)成立．

2 错误模型

具有n个单元闪存中，等级调制编码方案利用n个单元等级的排序来表示数据．对于具有9个单元的闪速存储设备，可以利用置换 π= (6， 3， 5， 1， 8， 9， 2， 4， 7)表示对应每一个闪存单元等级相对值由高到低的一个等级排列(如图1和图2所示)．

图1 等级调制码及其相邻对换错误(3，5)图2 等级调制码及其移位错误φ(2，8)

2.1 相邻对换错误

如果两个相邻闪存单元的电荷相对值差距很小，当电荷值较高的单元由于受到干扰电荷发生偏移，使得这个单元的电荷值高于或低于相邻单元的电荷值时，这两个单元的电荷相对等级就发生了对换，这就是单元等级的“相邻对换错误”． 图1所示的就是一种典型的闪存单元等级的“相邻对换错误”．

2.2 移位错误

由于受到闪存单元的位置和电荷量以及其他因素影响，在电荷泄漏过程中，某个闪存单元的电荷泄露速度明显高于其他许多单元电荷泄漏的速度． 在一定时间内，这个单元的电荷等级就低于其他许多单元的电荷等级，同时，闪存单元电荷值的相对等级次序发生变化，从而导致了闪存单元非相邻等级偏移错误，即闪存单元等级的“移位错误”．图2所示的就是一种典型的闪存单元等级的“移位错误”．

3 纠单个闪存单元等级移位错误码的构造与译码

为了构造纠单个闪存单元等级移位错误的等级调制纠错码，下面给出两个置换码的交织码的定义．

定义3 设C1(1)，C1(2)， …， C1(m)(长度为m)和C2(1)， C2(2)， …， C2(m-1) (长度为 m-1) 分别是置换码C1和C2的码字，将C1和C2的这两个码字分量进行交织，得到的码字C1(1)， C2(1)， C1(2)， C2(2)， …， C1(m-1)， C2(m-1)， C1(m)的集合称为置换码C1和C2的交织码C，记为 C= C1* C2．

当置换码C1和C2的码字的长度都为m时，可以定义其交织码 C= C1* C2的码字为C1(1)， C2(1)， C1(2)， C2(2)， …， C1(m)， C2(m)．

例1 考虑码长n=8的可纠正单个闪存单元等级右移位错误的纠错码 C= C1* C2，其中C1表示集合 P= {2， 4， 6， 8}上奇置换所构成的置换码，C2表示集合 Q= {1， 3， 5， 7}的奇置换所构成的置换码．利用 C1和C2的交织码 C= C1* C2对闪存单元等级进行编码．

图3 右移位错误φ(3, 6)对码字置换ω的影响，实际获取的错误码字置换η=(2， 1， 5， 4， 3， 6， 8， 7)

如图3所示，假设闪存单元等级可以编码为码字置换 ω= (2， 1， 6， 5， 4， 3， 8， 7)∈ C= C1* C2，由于右移位错误φ(3， 6)对编码码字置换ω中的影响，而使得实际获取的闪存单元等级的错误码字置换变为 η= (2， 1， 5， 4， 3， 6， 8， 7)∉ C= C1* C2．

结合前面所给出的置换的一些性质，下面的结论给出了按照上述所给置换码交织码的方法所构造的交织码 C= C1* C2的译码方法，同时也证明了该交织码 C= C1* C2是可以纠正单个闪存单元等级右移位错误的等级调制纠错码．

定理1 设C1表示集合P=i|i∈[n]∧i为偶数上奇置换所构成的置换码，C2表示集合 Q= i| i∈ [n]∧ i为奇数}上奇置换所构成的置换码．若按照上述所给置换码交织码的方法将置换码C1和C2进行交织，则所构造的交织码 C= C1* C2是可以纠正单个闪存单元等级右移位错误的等级调制纠错码．

证明 假设闪存单元等级编码后的码字置换 ω∈ C= C1* C2，而实际获取的闪存单元等级的错误码字置换为η，由于交织码 C= C1* C2中仅仅可能出现单个闪存单元等级的右移位错误φ(i， j)(i， j∈ [n]，且 i

设实际获取的闪存单元等级的码字置换η的第l个分量为η(l)，由交织码 C= C1* C2的定义和右移位错误φ(i， j)的定义知 i= minlη(l)-l (mod2)≠ 1，即i等于实际获取的错误码字置换η中使得其第l个分量元素η(l)偏离原编码码字置换ω中原来位置的最小的偏离量l．

令lmax=maxlη(l)-l(mod2)≠1．由于原来编码码字置换ω中各元素的奇偶性与它们位置的奇偶性刚好相反，而实际获取的错误码字置换η中连续的两元素η(lmax)与 η(lmax+1) 的奇偶性相同，所以，闪存单元等级的单个右移位错误为φ(i， lmax)或者φ(i， lmax+1)．因此，闪存单元等级的原编码码字置换ω或者为 ω′= η φ(lmax， i)或者为 ω″= η φ(lmax+1， i)．

为了确定ω′和ω″中哪一个是正确的原编码码字置换，下面分析两者之间的关系．

由ω′=η φ(lmax， i)得η=ω′ φ(i，lmax)，并将其代入 ω″= η φ(lmax+1， i)，利用引理3可得

ω″=η φ(lmax+1， i)=ω′ φ(i，lmax) φ(lmax+1， i)=ω′(i， lmax+1) ．

下面通过具体的例子来说明所提出的可以纠正单个闪存单元等级右移位错误的等级调制纠错码及其译码方法的有效性．

例1(续) 假设闪存单元等级可以编码为码字置换ω∈ C= C1* C2，由于闪存存储信道各种噪声的干扰，码字置换ω中发生的错误为φ(i， j)(i， j∈ [8]，且 i

对于给定的η，译码器首先确定实际获取的码字置换η中元素模2不等于1的元素集合{5， 4， 3， 6}，于是可得 i= minl η(l)-l (mod2)≠ 1=3，lmax= maxl η(l)-l (mod2)≠ 1=6，由定理1知单元等级的原编码码字置换ω或者为 ω′= η φ(6， 3)= (2， 1， 6， 5， 4， 3， 8， 7)，或者为 ω″= η φ(7， 3)= (2， 1， 8， 5， 4， 3， 6， 7)．

4 总 结

在深入分析置换码性质的基础上，利用置换码的交织技术，提出了一类纠单个闪存单元等级“移位错误”的等级调制纠错码(即交织码)的构造方法，同时给出相应的译码方法． 验证实例表明，所提出的译码方法可以对实际获取的闪存单元等级的交织码码字置换 η= (2， 1， 5， 4， 3， 6， 8， 7)进行正确译码，克服了文献[13]中提出的可纠单个单元等级“移位错误”的译码方法无法对这一类码字置换进行译码的缺点． 计算实例验证了所提出译码方法的正确性．

[1] GOLOGLU F, LEMBER J, RIET A E, et al. New Bounds for Permutation Codes in Ulam Metric [C]//2015 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2015: 1726-1730.

[2]BARG A, MAZUMDAR A. Codes in Permutations and Error Correction for Rank Modulation [J]. IEEE Transactions on Information Theory, 2010, 56(7): 3158-3165.

[3]BUZAGLO S, ETZION T. Bounds on the Size of Permutation Codes with the Kendallτ-Metric [J]. IEEE Transactions on Information Theory, 2015, 61(6): 3241-3250.

[4]PAVLIDOU N, HAN VINCK A J, YAZDANI J, et al. Power Line Communications: State of the Art and Future Trends [J]. IEEE Communications Magazine, 2003, 41(4): 34-40.

[5]JIANG A, MATEESCU R, SCHWARTZ M, et al Rank Modulation for Flash Memories [C]//Proceedings of IEEE International Symposium on Information Theory. Piscataway: IEEE, 2008: 1731-1735.

[6]CAPPELLETTI P, GOLLA C, OLIVO P, et al. Flash Memories [M]. Amsterdam: Kluwer, 1999.

[7]MICHELONI R, MARELLI A, RAVASIO R. Error Correction Codes for Non-Volatile Memories [M]. Vimercate: Springer, 2008.

[8]ZHANG F, PFISTER H D, JIANG A. LDPC Codes for Rank Modulation in Flash Memories[C]//Proceedings of IEEE International Symposium on Information Theory. Piscataway: IEEE, 2010: 859-863.

[9]GAD E, LANGBERG M, SCHWARTZ M, et al. Constant-weight Gray Codes for Local Rank Modulation[J]. IEEE Transactions on Information Theory, 2011, 57(11): 7431-7442.

[10]JIANG A, SCHWARTZ M, BRUCK J. Error-Correcting Codes for Rank Modulation [C]//Proceedings of IEEE International Symposium on Information Theory. Piscataway: IEEE, 2008: 1736-1740.

[11]KLØVE T, LIN T T, TSAI S C, et al. Permutation Arrays under the Chebyshev Distance [J]. IEEE Transactions on Information Theory, 2010, 56(6): 2611-2617.

[12]TAMO I, SCHWARTZ M. Correcting Limited-magnitude Errors in the Rank-modulation Scheme [J]. IEEE Transactions on Information Theory, 2010, 56(6): 2551-2560.

[13]FARNOUD F H, SKACHEK V, MILENKOVIC O. Error-correction in Flash Memories via Codes in the Ulam Metric [J]. IEEE Transactions on Information Theory, 2013, 59(5): 3003-3020.

[14]ROTMAN J J. A First Course in Abstract Algebra with Applications [M]. Third Edition. Upper Saddle River: Prentice Hall, 2005.

(编辑：郭 华)

Decoding of codes correcting a single translocation error for the cell’s level of flash memory

MUJianjun，ZHAOPeng，JIAOXiaopeng

(School of Computer Science and Technology, Xidian Univ., Xi’an 710071, China)

By using permutation to represent the data of flash memory cells, the rank modulation scheme, which can effectively improve the reliability of the data stored by the flash storage device, has become an important technology of the error control coding in flash data storage system. Based on permutation code interleaving, the construction for the rank modulation code that can correct a single translocation error for the cell’s level of flash memory is proposed. By making a detailed analysis of the properties of permutation theory, the corresponding decodinHocquenghem-Bose-Chandharig method for this rank modulation code is given.

permutation codes; flash memory; rank modulation; error-correcting codes

2015-11-03

时间：2016-04-01

国家自然科学基金资助项目(61271004, 61471286)

慕建君(1965-)，男，教授，E-mail: jjmu@xidian.edu.cn．

http://www.cnki.net/kcms/detail/61.1076.tn.20160401.1622.018.html

10.3969/j.issn.1001-2400.2016.06.009

TP301.6;TN911.22

A

1001-2400(2016)06-0051-05