基于Nand Flash的BCH校驗方法設計與實現*

焦新泉，武慧軍，單彥虎，秦菲

（中北大學電子測試技術國家重點實驗室，太原030051）

0 引 言

隨著目前武器系統和航天系統對發射或飛行過程中的環境參數數據量需求越來越大，NAND FLASH以其小體積、大容量、低成本、擦除次數多、保存壽命長等優點，被廣泛應用到固態記錄設備中［1］，但是由于其生產工藝方面的缺陷或受空間輻射等影響，在數據存儲和傳輸過程中位翻轉的幾率很大，優秀的數據校驗方法可以極大地提高數據存儲的可靠性。傳統的漢明校驗方法硬件實現占用的邏輯資源小，并可以提供1bit的糾錯能力，對于SLC類型Nand Flash漢明校驗法是一種性價比非常高的糾錯方法，但是隨著目前MLC類型Nand Flash的發展和SLC類型的Nand Flash容量的提高，漢明校驗仍然存在諸多缺陷，比如相對較差的編碼效率，編碼后的信息碼總量較大，對校驗位數目要求不合理，且糾錯位數有限等嚴重影響了數據存儲的可靠性。

為此國內外研究學者提出了很多改進校驗方法，其中有代表性的有LPDC、RS和BCH校驗算法。LPDC編碼是一種逼近Shannon理論極限優異性能的糾錯碼，但是由于構造難、分析難、實現難很長時間內未能得到很好的發展；RS碼適用于連續數據位糾錯（如大數據塊或整個硬盤失效時的數據恢復）；與之相比BCH碼更適用于Nand Flash的隨機錯誤糾錯，且校驗碼更短，存儲利用率更高，自1959年提出以來，因其在短碼糾錯方面的優異表現被得到大力發展。其中較為先進的且具有代表性的算法有文獻［2］提出的一種基于5bit糾錯的非流水BCH編／譯碼器結構，其采用特殊指令的微控制器實現，缺點是硬件開銷大且譯碼時間長；文獻［3］設計了一種帶流水結構的4bit糾錯的BCH編／譯碼器，由于采用按頁預取的譯碼方式，較前一種結構譯碼速度提升了很多，但譯碼時間依然很長；文獻［4］提出一種可配置的多比特糾錯控制器結構，可選用不同的糾錯算法，提升了譯碼效率，但是實現多種算法帶來了巨大的硬件開銷。本文設計了一種（4200，4096，8）的BCH碼ECC校驗方法，減少了編碼器中線性反饋移位寄存器電路的高扇出瓶頸，譯碼器方面對伴隨式求解模塊和錢氏搜索模塊采用并行處理方式，節省了8倍的譯碼時間，采用二級流水線分塊譯碼極大地提高了譯碼效率，是一種可靠高效的校驗方法。

1 Flash閃存結構

數據校驗的編譯碼需要對FLASH閃存結構有深入的研究，它的內部結構決定了碼元的長度及糾錯的位數，NAND Flash是以頁為最小存儲單元的存儲陣列，傳統閃存的頁面大小一般為512 B目前閃存的容量以經擴展到4 KB甚至8 KB（都為512 B的倍數）本文以某公司的MT29F128G08AJAAAWP為例，其單片存儲容量為16 GB，每頁包含8KB的數據存儲區和448 B的數據備用區，其內部的組織形式［5］如圖1所示。所以以512 B為一組數據編碼可同時滿足不同頁容量NAND Flash的ECC需求。

圖1 Nand Flash內部結構Fig.1 Internal structure of the Nand Flash memory

2 ECC校驗方法

2.1 BCH并行編碼

BCH編碼是一種線性分組碼，其結構是建立在有限域多項式基礎上的，特別是將多項式特性和糾錯能力聯系起來，使得這一類碼具有較強的糾錯能力。BCH碼能針對隨機發生的錯誤位進行糾錯，特別適合硬件實現，該編碼方式極大的提高了數據的可靠性。

在有限域 GF（2m）中，滿足 n＝k+mt，n≤2m-1。其中n為碼長，k為信息位長度，t為可糾錯位長。GF（2m）域中糾錯能力為 t的生成多項式為 g（x）＝m1（x）m3（x）…m2t-1（x），其中 mi（x）為本原元 ai的最小多項式，BCH編碼是由信息位計算得到校驗和，信息位和校驗和共同組成一組BCH碼，其碼型格式如圖2所示。

設k位信息碼多項式為m（x）＝mk-1xk-1+…mk-2xk-2+…+m1x1+m0。

n位BCH碼多項式為c（x）＝cn-1xn-1+cn-2xn-2+… +c1x1+c0c（x）＝m（x）xn-k+Rem（m（x）xnk）g（x）其中 Rem（m（x）xn-k）g（x）為 m（x）xn-k對g（x）取余。

圖2 BCH碼型格式Fig.2 BCH code format

根據多項式除法電路中線性反饋寄存器原理，可以得到T+1時刻和T時刻移位寄存器中的數據與T+1時刻信息碼碼元輸入之間的關系［6］。

矩陣表示為：

上述關系可簡化成R（T+1）＝F×（R（T）+m（T+1）），然后擴展為單字節并行輸入后寄存器R（T+8）和當前R（T）和8位信息數據之間的關系為R（T+8）＝F8×R（T）+F8×m（T+1）+F7×m（T+2）+…+F×m（T+8）。

基于MT29F128G08AJAAAWP型NAND Flash本文設計一種（4 200，4 096，8）的校驗碼，m＝13，k＝4 096，t＝8該碼是（8 191，8 087，8）的縮短碼，其本原多項式m1（x）＝x13+x4+x3+x+1。利用 Matlab迭代運算求得其生成多項式g（x）＝x104+x100+x98+x96+x95+x94+x93+x92+x91+x88+x84+x82+x79+x78+x77+x70+x69+x68+x67+x65+x64+x59+x58+x52+x49+x48+x47+x42+x41+x40+x38+x32+x31+x30+x26+x24+x23+x22+x18+x15+x14+x13+x12+x11+x9+x8+x5+x+1。

按字節編碼的關鍵組件如圖3所示，最終移位寄存器中的值為生成的BCH校驗碼。

圖3 字節編碼關鍵組件Fig.3 Key component of byte coding

2.2 BCH譯碼方法

譯碼對數據的讀取速度至關重要，設計高吞吐率的譯碼器非常關鍵［7］。譯碼過程通常分為伴隨式求解、錯誤位置多項式求解、錢氏搜索電路設計。

（1）伴隨式求解

設發送碼字的多項式c（x）＝cn-1xn-1+cn-2xn-2+…+c1x1+c0

接收碼字的多項式r（x）＝rn-1xn-1+rn-2xn-2+…+r1x1+r0

則 r（x）＝c（x）+e（x），其中 e（x）為錯誤多項式。

BCH碼的生成多項式g（x）必定含有2t個連續冪次的根，設 a、a2、…、a2t是 GF（2m）有限域上生成多項式 g（x）的根，伴隨式多項式 Si＝r（ai），若 Si＝0則接收碼無比特錯誤，否則：

Si＝r（ai）＝rn-1（ai）n-1+rn-2（ai）n-2+...+r1（ai）1+r0＝（r0（ai）0+r1（ai）1+… +r7（ai）7）（ai）0+（r8（ai）0+r9（ai）1+… +r15（ai）7）（ai）8+...+（rn-8（ai）0+rn-7（ai）1+...+rn-1（ai）7）（ai）n-8并行伴隨式求解電路如圖4所示。

圖4 伴隨式求解電路Fig.4 Adjoint solution circuit

（2）錯誤位置多項式求解

由上述求解可知伴隨式 Si＝r（ai）＝c（ai）+e（ai）＝e（ai）＝e1（ai）1+e2（ai）2+… +et（ai）t，令xt＝at，表示錯誤位置，則 Si＝e1（x1）i+e2（x2）i+…+et（xt）i，該式計算 t個未知數的 2t個方程比較困難，因此引入錯誤多項式 σ（x）＝（1+e1x1x）（1+e2x2x）…（1+etxtx）＝1+σ1x1+σ2x2+… +σtxt。

可知：

無求逆BM算法，是在經典BM算法的基礎上，簡化迭代次數，替代逆元求解運算，簡化后的無求逆BM算法迭代運算與傳統的BM迭代算法［8］類似，是目前應用最多且最高效的的求解算法。

認為w（x）是求解錯誤值多項式σ（x）的關鍵方程。

錯誤位置多項式系數的硬件求解電路如圖5所示，起始是 R寄存器中的值為（S1，0，0，0，…0），σ和k寄存器中的值為（1，0，0...0），dq的值設為 1，每個時鐘并行輸入兩位Si，放入R0，R1中，并將R寄存器中的內容隔級右移位，達到迭代次數后，σ寄存器中的內容即是錯誤位置多項式的系數。

圖5 錯誤位置多項式系數求解電路Fig.5 Error position polynomial coefficient solution circuit

（3）錢氏搜索電路設計

錢氏搜索電路的主體思想是窮舉法求錯誤位置多項式 σ（x）的根，設 an-1的倒數是 σ（x）的根，則σ（a-（n-1））＝0＝1+σ1a+σ2a2+… +σvav，譯碼器通過計算 σ1a，σ2a2，…，σvav，將他們相加求和，結果若為-1，則接收碼元中錯誤位置的那一位發生錯誤，通過對接收碼元的每一位進行驗證來查找錯誤位置，最終求得錯誤多項式e（x）。

本文設計為（4 200，4 096，8）的碼元，該碼元為（8 191，8 087，8）的縮短碼，在縮短碼前添加3 991個0，為縮短搜索范圍，搜索只對有效數據進行搜索［9］。搜索起點設置為a3991，為優化搜索速率采用8 bit并行搜索，搜索時間只需525個時鐘周期。對Chien搜索電路的寄存器進行初始化，由搜索起點設置為3 991，當i的冪的數值大于 8 191，i的值變為 i對8 191取余，所以它的初始值分別為 σ1a3191，σ2a7982，…，σ8a7355，搜索電路如圖6所示。

圖6 錢氏搜索電路Fig.6 Chien search circuit

3 ECC校驗過程及FPGA驗證

BCH編譯碼的最終目的是對flash讀寫操作過程中進行錯誤位的糾正。

數據校驗模塊功能框圖如圖7所示。由四個部分組成，分別為主控模塊、BCH編碼模塊、BCH譯碼模塊、糾錯模塊。在對flash進行讀操作時，主控模塊使能譯碼模塊，譯碼模塊中的伴隨式求解模塊判斷讀出的數據是否有錯，如果檢查出錯，則通過錯誤位置多項式求解模塊、和錢氏搜索模塊找到位翻轉的位置，最后到糾錯模塊進行糾錯。

圖7 ECC校驗模塊Fig.7 Verification module of ECC

當向Flash存儲數據時，每512 B數據字節產生的13 B校驗碼依次存放。根據Nand Flash的結構特點，備用區通常不用來存放數據信息，但它的內部結構與數據存儲一樣，這樣可以將一頁劃分為8塊，編碼過程可以理解為運算后對Flash的寫入過程，計算主要是邏輯運算和移位運算這里不再贅述，在讀取過程中可以連續讀出525 B字節的信息數據，然后進行譯碼，這樣即避免了讀地址之間來回切換，這種分塊譯碼的方法保證了各塊之間的相互獨立，對他們的讀取和譯碼可采用流水線的方式來操作如圖8所示。通過計算采用流水線結構的譯碼過程可以縮減譯碼時間，極大的提升了整個譯碼的效率，譯碼流程如圖9所示。

圖8 流水線結構Fig.8 Pipeline structure

此次驗證以某公司XC6SLX150芯片為硬件平臺，用每組512 B自加數（數據從00～FB，兩個字節的幀計數，EB90為幀尾，每兩幀組成一組信息碼）進行數據驗證［10］，使讀取數據”8F”H時出現錯誤，將第5位和第4位出現位翻轉，讀出的數據變為”BF”H，用傳統漢明碼校驗仿真波形如圖10所示，ecc_old_code為存儲一組數據時產生的校驗碼，ecc_new_code為讀取一組數據時產生的校驗碼，若讀取數據沒有錯誤，兩組校驗碼的值應完全一樣。簡化運算后為當 ECC_result（ECC_result＝ECC_old_result xor ECC_new_result）為全‘0’時證明存入的數據和讀出的數據無錯誤，若為全‘1’，證明發生了一位錯誤，其他值為兩位錯誤，對于兩位以上的錯誤則不能檢測。由仿真結果可以看出 ecc_result＝”011 000 000 000”，證明出現兩位錯誤，但漢明校驗的算法并不能確定錯誤位置，因此不能對其糾錯。圖11為應用BCH校驗的仿真，data_in為Nand Flash陣列讀出來的數據，data_final為糾錯模塊輸出的數據，當數據字節的sum1為全‘0’則代表第7位發生了錯誤，驗證實驗為從“8F”H翻轉成“BF”H，第5位和第4位出現翻轉，因此sum4和sum3變為了全‘0’。大數據量驗證后用上位機讀取數據并解包校驗，結果如圖12所示。

圖9 譯碼流程Fig.9 Decoding process

圖10 數據寫入和讀出仿真Fig.10 Simulation about data read

圖11 BCH譯碼Fig.11 Decoding of BCH

圖12 測試結果Fig.12 Test result

4 結束語

本文論述了一種適用于NAND閃存控制器的ECC校驗方法，該方法具有隨機糾錯多位的能力。該校驗結構采用模塊化的設計思路，利用并行編碼譯碼方法，充分考慮到了速度與面積的折中，可以實現對當前主流NAND閃存的基本操作，并保證在預定糾錯能力范圍內的可靠存取，目前該方法已成功應用于某航天數據記錄設備，經試驗證明該校驗方法可以實現數據的可靠存儲與回收，具有一定的參考價值。