一種糾單個閃存單元移位錯誤碼的譯碼方法

慕建君，趙 鵬，焦曉鵬

(西安電子科技大學 計算機學院，陜西 西安 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