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