劉 洋， 李 杰， 李金強(qiáng)， 李炳臻， 趙計賀

(1.中北大學(xué)儀器科學(xué)與動態(tài)測試教育部重點(diǎn)實(shí)驗(yàn)室， 太原， 030051； 2.山東航天電子技術(shù)研究所， 山東煙臺， 264000)

NAND FLASH在每次重新寫入前都需要區(qū)段擦除，隨著擦除次數(shù)的增多，誤碼率隨之升高。因此為了保證數(shù)據(jù)的準(zhǔn)確性，選擇一種性能良好的糾錯算法至關(guān)重要。針對具有高誤碼率的存儲器，采用能糾正一位錯誤的漢明碼已經(jīng)不能滿足需求[1]。BCH和LDPC是2種被廣泛使用的具有出色糾錯能力的算法[2-3]。但LDPC具有譯碼復(fù)雜度高的缺點(diǎn)，而且每次譯碼需要多次讀取[4]。BCH算法結(jié)構(gòu)相對簡單，不僅可以完成寫入數(shù)據(jù)時的糾錯，還能夠?qū)ψx取干擾和數(shù)據(jù)保持過程中電荷泄露造成的隨機(jī)位錯進(jìn)行糾正，且每次譯碼只需讀取一次，但LDPC和BCH都有較長的校驗(yàn)位開銷。對于任意的正整數(shù)m≥3和t<2m-1，一個碼長為2m-1的二元BCH碼，在整個碼字跨度上糾正t位錯誤，那么需要有mt個校驗(yàn)位，即糾錯能力每增加一位就需要多使用m個校驗(yàn)位。針對已經(jīng)因?yàn)椴翆懘螖?shù)過多導(dǎo)致誤碼率很高的情況，如果單獨(dú)使用BCH糾錯算法，其校驗(yàn)位顯然會占用非常多的空間。Reset-Check-Reverse-Flag，RCRF)是一種只需在每段信息位前添加一個標(biāo)志位就可以糾正一個或多個復(fù)位錯誤的算法[5]，但是并不能糾正隨機(jī)錯誤。現(xiàn)有文獻(xiàn)在提出此種算法后應(yīng)用其糾正新興存儲NRAM的“復(fù)位”錯誤(復(fù)位后存儲單元的信息為0)，并提議與BCH結(jié)合，在使用相同校驗(yàn)位數(shù)(標(biāo)志位+BCH校驗(yàn)位)的情況下和單獨(dú)應(yīng)用BCH進(jìn)行對比分析，得出組合方案具有更好糾錯效果的結(jié)論，但文獻(xiàn)中并未給出BCH部分的實(shí)現(xiàn)方法和總體方案具體的硬件驗(yàn)證過程。

本文在其基礎(chǔ)上提出將RCRF算法與BCH算法結(jié)合，對應(yīng)用更廣泛的NAND FLASH中的位錯進(jìn)行糾正。與新興存儲不同的是，NAND FLASH不存在復(fù)位錯誤，而是存在一種擦除錯誤(擦除后的存儲單元信息為1，如果出錯則為0)，所以初步采用RCRF的思想對部分初始擦除錯誤進(jìn)行糾正，然后級聯(lián)BCH糾正剩余的位錯，同時從實(shí)際硬件實(shí)現(xiàn)角度出發(fā)，重點(diǎn)提出了BCH的改進(jìn)方法。對于設(shè)計的2 048位信息位中識別并糾正3位錯誤的BCH碼，只需添加一位標(biāo)志位就可以達(dá)到在整個碼字區(qū)間糾正3位及以上位錯的效果。圖1展示了傳統(tǒng)單獨(dú)使用BCH方法與新方案RCRF+BCH的碼字分布示意圖。

本文詳細(xì)闡述了該高速并行算法的編譯碼原理和執(zhí)行步驟，使用消耗更少硬件資源的無求逆的iBM關(guān)鍵方程求解算法，然后提出通過推導(dǎo)列出錯誤位置多項(xiàng)式不同路徑的幾種確定形式，進(jìn)一步提高了譯碼速度。最終在FPGA平臺硬件實(shí)現(xiàn)并仿真驗(yàn)證了此方案的有效性。

圖1 BCH與BCH+RCRF碼字分布示意圖

1 RCRF編解碼

1.1 RCRF編碼

NAND FLASH在每次重新寫入前需要區(qū)段擦除，擦除過的BLOCK所有的存儲單元存儲的值都為1，如果此位發(fā)生錯誤則為0。定義一幀數(shù)據(jù)由1位標(biāo)志位和2 048位數(shù)據(jù)位構(gòu)成。如圖2所示，RCRF編碼過程可以用簡單的4部分來描述[5-6]。首先讀取擦除過后的NAND FLASH中的一幀內(nèi)容；然后判斷其中是否有位錯發(fā)生，如果從右數(shù)的位置a處發(fā)生位錯，則識別準(zhǔn)備寫入的2 048位信息位對應(yīng)位置a處的值是否為1：如果是1，且因?yàn)椴脸≡斐刹荒苤匦聦懭?，可以將標(biāo)志位和準(zhǔn)備寫入的信息位全部翻轉(zhuǎn)并組合，使a處的值轉(zhuǎn)變?yōu)?，與幀數(shù)據(jù)位錯的值一致，保證翻轉(zhuǎn)后的2 049位數(shù)據(jù)寫入NAND FLASH時是正確的，同時標(biāo)志位從1變?yōu)?指示信息位已經(jīng)被翻轉(zhuǎn)，方便解碼時確認(rèn)；如果信息位a處的值是0，則相當(dāng)于不構(gòu)成位錯，可以直接送入BCH編碼器。

圖2 RCRF編碼過程

1.2 RCRF解碼

圖3提供了RCRF解碼的流程。在BCH解碼器糾正了因其他噪聲影響造成的位翻轉(zhuǎn)后，此時標(biāo)志位如果為0，則翻轉(zhuǎn)2 048位數(shù)據(jù)位即可獲得正確的信息位，否則直接輸出。值得注意的是即使標(biāo)志位翻轉(zhuǎn)，同樣可以依靠BCH完成糾正。圖4展示了一種RCRF可以糾正一位擦除錯誤的情況以及RCRF+BCH糾錯方案的整體流程。

圖3 RCRF解碼過程

圖4 RCRF編解碼糾正一位錯誤(RCRF+BCH糾錯方案的整體流程)

理論上RCRF不僅具有糾正一位擦除錯誤的能力，還可以應(yīng)對發(fā)生多位錯誤的情況[5]。以存在2位擦除錯誤為例進(jìn)行分析，即該段數(shù)據(jù)包含任意2個位置的值都為0，用00來表示。此時亟待寫入的信息位中對應(yīng)的值存在4種可能性，分別用00，11，01和10這4個圖樣來表示。信息位圖樣為00時等于沒有位錯發(fā)生，圖樣為11時與上述原理相同，方便執(zhí)行RCRF編碼操作并在解碼時翻轉(zhuǎn)，即可完成全部位錯的糾正過程，標(biāo)志位可以根據(jù)圖5的電路產(chǎn)生。針對信息位圖樣為01和10的情況，RCRF編解碼對數(shù)據(jù)恢復(fù)沒有效果，因?yàn)榉D(zhuǎn)后也不能完全寫入正確的數(shù)據(jù)。但是即使判斷存在擦除錯誤，標(biāo)志位與信息位翻轉(zhuǎn)，也可以應(yīng)用BCH對剩余位錯進(jìn)行檢測并糾正。所以實(shí)際在相應(yīng)的情況下RCRF可以糾正多位錯誤。

圖5 標(biāo)志位生成電路

2 BCH編解碼

2.1 BCH編碼

在一個(n,k,t)BCH碼C(x)中，n是整個碼字的長度，k為待編碼的信息位長度，t是在整個碼字跨度上糾正位錯的個數(shù)，n-k和mt都代表碼的校驗(yàn)位長度[7-8]。此方案設(shè)計級聯(lián)RCRF后采用BCH算法更正3位錯誤，實(shí)現(xiàn)的BCH碼為GF(212)上的縮短碼(2 085,2 049,3)。

如圖6所示，C(x)的串行編碼可以通過帶反饋回路的n-k級移位寄存器的有限域除法電路來實(shí)現(xiàn)，反饋回路的連接關(guān)系由生成多項(xiàng)式g(x)的系數(shù)gi是否為1來確定，其中⊕代表異或關(guān)系，然后取寄存器中存儲的余式作為校驗(yàn)位B(x)。即：

B(x)=(xn-km(x))modg(x)

圖6 有限域除法電路

為提高編碼效率，通過推導(dǎo)合并串行運(yùn)算的方法，可以得到p位并行迭代編碼的計算公式(1)。te表示迭代的次數(shù)，b(te)表示第te次迭代后n-k個寄存器的值，Rp(te)表示第te次迭代輸入的p位信息位[9]。在硬件電路中，式(1)描述的寄存器狀態(tài)更新關(guān)系，可以通過使用matlab編寫生成對應(yīng)的verilog組合邏輯函數(shù)來實(shí)現(xiàn)。

b(te+1)=Fpb(te)+FGpRp(te)

(1)

式中矩陣FGp為：

FGp=(Fp-1G,…,FG,G)

其中向量G為：

G=(gn-k-1,…,g1,g0)T

矩陣F為：

2.2 BCH解碼

BCH解碼總體上包含計算伴隨式，確定錯誤位置多項(xiàng)式和錢搜索這3個環(huán)節(jié)[10-11]，本研究分別對其進(jìn)行模塊化的邏輯電路功能描述，采用流水線式的操作結(jié)構(gòu)，每個硬件模塊執(zhí)行完成即切換處理下一幀數(shù)據(jù)。設(shè)v(x)發(fā)送多項(xiàng)式，e(x)為差錯多項(xiàng)式，則接收多項(xiàng)式r(x)=v(x)+e(x)。

2.2.1 伴隨式求解

伴隨式s(x)是r(x)除以g(x)所得的余數(shù)。即：

s(x)=r(x)modg(x)

若s(x)=0，則認(rèn)為接收多項(xiàng)式與發(fā)送多項(xiàng)式完全一致，即在整個信道傳輸過程中數(shù)據(jù)沒有任何錯誤。若s(x)≠0，則表示檢測到了錯誤并需根據(jù)式sz=s(αz)計算參數(shù)sz以用于確定錯誤位置多項(xiàng)式(1≤z≤2t，α是本原元)[12]。伴隨式的計算過程分為2部分。首先將接收數(shù)據(jù)的前2 049位送入編碼電路，然后將得到的余式與接收數(shù)據(jù)的后36位進(jìn)行異或操作，完成后即可得出s(x)。

2.2.2 確定錯誤位置多項(xiàng)式

BM算法是用于確定錯誤位置多項(xiàng)式σ(x)的一種經(jīng)典迭代譯碼算法。其迭代方程為：

(2)

式中：dμ代表第μ次迭代的修正項(xiàng)(0≤μ≤2t-1)，有：

(3)

ρ的選擇原則是滿足ρ<μ且dρ≠0的所有ρ中使得ρ-lρ值最大的那個。lρ代表σ(ρ)(x)的階。

由于該迭代方程中存在有限域求逆運(yùn)算，對應(yīng)的多項(xiàng)式除法算法復(fù)雜度高且不易于硬件實(shí)現(xiàn)，故采用一種無求逆的iBM算法[13-14]?？梢詫⒂邢抻蚨囗?xiàng)式求逆運(yùn)算轉(zhuǎn)換為多項(xiàng)式乘法運(yùn)算[15]：

A(x)B(x)=(am-1xm-1+…+a0)·

(bm-1xm-1+…+b0)modQ(x)=

(4)

式中：Q(x)=xn+qn-1xn-1+…+q1x+1=x12+x6+x4+x+1，代表有限域GF(212)的本原多項(xiàng)式。矩陣fij為：

(5)

qi,j的第1行為Q(x)的多項(xiàng)式系數(shù)，即q0,j=qj，其余元素可以通過式(6)使用遞歸方法得到。進(jìn)而方便求出GF(212)中易于用組合邏輯描述的多項(xiàng)式乘法的確定形式。

(6)

同時通過推導(dǎo)與總結(jié)，可得奇數(shù)次迭代的修正項(xiàng)dμ的值始終為0，所以對于糾正3位錯的BCH碼，求解錯誤位置多項(xiàng)式的迭代過程可以從6步縮減為3步。憑借迭代方程描述的特定關(guān)系，進(jìn)一步簡化迭代過程，通過判斷dμ的值是否為0，圖7列出了最終錯誤位置多項(xiàng)式的4種確定情況。ex表示當(dāng)d2=0,d4≠0時接收數(shù)據(jù)中的位錯數(shù)量超出了BCH碼的糾錯能力范圍。應(yīng)用這種直接的錯誤位置多項(xiàng)式求解方法，避免了繁瑣的迭代過程，可顯著減小算法復(fù)雜度，加快譯碼進(jìn)程并降低電路延遲。

圖7 錯誤位置多項(xiàng)式的4種情況

2.2.3 錢搜索

錢搜索算法是將GF(212)域中元素分別代入σ(x)，以驗(yàn)證σ(α-i)是否等于0的過程[16]，如果滿足條件則說明接收數(shù)據(jù)的第i位為錯誤位置，對錯誤位置取反即可完成糾錯。為加快譯碼速度，例化了32個錢搜索模塊并行處理該搜索過程。并行電路如圖8所示，圖中?符號代表有限域多項(xiàng)式乘法操作。在實(shí)際電路實(shí)現(xiàn)時，由于采用的是縮短碼(2 085,2 049,3)，所以不用遍歷原碼域中全部的元素，可以將根的范圍鎖定在α2 011到α4 095之間。同時通過判斷σ(x)的階可以得出發(fā)生隨機(jī)錯誤的個數(shù)，因此在搜索到對應(yīng)個數(shù)的根后可提前終止搜索過程。通過使用提出的這2個方法可顯著提高譯碼速度并減小功耗(具體速度的提升空間取決于碼字中錯誤的位置分布)。

圖8 并行錢搜索電路

3 仿真與驗(yàn)證

已使用Verilog對電路進(jìn)行描述，并搭建了matlab軟件平臺，方便對其進(jìn)行對比驗(yàn)證，Vivado綜合后的仿真結(jié)果證明了該方案具有出色高效的糾錯性能。

取擦除后從NAND FLASH讀出的2 049位數(shù)據(jù)，假設(shè)從高位數(shù)的第2位、第3位發(fā)生擦除錯誤，即最高9位從1FF改變?yōu)?3F。且設(shè)此時亟待寫入的2 048位信息位最高8位為C0，即在對應(yīng)錯誤位置的2位數(shù)據(jù)都為1。此情況滿足RCRF編碼的判斷條件，所以首先采用RCRF編碼，翻轉(zhuǎn)1位標(biāo)志位和2 048位信息位(此時最高9位為03F)，并隨之送入128位并行BCH編碼器。圖9展示了編碼電路仿真結(jié)果的主要信號。RCRF_read表示從NAND FLASH讀出的數(shù)據(jù)；message表示準(zhǔn)備寫入的2 048位數(shù)據(jù)；信號flag_bit顯示標(biāo)志位翻轉(zhuǎn)后始終為0；encode_128展示了128并行編碼器每次迭代后36位寄存器的狀態(tài)更新過程；最終圖中顯示經(jīng)過0～16個cnt加1的過程后(共計迭代17次)，輸出編碼結(jié)果parity，其值為023FB3197，與matlab的編碼輸出結(jié)果一致。

設(shè)讀出時2 085位數(shù)據(jù)中(翻轉(zhuǎn)后的1位標(biāo)志位+翻轉(zhuǎn)后的2 048位信息位+36位校驗(yàn)位)，從最高位數(shù)的第6、第7和第8位發(fā)生隨機(jī)錯誤，即前9位從03F轉(zhuǎn)變?yōu)?31。接下來對該2 085位數(shù)據(jù)din進(jìn)行譯碼操作。為了方便說明，現(xiàn)將解碼過程的部分主要信號分成圖10、圖11進(jìn)行闡述。

首先輸出BCH伴隨式求解結(jié)果S(x)=8B2E8A389，因?yàn)榇藭rS(x)不為0，代表檢測到了隨機(jī)錯誤，所以隨之S(x)_complish信號置1表明伴隨式計算完成且有效。將值送入S1～S6計算模塊，圖10中信號S1～S6給出了對應(yīng)參數(shù)的求解結(jié)果，并拉高有效信號s1_6_vld，同時使能錯誤位置多項(xiàng)式計算模塊。使用圖7所示的優(yōu)化結(jié)構(gòu)，僅在4個時鐘周期后便可快捷得到錯誤位置多項(xiàng)式系數(shù)sigma0～sigma3的計算結(jié)果。three_err變?yōu)楦唠娖奖砻鞲鶕?jù)錯誤位置多項(xiàng)式的最終形式判斷得出接收數(shù)據(jù)中有3位數(shù)據(jù)發(fā)生錯誤。

然后執(zhí)行32位并行錢搜索操作。如圖11所示，chien_vld_6～chien_vld_8表明在6、7、8這3個錢搜索模塊中搜尋到錯誤位置多項(xiàng)式的3個根，分別為α2 016、α2 017和α2 018。根據(jù)此信息將對應(yīng)位置數(shù)據(jù)取反，信號BCH_de顯示3個隨機(jī)位錯已經(jīng)被糾正，即前9位從031更正為03F。此時BCH解碼過程結(jié)束，執(zhí)行RCRF譯碼操作，經(jīng)過判斷，標(biāo)志位當(dāng)前值為0，已知如果標(biāo)志位為0說明數(shù)據(jù)經(jīng)歷過翻轉(zhuǎn)操作，因此將2 048位數(shù)據(jù)再次翻轉(zhuǎn)得到最終的正確數(shù)據(jù)decode_result。圖中該信號的最高8位為C0，表明從數(shù)據(jù)發(fā)送到接受產(chǎn)生的5個位錯已經(jīng)被全部糾正，譯碼完畢。

圖9 128位并行RCRF+BCH編碼仿真結(jié)果

圖10 128位并行RCRF+BCH伴隨式及錯誤位置多項(xiàng)式仿真結(jié)果

圖11 并行錢搜索仿真結(jié)果

4 結(jié)語

針對在具有高誤碼率情況下的NAND FLASH或其他存儲器，本文提出并實(shí)現(xiàn)了一種實(shí)用的高速并行RCRF+BCH糾錯方案。對比單獨(dú)使用BCH算法，此方案在僅添加一位標(biāo)志位的情況下具備糾正更多位錯的能力，減小了校驗(yàn)位開銷，極大保證了數(shù)據(jù)的準(zhǔn)確性，顯著提高了存儲系統(tǒng)的可靠性。同時由于FPGA具有靈活度高，可移植性強(qiáng)的特點(diǎn)，后續(xù)可以對這種方案配置不同的設(shè)計參數(shù)，以滿足不同的糾錯需求。