Flash存儲(chǔ)中的糾錯(cuò)編碼

康 旺 張有光 金令旭 王名邦

(北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191)

因閃存(Flash memory)具有非易失性、高密度、高存儲(chǔ)速度、低功耗、防震等諸多優(yōu)良特性而備受人們青睞，隨著移動(dòng)通信的發(fā)展以及便攜式設(shè)備的普及，閃存的應(yīng)用也越來(lái)越廣泛，成為當(dāng)前市場(chǎng)上最主流的固態(tài)存儲(chǔ)器之一.閃存通常由若干閃存塊(block)組成，閃存塊由若干物理頁(yè)(page)組成，而物理頁(yè)又由若干基本的存儲(chǔ)胞元(cell)組成.閃存根據(jù)胞元內(nèi)部結(jié)構(gòu)的不同可分為“或非(NOR)”型和“與非(NAND)”型兩種，而根據(jù)胞元可存儲(chǔ)比特(bit)數(shù)目的不同又可以分為SLC(Single-Level Cell)型和MLC(Multi-Level Cell)型兩種，SLC型Flash的胞元狀態(tài)只有兩個(gè)，只能存儲(chǔ)一個(gè)比特信息，而MLC型胞元狀態(tài)有多個(gè)(4～256或者更多)，可以存儲(chǔ)多個(gè)比特信息［1］.本文只討論 MLC NAND Flash.

NAND Flash以頁(yè)為單位進(jìn)行讀寫(xiě)操作，且在重寫(xiě)之前需對(duì)目標(biāo)區(qū)域進(jìn)行擦除，而以塊為單位進(jìn)行擦除，且擦除次數(shù)是有限的(SLC為10萬(wàn)次左右，MLC為1萬(wàn)次左右)，因此，提高Flash的生命周期是當(dāng)前研究熱點(diǎn)之一，也是Flash大規(guī)模普及面臨最嚴(yán)重的挑戰(zhàn)之一.目前的研究方案有很多，涉及不同的層次，其中采用磨損均衡的方式以平衡各個(gè)塊的擦除次數(shù)主要是考慮設(shè)計(jì)一個(gè)良好的文件系統(tǒng)，該方案易于操作也比較有效，但是其會(huì)帶來(lái)額外的數(shù)據(jù)擦除［2］;而采用存儲(chǔ)編碼(storage coding)通過(guò)對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行編碼，以控制存儲(chǔ)狀態(tài)轉(zhuǎn)移，從而提高存儲(chǔ)單元的重寫(xiě)次數(shù)，減小塊的擦除次數(shù)，如 floating codes［3］，buffer codes［4］， multidimensional Flash codes［5］， rank modulation［6］等，其同樣會(huì)帶來(lái)系統(tǒng)設(shè)計(jì)上的難度，目前難以應(yīng)用于實(shí)際系統(tǒng);另外一種方案就是結(jié)合糾錯(cuò)編碼、壞塊管理等方式把壞塊重新利用，從而提高Flash的生命周期［7］，本文主要考慮這種方式.

Flash中存在的另一個(gè)挑戰(zhàn)是存儲(chǔ)數(shù)據(jù)的可靠性，隨著擦除次數(shù)的增加，胞元的可靠性會(huì)降低，而且讀寫(xiě)電路的誤差以及外界環(huán)境引入的噪聲會(huì)使得存儲(chǔ)數(shù)據(jù)產(chǎn)生差錯(cuò)，存儲(chǔ)系統(tǒng)一般通過(guò)錯(cuò)誤校驗(yàn)與糾錯(cuò)(ECC，Error Checking and Correction)模塊來(lái)保證數(shù)據(jù)的可靠性，寫(xiě)入數(shù)據(jù)時(shí)，對(duì)存儲(chǔ)數(shù)據(jù)進(jìn)行編碼，讀取數(shù)據(jù)時(shí)檢測(cè)差錯(cuò)并進(jìn)行糾正，如漢明編碼、BCH碼、LDPC碼等.另外還有文獻(xiàn)考慮把ECC與存儲(chǔ)編碼聯(lián)合起來(lái)設(shè)計(jì)的編碼方案［8］，既提高系統(tǒng)可靠性，同時(shí)又提高系統(tǒng)的生命周期.

針對(duì)目前Flash中的可靠性與壽命兩個(gè)典型問(wèn)題提出了一種基于正交映射的編碼方法，研究分析發(fā)現(xiàn)，該方法不僅具有糾錯(cuò)和提高壽命的能力，還能夠提供分布式多用戶(hù)共享以及歷史數(shù)據(jù)恢復(fù)等實(shí)際應(yīng)用中的解決方案.

1 Flash存儲(chǔ)系統(tǒng)結(jié)構(gòu)框架

典型的Flash存儲(chǔ)系統(tǒng)結(jié)構(gòu)框架［2］如圖1所示，存儲(chǔ)技術(shù)設(shè)備層(MTD，Memory Technology Device)作為底層功能模塊提供對(duì)Flash存儲(chǔ)單元最基本的讀、寫(xiě)、擦除等操作;閃存映射層(FTL，F(xiàn)lash Translation Layer)作為上層文件系統(tǒng)與存儲(chǔ)單元之間的中間層，提供邏輯塊地址(LBA，Logic Block Address)到物理塊地址(PBA，Physic Block Address)之間的映射，不同的存儲(chǔ)系統(tǒng)根據(jù)實(shí)際應(yīng)用需求采用不同的映射方法，典型的映射方式有基于頁(yè)地址映射和基于塊地址映射［2］等;Flash控制器(Flash controller)是Flash存儲(chǔ)管理相當(dāng)重要的一個(gè)模塊，包括磨損均衡(WL，Wear Leveling)、垃圾回收(GC，Garbage Collection)、錯(cuò)誤檢驗(yàn)與糾正(ECC，Error Checking and Correction)、存儲(chǔ)編碼(SC，Storage Coding)、壞塊管理(BBM，Bad Block Management)等，這些模塊對(duì)Flash存儲(chǔ)系統(tǒng)的穩(wěn)定性與可靠性提供保障.本文在典型系統(tǒng)結(jié)構(gòu)的基礎(chǔ)之上，構(gòu)建了一個(gè)正交映射編碼模塊(OMCL，Orthogonal Mapping Coding Layer)，該模塊提供了一種基于正交映射的糾錯(cuò)編碼方法.

圖1 典型的Flash存儲(chǔ)系統(tǒng)結(jié)構(gòu)

2 基于正交映射的糾錯(cuò)編碼

2.1 糾錯(cuò)編碼原理

考慮一個(gè)Q元(N，M，d)碼C，其包含有M個(gè)碼字，每個(gè)碼字{q，q∈Ω}N長(zhǎng)度為N，取自于 Q元集合 Ω ={0，1，…，q－1}，任意兩個(gè)碼字之間的漢明距離為d.如果Q=2，則C是一個(gè)二進(jìn)制碼.編碼過(guò)程即通過(guò)一個(gè)編碼函數(shù)εC:M→C，把消息集合M中的M=|M|個(gè)消息一一映射為碼C中的M個(gè)碼字，即εC(m，m∈M).

由于環(huán)境噪聲、電路誤差以及Flash的物理特性，碼字中的某個(gè)或多個(gè)元素可能發(fā)生錯(cuò)誤或擦除，這里的錯(cuò)誤指的是碼字中某些不知位置的元素發(fā)生了改變，但仍屬于集合Ω，而擦除指的某些可知位置的元素變成了不可識(shí)別的符號(hào)(如Flash胞元由于電壓過(guò)沖超過(guò)了可識(shí)別的電壓范圍)，這里用“?”表示.根據(jù)編碼理論［9］，最小漢明距離為DH(，)=d的糾錯(cuò)碼可以糾正t個(gè)錯(cuò)誤，同時(shí)檢測(cè)e個(gè)錯(cuò)誤時(shí)，滿(mǎn)足如下不等式:

2.2 正交映射函數(shù)與序列

設(shè)函數(shù)集合F為

若滿(mǎn)足:

這里Ki為某個(gè)不等于0的常數(shù)，則稱(chēng)F在x∈［T1，T2］為正交函數(shù)集.如果在F之外，不存在另外一個(gè)非零函數(shù)與F中每一個(gè)函數(shù)都正交，則稱(chēng)F為完備正交函數(shù)集，如三角函數(shù)集、沃爾什(Walsh)函數(shù)集等.如圖2a所示為 t∈［0，T］的8階沃爾什函數(shù)集.

定義正交函數(shù)序列fi(n)為正交函數(shù)在其定義域內(nèi)的N個(gè)離散采樣序列，其滿(mǎn)足:

典型的正交函數(shù)序列有雷徳麥徹(Rademacher)序列，沃爾什(Walsh)序列等.如圖2b所示為采樣數(shù)N=23時(shí)的8階沃爾什序列，雷徳麥徹序列與沃爾什序列都能很方便地通過(guò)哈達(dá)瑪矩陣進(jìn)行快速生成、擴(kuò)展與相互轉(zhuǎn)化.

圖2 沃爾什正交函數(shù)集與序列

2.3 基于正交序列映射的糾錯(cuò)編碼

考慮消息序列集合M，本文提出了一種基于正交序列映射的糾錯(cuò)編碼(正交映射碼)C，其編碼函數(shù)εC:M→C把M中M=|M|個(gè)消息映射為正交函數(shù)序列集中的相應(yīng)序列;解碼函數(shù)用相應(yīng)的正交函數(shù)序列與信道輸出序列相乘即可恢復(fù)原始信息.考慮一個(gè)q元(N，M，t)正交映射碼C，其中每個(gè)碼字長(zhǎng)度為N，包含M個(gè)碼字，能糾正t個(gè)錯(cuò)誤.

例1 如圖3所示，為考慮二進(jìn)制消息序列，以沃爾什序列作為映射序列的(4，4，2)碼.

圖3 一個(gè)正交映射編碼示例

例1是一個(gè)簡(jiǎn)單的基于沃爾什序列的映射編碼，碼長(zhǎng)為4，存在4個(gè)碼字，可糾正2個(gè)錯(cuò)誤.由圖3可以看到，這個(gè)映射過(guò)程其實(shí)類(lèi)似于多用戶(hù)擴(kuò)頻通信中地址碼的分配［10］，但是由于Flash存儲(chǔ)結(jié)構(gòu)不同于無(wú)線信道，這個(gè)過(guò)程不能簡(jiǎn)單地直接應(yīng)用到Flash當(dāng)中.第3節(jié)介紹如何結(jié)合MLC NAND Flash的結(jié)構(gòu)特點(diǎn)，將這種正交映射機(jī)制應(yīng)用到Flash當(dāng)中，最后給出正交映射編碼在Flash中的應(yīng)用原理以及系統(tǒng)結(jié)構(gòu)框架，同時(shí)分析這種碼的糾錯(cuò)能力.

3 Flash中的正交映射編碼

3.1 Flash中的正交映射編碼原理與系統(tǒng)結(jié)構(gòu)

根據(jù)Flash中的存儲(chǔ)結(jié)構(gòu)以及操作特性，可以構(gòu)建正交映射編碼的系統(tǒng)結(jié)構(gòu)如圖4所示.圖中FTL模塊提供邏輯地址到物理地址的映射，正交映射編碼模塊提供基于正交序列映射的糾錯(cuò)編碼構(gòu)造方法.設(shè)每個(gè)塊由P個(gè)頁(yè)組成，可把P個(gè)頁(yè)分成M個(gè)超頁(yè)(super page)［11］，每個(gè)超頁(yè)由K個(gè)普通頁(yè)組成，同時(shí)為每個(gè)普通頁(yè)分配一個(gè)唯一的正交映射序列，當(dāng)有信息數(shù)據(jù)m1經(jīng)過(guò)FTL映射后需要存儲(chǔ)到Flash中的某個(gè)頁(yè)時(shí)，假設(shè)當(dāng)前超頁(yè)為空頁(yè)(free page，即可以直接寫(xiě)入數(shù)據(jù)的頁(yè))，則直接把m1通過(guò)正交映射編碼后的數(shù)據(jù)(記為c1)存入當(dāng)前超頁(yè)中的某個(gè)普通頁(yè)(記為p1)，然后當(dāng)有新數(shù)據(jù)或者更新數(shù)據(jù)m2到來(lái)，則把p1的數(shù)據(jù)c1放入緩沖區(qū)，再把m2進(jìn)行正交映射編碼后的數(shù)據(jù)c2與c1進(jìn)行疊加，存入下一個(gè)普通頁(yè)(記為 p2)，而把p1標(biāo)記為臟頁(yè)(dirty page，即不可寫(xiě)入數(shù)據(jù)，需要進(jìn)行擦除后才能繼續(xù)使用的頁(yè))，依此進(jìn)行操作.因此，在一個(gè)超頁(yè)中，只存在一個(gè)普通頁(yè)是有效頁(yè)(active page，即包含有效數(shù)據(jù)的頁(yè))，當(dāng)某個(gè)超頁(yè)沒(méi)有空頁(yè)時(shí)，需要對(duì)該超頁(yè)的數(shù)據(jù)進(jìn)行整理并轉(zhuǎn)存，這涉及磨損均衡與垃圾回收過(guò)程，這里不做討論.

圖4 正交映射編碼系統(tǒng)結(jié)構(gòu)

讀取數(shù)據(jù)時(shí)，把有效頁(yè)讀入緩存區(qū)中，然后根據(jù)相應(yīng)的正交映射序列恢復(fù)出原始數(shù)據(jù)，由于正交映射序列的正交性，最后總能根據(jù)每個(gè)數(shù)據(jù)分配的正交映射序列還原出相應(yīng)的原始數(shù)據(jù)，并能糾正部分錯(cuò)誤.本文提出的正交映射編碼是一個(gè)并行編碼的過(guò)程，可以利用并行結(jié)構(gòu)進(jìn)行處理，從而提高系統(tǒng)效率與處理速度.

例2 如圖5所示，考慮沃爾什序列作為正交映射編碼的映射序列，只考慮一個(gè)超頁(yè)，其包含4個(gè)普通頁(yè)，對(duì)應(yīng)4個(gè)沃爾什序列.本例簡(jiǎn)單地描述了正交映射編碼和解碼過(guò)程.

3.2 正交映射編碼的解碼與糾錯(cuò)能力

設(shè)正交映射序列長(zhǎng)度為N，每個(gè)超頁(yè)包含K個(gè)普通頁(yè)，對(duì)應(yīng)K個(gè)正交映射序列，由3.1節(jié)可知，當(dāng)前超頁(yè)中唯一有效頁(yè)存儲(chǔ)的數(shù)據(jù)為

這里1≤k≤K.

當(dāng)要恢復(fù)某一頁(yè)pi(1≤i≤k)的原始數(shù)據(jù)時(shí)，用該頁(yè)對(duì)應(yīng)的正交映射序列進(jìn)行如下解碼過(guò)程:

圖5 正交映射編解碼示例

對(duì)正交映射序列進(jìn)行歸一化即可恢復(fù)原始數(shù)據(jù).

設(shè)Flash中每個(gè)存儲(chǔ)單元具有πq個(gè)狀態(tài)，這里 πq={0，1，…，q－1}為一個(gè)狀態(tài)集合，考慮正交映射編碼(N，M，t)，若每個(gè)超頁(yè)包含K個(gè)普通頁(yè)，則M=K.從編碼過(guò)程可知，任意兩個(gè)碼之間的漢明距離為

因此根據(jù)編碼理論，其可以糾正(DH－1)/2個(gè)錯(cuò)誤.而且，在目前應(yīng)用的Flash中，πq的狀態(tài)數(shù)目(≤256)是有限的，這也決定了超頁(yè)的大小以及碼的個(gè)數(shù)，即M=K≤q/2.

4 正交映射編碼的典型應(yīng)用

4.1 分布式多用戶(hù)共享存儲(chǔ)

如第3節(jié)所述，考慮如圖4所示的正交映射編碼結(jié)構(gòu)，同樣采用超頁(yè)作為存儲(chǔ)單元.假設(shè)有K個(gè)用戶(hù)共享同一塊存儲(chǔ)空間，通過(guò)上層應(yīng)用程序以及文件系統(tǒng)的調(diào)用，需要多用戶(hù)進(jìn)行共享存儲(chǔ)時(shí)，在圖4的基礎(chǔ)上，只需修改正交映射編碼模塊，使其為每個(gè)用戶(hù)分配不同的正交映射序列fi(N)，0≤i≤K－1即可，其他的操作類(lèi)似于第3.1節(jié)，這樣，由于fi(N)之間的正交性，K個(gè)用戶(hù)可以對(duì)同一存儲(chǔ)空間進(jìn)行操作，而不會(huì)干擾其他用戶(hù)的數(shù)據(jù)，而且不需要進(jìn)行加密即可在一定程度上實(shí)現(xiàn)用戶(hù)彼此之間數(shù)據(jù)的安全性.隨著物聯(lián)網(wǎng)和云存儲(chǔ)的發(fā)展，該方法經(jīng)過(guò)擴(kuò)展可為分布式多用戶(hù)共享存儲(chǔ)提供一種解決方案.

4.2 歷史數(shù)據(jù)恢復(fù)

同樣基于第3節(jié)中圖4所示的編碼結(jié)構(gòu)，根據(jù)上層應(yīng)用程序的需求，只需修改正交映射模塊，當(dāng)每一次數(shù)據(jù)寫(xiě)入或者更新時(shí)，為每一個(gè)數(shù)據(jù)版本分配一個(gè)正交映射序列，即使對(duì)同一個(gè)邏輯地址區(qū)的數(shù)據(jù)進(jìn)行修改或者誤刪除，當(dāng)需要恢復(fù)到歷史數(shù)據(jù)版本時(shí)，不需要額外的工具或者操作，只需獲取到歷史數(shù)據(jù)版本對(duì)應(yīng)的正交序列，即可無(wú)差錯(cuò)的恢復(fù)出歷史數(shù)據(jù)，其基本的操作過(guò)程類(lèi)似于第3.1節(jié).當(dāng)然，由于超頁(yè)大小的限制，最多只能恢復(fù)出K層歷史數(shù)據(jù).

4.3 壞塊利用

在傳統(tǒng)的 Flash中，由于擦除次數(shù)的限制(MLC，一般為1萬(wàn)次;SLC為10萬(wàn)次)，工藝制作水平的約束，以及環(huán)境因素的影響，存儲(chǔ)胞元很容易發(fā)生毀壞，而在Flash應(yīng)用中，只要一個(gè)胞元發(fā)生毀壞，則整個(gè)存儲(chǔ)塊也不能使用，稱(chēng)之為壞塊，當(dāng)壞塊的比率達(dá)到一定水平時(shí)，則整個(gè)Flash也不能使用，一般通過(guò)壞塊管理模塊進(jìn)行壞塊查找和管理，壞塊的存在大大影響系統(tǒng)的性能與存儲(chǔ)數(shù)據(jù)安全.提高Flash的生命周期也是目前急需解決的一個(gè)實(shí)際問(wèn)題.

正交映射編碼可以從兩個(gè)層次解決壞塊問(wèn)題，第1個(gè)是胞元層次，即使某個(gè)胞元?dú)?，仍然可以利用這個(gè)塊進(jìn)行數(shù)據(jù)存儲(chǔ)，因?yàn)閴牡陌恢檬且阎?，所以在進(jìn)行讀寫(xiě)操作時(shí)，可以忽略這個(gè)位置的數(shù)據(jù)，而利用正交映射編碼的糾錯(cuò)能力進(jìn)行數(shù)據(jù)糾錯(cuò)即可;第2個(gè)是頁(yè)層次，可以根據(jù)編碼模塊與壞塊管理模塊之間的交互獲得壞頁(yè)的位置，從而在進(jìn)行正交映射編碼時(shí)，忽略這個(gè)頁(yè)的映射序列.這兩種方式都能有效地利用壞塊，從而提高Flash的生命周期.

5 結(jié)論

基于MLC NAND Flash的結(jié)構(gòu)特征與操作特性，提出了一種應(yīng)用于MLC NAND Flash存儲(chǔ)器的正交映射編碼方法，在保持整體結(jié)構(gòu)不變的基礎(chǔ)上，只需修改編碼模塊，即可實(shí)現(xiàn)錯(cuò)誤校驗(yàn)與糾正、多用戶(hù)共享存儲(chǔ)、歷史數(shù)據(jù)恢復(fù)、壞塊利用等多種實(shí)際應(yīng)用需求.該方法在提高系統(tǒng)可靠性與生命周期的同時(shí)，為分布式多用戶(hù)共享存儲(chǔ)以及數(shù)據(jù)恢復(fù)提供了一種解決方案.在本文工作的基礎(chǔ)上，只需對(duì)傳統(tǒng)控制器進(jìn)行簡(jiǎn)單的修改，即可開(kāi)發(fā)一個(gè)適用于多種應(yīng)用場(chǎng)景的閃存控制器，這有待未來(lái)更進(jìn)一步的研究.

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，F(xiàn)rance: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，F(xiàn)rance: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，F(xiàn)rance: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