呂小微

(西安電子科技大學(xué)電子工程學(xué)院，陜西西安 710071)

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

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

1 Hamming編碼

Hamming編碼計算簡單。廣泛用于NAND Flash的Hamming算法，通過計算塊上數(shù)據(jù)包得到2個ECC值。為計算ECC值，數(shù)據(jù)包中的比特數(shù)據(jù)要先進行分割，如1/2組、1/4組、1/8組等，直到其精度達(dá)到單個比特為止，以8 bit即1 Byte的數(shù)據(jù)包為例進行說明，如圖1所示。

圖1 8 bit數(shù)據(jù)包校驗的數(shù)據(jù)分割

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

圖2 計算奇偶ECC數(shù)據(jù)

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

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

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

圖3 發(fā)生錯誤數(shù)據(jù)包的ECC計算

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

圖4 判斷是否發(fā)生錯誤

對于1 bit錯誤的情況，出錯地址可通過將原有ECCo值和新ECCo值進行按位“異或”來識別獲取。通過圖5中的計算，結(jié)果為2，表明原數(shù)據(jù)第2 bit位出現(xiàn)了問題。該計算采用奇校驗數(shù)據(jù)ECCo，這是因為它們可以直接地反映出出錯比特的位置。

圖5 找出出錯比特位置

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

圖6 把出錯的數(shù)據(jù)恢復(fù)為原始數(shù)據(jù)

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

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

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

圖7 計算數(shù)據(jù)包的ECC

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

圖8 出錯數(shù)據(jù)包的校驗過程

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

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

3 實驗分析

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

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

表1 出錯狀態(tài)比特描述

實驗仿真環(huán)境為Altera Quartus II 7.0，編程語言為VHDL［3］。VHDL語言為硬件編程語言，具有并行處理的特點，而原程序中有大量的需要并行處理的異或操作，因此程序執(zhí)行效率高，非常有利于硬件實現(xiàn)。

圖9 1 bit錯誤的仿真結(jié)果

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

圖10 2 bit錯誤的仿真結(jié)果

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

圖11 無數(shù)據(jù)出錯的仿真結(jié)果

當(dāng)然，如果數(shù)據(jù)包沒有發(fā)生任何錯誤，也就是若讀出的數(shù)據(jù)與先前寫入的數(shù)據(jù)完全一致，ECC校驗也是能夠保證檢測出來的。如圖11所示，當(dāng)未發(fā)生任何錯誤時，errSTATUS為“00”，驗證了數(shù)據(jù)的一致性。此時，ERRloc無意義。

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

4 結(jié)束語

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

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

［1］ NAND Flash.Technical notes［M］.USA:NAND Conproation，2006.

［2］ NAND Flash.Data sheet［M］.USA:NAND Conproation，2008.

［3］ 曾繁泰，陳美金.VHDL程序設(shè)計［M］.2版.北京:清華大學(xué)出版社，2001.

［4］ 韋峰，盧再奇，劉偉.YAFFS2在嵌入式系統(tǒng)中的實現(xiàn)［J］.現(xiàn)代電子技術(shù)，2010(8):38－42，45.

［5］ 李璐，周海燕.一種含 BCH編解碼器的 SLC/MLCNAND Flash控制器的VLSI設(shè)計［J］.現(xiàn)代電子技術(shù)，2009(7):174－177.