基于FPGA的NAND Flash ECC校驗(yàn)

　　移動(dòng)產(chǎn)品應(yīng)用領(lǐng)域，NANDFlash設(shè)備已成為人們解決高密度固態(tài)存儲(chǔ)的專(zhuān)用方法。信息技術(shù)的飛速發(fā)展，人們對(duì)信息的需求量也越來(lái)越大。因此，大量數(shù)據(jù)在系統(tǒng)內(nèi)部以及網(wǎng)絡(luò)之間存儲(chǔ)和傳遞時(shí)，對(duì)數(shù)據(jù)進(jìn)行檢測(cè)并更正可能出現(xiàn)的錯(cuò)誤尤為重要。糾錯(cuò)碼ECC(ErrorCorrect-ionCode)滿(mǎn)足這一需求，其被稱(chēng)為ECC校驗(yàn)，是一種常用于NANDFlash讀寫(xiě)控制器的校驗(yàn)編碼。

　　ECC校驗(yàn)負(fù)責(zé)檢測(cè)錯(cuò)誤、維護(hù)ECC信息、更正由原數(shù)值改變了的單比特錯(cuò)誤。所有ECC的操作處理都可由一個(gè)ECC模塊來(lái)控制，其作為一種簡(jiǎn)單地存儲(chǔ)一映射接口，放置在NAND器件和處理器接口之間。該模塊一般包含Hamming編碼產(chǎn)生模塊和出錯(cuò)位置模塊，分別用于產(chǎn)生ECC校驗(yàn)碼和計(jì)算出錯(cuò)位置。

　　1Haremina編碼

　　Hamming編碼計(jì)算簡(jiǎn)單。廣泛用于NANDFlash的Hamming算法，通過(guò)計(jì)算塊上數(shù)據(jù)包得到2個(gè)ECC值。為計(jì)算ECC值，數(shù)據(jù)包中的比特?cái)?shù)據(jù)要先進(jìn)行分割，如1／2組、1／4組、1／8組等，直到其精度達(dá)到單個(gè)比特為止，以8bit即1Byte的數(shù)據(jù)包為例進(jìn)行說(shuō)明，如圖1所示。

　　該數(shù)據(jù)按圖1所示方式進(jìn)行比特分割，分別得到上方的偶校驗(yàn)值ECCe和下方的奇校驗(yàn)值ECCo。其中，1／2校驗(yàn)值經(jīng)“異或”操作構(gòu)成ECC校驗(yàn)的最高有效位，同理1／4校驗(yàn)值構(gòu)成ECC校驗(yàn)的次高有效位，最低有效位由具體到比特的校驗(yàn)值填補(bǔ)。圖2展示了兩個(gè)ECC校驗(yàn)值的計(jì)算過(guò)程。

　　即偶校驗(yàn)值ECCe為“101”，奇校驗(yàn)值ECCo為“010”。圖1所示為只有1Byte數(shù)據(jù)的數(shù)據(jù)包，更大的數(shù)據(jù)包需要更多的ECC值。事實(shí)上，每nbit的ECC數(shù)值可滿(mǎn)足2nbit數(shù)據(jù)包的校驗(yàn)要求。又由于這種Hamming碼算法要求一對(duì)ECC數(shù)據(jù)(奇偶)，所以總共要求2nbit的ECC校驗(yàn)數(shù)據(jù)來(lái)處理2nbit的數(shù)據(jù)包。

　　計(jì)算之后，原數(shù)據(jù)包和ECC數(shù)值都要寫(xiě)入NAND器件。稍后，原數(shù)據(jù)包將從NAND器件中讀取，此時(shí)ECC值將重新計(jì)算。如果新計(jì)算的ECC不同于先前編入NAND器件的ECC，那么表明數(shù)據(jù)在讀寫(xiě)過(guò)程中出錯(cuò)。

　　例如，原始數(shù)據(jù)01010001中有1個(gè)單一的比特出現(xiàn)錯(cuò)誤，出錯(cuò)后的數(shù)據(jù)是01010101。經(jīng)前面所示方法計(jì)算，從圖3中可以清楚地看到由于數(shù)據(jù)發(fā)生了變化，2個(gè)新的ECC數(shù)值已不同與原來(lái)的ECC值。

　　此時(shí)把所有4個(gè)ECC數(shù)值進(jìn)行按位“異或”，就可以判斷是否出現(xiàn)了1個(gè)單一比特的錯(cuò)誤或者是多比特的錯(cuò)誤。如果計(jì)算結(jié)果為全“0”，說(shuō)明數(shù)據(jù)在讀寫(xiě)過(guò)程中未發(fā)生變化。如果計(jì)算的結(jié)果為全“1”，表明發(fā)生了1bit錯(cuò)誤，如圖4所示。如果計(jì)算結(jié)果是除了全“0”和全“1”的任何一種情況，那么就是2bit出錯(cuò)的情況。2bit錯(cuò)誤總可以檢測(cè)到，然而，Hamming碼算法僅能夠保證更正單一比特的錯(cuò)誤。如果兩個(gè)或是更多的比特出錯(cuò)，那么就不能修改該出錯(cuò)的數(shù)據(jù)包，在這種情況下，Hamming算法就可能不能夠指示出已經(jīng)出現(xiàn)的錯(cuò)誤。不過(guò)，考慮到SLCNAND器件的比特錯(cuò)誤的情況，出現(xiàn)2、3bit錯(cuò)誤的可能性非常低。

　　對(duì)于1bit錯(cuò)誤的情況，出錯(cuò)地址可通過(guò)將原有ECCo值和新ECCo值進(jìn)行按位“異或”來(lái)識(shí)別獲取。通過(guò)圖5中的計(jì)算，結(jié)果為2，表明原數(shù)據(jù)第2bit位出現(xiàn)了問(wèn)題。該計(jì)算采用奇校驗(yàn)數(shù)據(jù)ECCo，這是因?yàn)樗鼈兛梢灾苯拥胤从吵龀鲥e(cuò)比特的位置。

　　找到出錯(cuò)比特后，只要通過(guò)翻轉(zhuǎn)它的狀態(tài)就可修復(fù)數(shù)據(jù)包，具體操作也就是將該位與“1”進(jìn)行異或操作，如圖6所示。

　　2擴(kuò)展數(shù)據(jù)包

　　在上述舉例中，校驗(yàn)1個(gè)8bit數(shù)據(jù)包需要6bit的ECC數(shù)據(jù)。在這種情況下，校驗(yàn)數(shù)據(jù)量達(dá)到原始數(shù)據(jù)包的數(shù)據(jù)量的75％，看上去并不令人滿(mǎn)意。然而，隨著數(shù)據(jù)包大小的增加，Hamming算法將表現(xiàn)得越來(lái)越有效率。由前面2nbit數(shù)據(jù)需要2nbitECC校驗(yàn)的關(guān)系推知，每增加一倍的數(shù)據(jù)要求兩個(gè)額外的ECC信息比特。這樣，當(dāng)數(shù)據(jù)增加到，比如512Byte時(shí)，僅產(chǎn)生24bit的ECC，此時(shí)用于校驗(yàn)的數(shù)據(jù)占原數(shù)據(jù)的比例降為0．06％，效率較高。下面，以1個(gè)8Byte的數(shù)據(jù)包為例說(shuō)明擴(kuò)展數(shù)據(jù)包的校驗(yàn)情況。

　　在這里，由于異或操作滿(mǎn)足交換律，用一種更為有效的方法進(jìn)行校驗(yàn)。如圖7所示，首先將該8Byte數(shù)據(jù)排為1個(gè)矩陣的形式，每行為1B-yte。分別計(jì)算每行各bit的異或結(jié)果記為字節(jié)校驗(yàn)碼(Byte-Wise)，計(jì)算每列各bit的異或結(jié)果記為比特校驗(yàn)碼(Bit-Wise)。接下來(lái)，將兩個(gè)校驗(yàn)碼分別按上述方法分割計(jì)算得到ECC校驗(yàn)碼，并將字節(jié)校驗(yàn)碼的ECC結(jié)果作為ECCe和ECCo的高有效位(MSB)、比特校驗(yàn)碼的ECC結(jié)果做為低有效位(LSB)進(jìn)行組合，最終得到8Byte數(shù)據(jù)包的ECC校驗(yàn)碼。

　　當(dāng)數(shù)據(jù)包發(fā)生錯(cuò)誤時(shí)，錯(cuò)誤檢測(cè)和更正所使用的方法與先前所描述的方法相似，這里仍以1bit錯(cuò)誤來(lái)說(shuō)明校驗(yàn)過(guò)程，具體如圖8所示。

　　經(jīng)步驟1～步驟4的計(jì)算，新的數(shù)據(jù)包存在錯(cuò)誤且出錯(cuò)位置為“110010”，由于前面將字節(jié)校驗(yàn)碼設(shè)為ECC值的高位，比特校驗(yàn)碼設(shè)為低位，因此，“110010”的高有效位表示出錯(cuò)的字節(jié)地址，低有效位代表出錯(cuò)的比特地址，即字節(jié)地址為6、比特地址為2的數(shù)據(jù)發(fā)生了錯(cuò)誤，與設(shè)定的錯(cuò)誤情況相符。此時(shí)，只需將該位的數(shù)據(jù)比特與“1”異或即可完成數(shù)據(jù)包的修正。

　　將8Byte數(shù)據(jù)包擴(kuò)展到512Byte數(shù)據(jù)包，雖然數(shù)據(jù)量大大增加，但僅添加了數(shù)據(jù)分割的情況，算法仍然一樣。計(jì)算所得奇偶ECC數(shù)據(jù)均為12bit長(zhǎng)，其中，3個(gè)低有效位代表bit地址(7～0)，9個(gè)高有效位代表512Byte的地址(255～0)。

　　3實(shí)驗(yàn)分析

　　本實(shí)驗(yàn)處理對(duì)像為256Byte的數(shù)據(jù)包，對(duì)其進(jìn)行ECC校驗(yàn)共生成22bit校驗(yàn)數(shù)據(jù)。為方便讀取，可以在末尾添加兩位，形成完整的3Byte校驗(yàn)數(shù)據(jù)。這3Byte共24bit，分成兩部分：6bit的比特校驗(yàn)和16bit的字節(jié)校驗(yàn)，多余的兩個(gè)比特置1并置于校驗(yàn)碼的最低位，在進(jìn)行異或操作時(shí)此兩比特忽略。

　　當(dāng)往NANDFlash頁(yè)中寫(xiě)人數(shù)據(jù)時(shí)，每256bit生成一個(gè)ECC校驗(yàn)，稱(chēng)之為原ECC校驗(yàn)和，并保存到頁(yè)的OOB數(shù)據(jù)區(qū)中；當(dāng)從NANDFlash中讀取數(shù)據(jù)的時(shí)，每256bit又生成一個(gè)新ECC校驗(yàn)，稱(chēng)之為新的ECC校驗(yàn)和。校驗(yàn)時(shí)，將從OOB區(qū)中讀出的原ECC校驗(yàn)和與新ECC校驗(yàn)和并執(zhí)行按位異或操作，若計(jì)算結(jié)果為全“0”，則表示不存在出錯(cuò)，并將出錯(cuò)狀態(tài)變量errSTATUS賦值為“00”；若結(jié)果為全“1”，表示出現(xiàn)1個(gè)比特錯(cuò)誤，將errSTATUS賦值為"01”并進(jìn)行糾正；除全“0”和全“1”外的其他情況將errSTATUS賦值為“10”表示出現(xiàn)了無(wú)法糾正的2bit錯(cuò)誤，如表1所示。

　　實(shí)驗(yàn)仿真環(huán)境為AlteraQuartusII7．0，編程語(yǔ)言為VHDL。VHDL語(yǔ)言為硬件編程語(yǔ)言，具有并行處理的特點(diǎn)，而原程序中有大量的需要并行處理的異或操作，因此程序執(zhí)行效率高，非常有利于硬件實(shí)現(xiàn)。

　　圖9給出了數(shù)據(jù)包發(fā)生1bit錯(cuò)誤的校驗(yàn)情況。其中，DATAin表示待讀取的數(shù)據(jù)，HammingCALC表示在寫(xiě)入NANDFlash頁(yè)時(shí)計(jì)算好的原始ECC，HAMMINGout表示后面在讀取DATAin數(shù)據(jù)時(shí)計(jì)算的新的ECC，errSTATUS為出錯(cuò)狀態(tài)，ERRIoc為計(jì)算所得出錯(cuò)的位置。為滿(mǎn)足1bit錯(cuò)誤的條件且易于觀(guān)察，將256Byte數(shù)據(jù)(0～255)的最后一個(gè)Byte由“11110110”變?yōu)?ldquo;11111110”，如圖9中陰影部分所示。此時(shí)，errSTATUS結(jié)果為"01”，表明程序檢測(cè)出了該1bit錯(cuò)誤，且ERRloc輸出為“111111111O11”，即出錯(cuò)位置為第255Byte的比特3發(fā)生了錯(cuò)誤。為糾正該錯(cuò)誤，此時(shí)，只要將該位置的比特取反輸出即可。

　　在原來(lái)1bit錯(cuò)誤的情況下，將其相鄰的第254bit的數(shù)據(jù)由“11110101”變?yōu)?ldquo;01110101”，如圖10陰影部分所示，整個(gè)數(shù)據(jù)包有2bit發(fā)生了變化。此時(shí)，errSTATUS結(jié)果顯示為“10”，即檢測(cè)出了有2bit錯(cuò)誤。但此時(shí)的ERRloe無(wú)效，不能表征出兩個(gè)出錯(cuò)的位置，也就是為什么ECC校驗(yàn)只能檢測(cè)出2bit錯(cuò)誤而不能對(duì)其進(jìn)行更正的原因。

　　當(dāng)然，如果數(shù)據(jù)包沒(méi)有發(fā)生任何錯(cuò)誤，也就是若讀出的數(shù)據(jù)與先前寫(xiě)入的數(shù)據(jù)完全一致，ECC校驗(yàn)也是能夠保證檢測(cè)出來(lái)的。如圖11所示，當(dāng)未發(fā)生任何錯(cuò)誤時(shí)，errSTATUS為“00”，驗(yàn)證了數(shù)據(jù)的一致性。此時(shí)，ERPloe無(wú)意義。

　　值得說(shuō)明的是，如果數(shù)據(jù)包發(fā)生的錯(cuò)誤多于2bit，該算法并不適宜。測(cè)定了更多比特(≥3)出錯(cuò)的情況，結(jié)果證明，errSTATUS的結(jié)果可能為“00”、“01”、“10”中的任何一個(gè)，也就是說(shuō)在這種情況下，該算法很可能出現(xiàn)誤檢。因此，在這里，可以得出與ECC校驗(yàn)原理相符的結(jié)論：ECC能夠保證糾正1bit錯(cuò)誤和檢測(cè)2bit錯(cuò)誤，但對(duì)于1bit以上的錯(cuò)誤無(wú)法糾正，對(duì)2bit以上的錯(cuò)誤不保證能檢測(cè)。

　　4結(jié)束語(yǔ)

　　本文將ECC校驗(yàn)算法通過(guò)硬件編程語(yǔ)言VHDL在AheraQuanusⅡ7．0開(kāi)發(fā)環(huán)境下進(jìn)行了后仿真測(cè)試，實(shí)現(xiàn)了NANDFlash的ECC校驗(yàn)功能。本程序可實(shí)現(xiàn)每256Byte數(shù)據(jù)生成3ByteECC校驗(yàn)數(shù)據(jù)，且通過(guò)與原始ECC數(shù)據(jù)對(duì)比，能夠保證檢測(cè)出1bit的錯(cuò)誤及其出錯(cuò)位置，進(jìn)一步結(jié)合對(duì)此錯(cuò)誤的糾正，可應(yīng)用于NANDFlash讀寫(xiě)控制器的FPGA設(shè)計(jì)，實(shí)現(xiàn)對(duì)數(shù)據(jù)的ECC校驗(yàn)，確保數(shù)據(jù)準(zhǔn)備有效地傳輸。經(jīng)硬件實(shí)驗(yàn)結(jié)果反饋，該算法硬件適應(yīng)性良好。

　　ECC是一種在NANDFlash處理中比較專(zhuān)用的校驗(yàn)，其原理簡(jiǎn)便、易于執(zhí)行、計(jì)算速度快并且數(shù)據(jù)量越大，其算法越有效。但這樣一個(gè)高效的算法仍存在缺陷，那就是其有限的糾錯(cuò)能力。本文也驗(yàn)證了其對(duì)于2bit以上錯(cuò)誤是無(wú)效的，盡管這種情況在Flash中發(fā)生的幾率很低，但就校驗(yàn)原理來(lái)說(shuō)，是否存在一種改進(jìn)的算法可用于多比特錯(cuò)誤的糾正還有待進(jìn)一步研究和驗(yàn)證。