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

（中北大學(xué)電子測(cè)試技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，太原030051）

0 引 言

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

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

1 Flash閃存結(jié)構(gòu)

數(shù)據(jù)校驗(yàn)的編譯碼需要對(duì)FLASH閃存結(jié)構(gòu)有深入的研究，它的內(nèi)部結(jié)構(gòu)決定了碼元的長(zhǎng)度及糾錯(cuò)的位數(shù)，NAND Flash是以頁(yè)為最小存儲(chǔ)單元的存儲(chǔ)陣列，傳統(tǒng)閃存的頁(yè)面大小一般為512 B目前閃存的容量以經(jīng)擴(kuò)展到4 KB甚至8 KB（都為512 B的倍數(shù)）本文以某公司的MT29F128G08AJAAAWP為例，其單片存儲(chǔ)容量為16 GB，每頁(yè)包含8KB的數(shù)據(jù)存儲(chǔ)區(qū)和448 B的數(shù)據(jù)備用區(qū)，其內(nèi)部的組織形式［5］如圖1所示。所以以512 B為一組數(shù)據(jù)編碼可同時(shí)滿足不同頁(yè)容量NAND Flash的ECC需求。

圖1 Nand Flash內(nèi)部結(jié)構(gòu)Fig.1 Internal structure of the Nand Flash memory

2 ECC校驗(yàn)方法

2.1 BCH并行編碼

BCH編碼是一種線性分組碼，其結(jié)構(gòu)是建立在有限域多項(xiàng)式基礎(chǔ)上的，特別是將多項(xiàng)式特性和糾錯(cuò)能力聯(lián)系起來(lái)，使得這一類(lèi)碼具有較強(qiáng)的糾錯(cuò)能力。BCH碼能針對(duì)隨機(jī)發(fā)生的錯(cuò)誤位進(jìn)行糾錯(cuò)，特別適合硬件實(shí)現(xiàn)，該編碼方式極大的提高了數(shù)據(jù)的可靠性。

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

設(shè)k位信息碼多項(xiàng)式為m（x）＝mk-1xk-1+…mk-2xk-2+…+m1x1+m0。

n位BCH碼多項(xiàng)式為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對(duì)g（x）取余。

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

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

矩陣表示為：

上述關(guān)系可簡(jiǎn)化成R（T+1）＝F×（R（T）+m（T+1）），然后擴(kuò)展為單字節(jié)并行輸入后寄存器R（T+8）和當(dāng)前R（T）和8位信息數(shù)據(jù)之間的關(guān)系為R（T+8）＝F8×R（T）+F8×m（T+1）+F7×m（T+2）+…+F×m（T+8）。

基于MT29F128G08AJAAAWP型NAND Flash本文設(shè)計(jì)一種（4 200，4 096，8）的校驗(yàn)碼，m＝13，k＝4 096，t＝8該碼是（8 191，8 087，8）的縮短碼，其本原多項(xiàng)式m1（x）＝x13+x4+x3+x+1。利用 Matlab迭代運(yùn)算求得其生成多項(xiàng)式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。

按字節(jié)編碼的關(guān)鍵組件如圖3所示，最終移位寄存器中的值為生成的BCH校驗(yàn)碼。

圖3 字節(jié)編碼關(guān)鍵組件Fig.3 Key component of byte coding

2.2 BCH譯碼方法

譯碼對(duì)數(shù)據(jù)的讀取速度至關(guān)重要，設(shè)計(jì)高吞吐率的譯碼器非常關(guān)鍵［7］。譯碼過(guò)程通常分為伴隨式求解、錯(cuò)誤位置多項(xiàng)式求解、錢(qián)氏搜索電路設(shè)計(jì)。

（1）伴隨式求解

設(shè)發(fā)送碼字的多項(xiàng)式c（x）＝cn-1xn-1+cn-2xn-2+…+c1x1+c0

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

則 r（x）＝c（x）+e（x），其中 e（x）為錯(cuò)誤多項(xiàng)式。

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

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）錯(cuò)誤位置多項(xiàng)式求解

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

可知：

無(wú)求逆BM算法，是在經(jīng)典BM算法的基礎(chǔ)上，簡(jiǎn)化迭代次數(shù)，替代逆元求解運(yùn)算，簡(jiǎn)化后的無(wú)求逆BM算法迭代運(yùn)算與傳統(tǒng)的BM迭代算法［8］類(lèi)似，是目前應(yīng)用最多且最高效的的求解算法。

認(rèn)為w（x）是求解錯(cuò)誤值多項(xiàng)式σ（x）的關(guān)鍵方程。

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

圖5 錯(cuò)誤位置多項(xiàng)式系數(shù)求解電路Fig.5 Error position polynomial coefficient solution circuit

（3）錢(qián)氏搜索電路設(shè)計(jì)

錢(qián)氏搜索電路的主體思想是窮舉法求錯(cuò)誤位置多項(xiàng)式 σ（x）的根，設(shè) an-1的倒數(shù)是 σ（x）的根，則σ（a-（n-1））＝0＝1+σ1a+σ2a2+… +σvav，譯碼器通過(guò)計(jì)算 σ1a，σ2a2，…，σvav，將他們相加求和，結(jié)果若為-1，則接收碼元中錯(cuò)誤位置的那一位發(fā)生錯(cuò)誤，通過(guò)對(duì)接收碼元的每一位進(jìn)行驗(yàn)證來(lái)查找錯(cuò)誤位置，最終求得錯(cuò)誤多項(xiàng)式e（x）。

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

圖6 錢(qián)氏搜索電路Fig.6 Chien search circuit

3 ECC校驗(yàn)過(guò)程及FPGA驗(yàn)證

BCH編譯碼的最終目的是對(duì)flash讀寫(xiě)操作過(guò)程中進(jìn)行錯(cuò)誤位的糾正。

數(shù)據(jù)校驗(yàn)?zāi)K功能框圖如圖7所示。由四個(gè)部分組成，分別為主控模塊、BCH編碼模塊、BCH譯碼模塊、糾錯(cuò)模塊。在對(duì)flash進(jìn)行讀操作時(shí)，主控模塊使能譯碼模塊，譯碼模塊中的伴隨式求解模塊判斷讀出的數(shù)據(jù)是否有錯(cuò)，如果檢查出錯(cuò)，則通過(guò)錯(cuò)誤位置多項(xiàng)式求解模塊、和錢(qián)氏搜索模塊找到位翻轉(zhuǎn)的位置，最后到糾錯(cuò)模塊進(jìn)行糾錯(cuò)。

圖7 ECC校驗(yàn)?zāi)KFig.7 Verification module of ECC

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

圖8 流水線結(jié)構(gòu)Fig.8 Pipeline structure

此次驗(yàn)證以某公司XC6SLX150芯片為硬件平臺(tái)，用每組512 B自加數(shù)（數(shù)據(jù)從00～FB，兩個(gè)字節(jié)的幀計(jì)數(shù)，EB90為幀尾，每?jī)蓭M成一組信息碼）進(jìn)行數(shù)據(jù)驗(yàn)證［10］，使讀取數(shù)據(jù)”8F”H時(shí)出現(xiàn)錯(cuò)誤，將第5位和第4位出現(xiàn)位翻轉(zhuǎn)，讀出的數(shù)據(jù)變?yōu)椤盉F”H，用傳統(tǒng)漢明碼校驗(yàn)仿真波形如圖10所示，ecc_old_code為存儲(chǔ)一組數(shù)據(jù)時(shí)產(chǎn)生的校驗(yàn)碼，ecc_new_code為讀取一組數(shù)據(jù)時(shí)產(chǎn)生的校驗(yàn)碼，若讀取數(shù)據(jù)沒(méi)有錯(cuò)誤，兩組校驗(yàn)碼的值應(yīng)完全一樣。簡(jiǎn)化運(yùn)算后為當(dāng) ECC_result（ECC_result＝ECC_old_result xor ECC_new_result）為全‘0’時(shí)證明存入的數(shù)據(jù)和讀出的數(shù)據(jù)無(wú)錯(cuò)誤，若為全‘1’，證明發(fā)生了一位錯(cuò)誤，其他值為兩位錯(cuò)誤，對(duì)于兩位以上的錯(cuò)誤則不能檢測(cè)。由仿真結(jié)果可以看出 ecc_result＝”011 000 000 000”，證明出現(xiàn)兩位錯(cuò)誤，但漢明校驗(yàn)的算法并不能確定錯(cuò)誤位置，因此不能對(duì)其糾錯(cuò)。圖11為應(yīng)用BCH校驗(yàn)的仿真，data_in為Nand Flash陣列讀出來(lái)的數(shù)據(jù)，data_final為糾錯(cuò)模塊輸出的數(shù)據(jù)，當(dāng)數(shù)據(jù)字節(jié)的sum1為全‘0’則代表第7位發(fā)生了錯(cuò)誤，驗(yàn)證實(shí)驗(yàn)為從“8F”H翻轉(zhuǎn)成“BF”H，第5位和第4位出現(xiàn)翻轉(zhuǎn)，因此sum4和sum3變?yōu)榱巳?’。大數(shù)據(jù)量驗(yàn)證后用上位機(jī)讀取數(shù)據(jù)并解包校驗(yàn)，結(jié)果如圖12所示。

圖9 譯碼流程Fig.9 Decoding process

圖10 數(shù)據(jù)寫(xiě)入和讀出仿真Fig.10 Simulation about data read

圖11 BCH譯碼Fig.11 Decoding of BCH

圖12 測(cè)試結(jié)果Fig.12 Test result

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

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