蔡恒，崔雪楠，孟虹兆，黃啟俊，常勝

（武漢大學(xué)物理科學(xué)與技術(shù)學(xué)院微電子學(xué)與固體電子學(xué)，湖北武漢430072）

隨著科技進(jìn)步和信息化的快速發(fā)展，如何在海量數(shù)據(jù)存儲(chǔ)中確保數(shù)據(jù)不出錯(cuò)成為眾人關(guān)心的問題。作為廣泛應(yīng)用于U盤、固態(tài)硬盤等電子產(chǎn)品的一種非易失性存儲(chǔ)介，NAND Flash由于其結(jié)構(gòu)的特殊性，在進(jìn)行擦寫操作時(shí)易產(chǎn)生錯(cuò)誤，故需要引入錯(cuò)誤校驗(yàn)機(jī)制。早期使用SLC工藝的NAND Flash通常采用漢明碼（ECC）校驗(yàn)，但是無法糾正1 bit以上的錯(cuò)誤。現(xiàn)今的MLC工藝多采用BCH糾錯(cuò)，但每頁產(chǎn)生的錯(cuò)誤往往超過2 bit，甚至達(dá)到4 bit。國內(nèi)外對(duì)BCH糾錯(cuò)的研究已展開，參考文獻(xiàn)[1-2]采用串行結(jié)構(gòu)完成譯碼器設(shè)計(jì)，實(shí)現(xiàn)簡(jiǎn)單，但最大時(shí)鐘頻率小、速度慢，無法滿足高速的需要。參考文獻(xiàn)[3-4]中提出并行化結(jié)構(gòu)，提高了設(shè)計(jì)速度和數(shù)據(jù)吞吐量，但電路實(shí)現(xiàn)討論不充分。參考文獻(xiàn)[5]中通過ASIC制備芯片并進(jìn)行測(cè)試驗(yàn)證，但此方法周期長(zhǎng)、費(fèi)用高。

針對(duì)以上問題，本文基于Altera公司的CycloneII EP2C35系列FPGA完成了并行化BCH(8184，7976，16)碼編譯器設(shè)計(jì)，并利用SoPC Builder搭建了驗(yàn)證平臺(tái)，在Nios II處理器的控制下能高效地完成BCH編譯碼算法的驗(yàn)證，具有測(cè)試環(huán)境可配置、測(cè)試向量覆蓋率高、測(cè)試流程智能化的特點(diǎn)。

1 BCH編譯碼FPGA設(shè)計(jì)

結(jié)合實(shí)際使用NAND Flash的情況，16 bit糾錯(cuò)是NAND Flash使用的趨勢(shì)。本設(shè)計(jì)采用并行化結(jié)構(gòu)實(shí)現(xiàn)16 bit BCH碼算法。

1.1 并行BCH編碼器的設(shè)計(jì)

BCH 編碼器通過除法電路得到余數(shù)作為系統(tǒng)碼的校驗(yàn)位，實(shí)現(xiàn)公式為：

其中，m(x)為原碼，C(x)為編碼得到的系統(tǒng)碼，g(x)為生成多項(xiàng)式。

對(duì)于BCH(8184，7976，16)碼，有:

由式(4)可知編碼的核心計(jì)算單元Ri-1(x)x8mod g(x)可由8個(gè)Ri-1(x)x mod g(x)級(jí)聯(lián)而成，單個(gè)Ri-1(x)x mod g(x)電路是一個(gè)純組合邏輯的線性移位電路，有：

則余式求解如下：

式(7)可采用線性反饋移位寄存器（LFSR）電路來實(shí)現(xiàn)[6]。電路如圖1所示。

1.2 并行BCH譯碼器的設(shè)計(jì)

BCH譯碼由伴隨式計(jì)算、求解錯(cuò)誤位置多項(xiàng)式、Chien搜索3個(gè)步驟組成。由接收到的系統(tǒng)碼R(x)計(jì)算伴隨式S(x)；根據(jù)伴隨式S(x)求解關(guān)鍵方程，求出錯(cuò)誤位置多項(xiàng)式σ(x)；采用Chien搜索算法求解錯(cuò)誤位置；再根據(jù)錯(cuò)誤位置將相應(yīng)位置上的數(shù)據(jù)取反，即可得到正確的原碼。以上流程通過伴隨式計(jì)算電路、錯(cuò)誤位置多項(xiàng)式求解電路及Chien搜索電路來實(shí)現(xiàn)。

1.2.1 伴隨式求解

伴隨式的計(jì)算分兩步完成：首先將接收到的系統(tǒng)碼R(x)對(duì)最小多項(xiàng)式求余，獲得余數(shù)項(xiàng)為rk(x)；再將相應(yīng)的共軛類元素αi逐一代入余式求解出伴隨式Si=rk(αi)。伴隨式計(jì)算電路求解出余式后，由常數(shù)乘法器計(jì)算得到伴隨式的最終結(jié)果。

1.2.2 關(guān)鍵方程求解

令錯(cuò)誤位置多項(xiàng)式為：σ(x)=1+σ1x+σ2x2+σ3x3+…+σtxt，伴隨式多項(xiàng)式：S(x)=1+S1x+S2x2+S3x3+…+S2tx2t，則關(guān)鍵方程為?(x)=S(x)σ(x)，借助牛頓等式即可求解出錯(cuò)誤位置多項(xiàng)式的各項(xiàng)系數(shù)。電路結(jié)構(gòu)如圖2所示。

圖2 關(guān)鍵方程求解電路結(jié)構(gòu)圖

1.2.3 錢搜索

得到錯(cuò)誤位置多項(xiàng)式σ(x)之后，找出出錯(cuò)比特所在的位置。計(jì)算σ(αn-i)=1+σ1αn-i+σ2α2(n-i)+σ3α3(n-i)+…+σtαt(n-i)。如果σ(αn-i)=0，則該比特位出錯(cuò)，否則正確。圖3為錢搜索模塊電路，主要由乘法、加法和求反組成。其中對(duì)錢搜索部分影響最大的是乘法器的選擇，本設(shè)計(jì)采用通用乘法器。

圖38 位并行錢搜索模塊電路圖

2 基于SoPC技術(shù)的驗(yàn)證系統(tǒng)

搭建了基于SoPC技術(shù)的嵌入式驗(yàn)證平臺(tái)，NiosⅡProcessor通過AVALON總線以AVALON—SLERVER協(xié)議與RAM_CONTROLLER以及BCH_IP外設(shè)進(jìn)行通信，控制編譯碼模塊工作，如圖4所示。其中data_cnt為傳輸碼元數(shù),eob信號(hào)為傳輸碼元結(jié)束信號(hào)，sob為開始傳輸原碼信號(hào)，data信號(hào)為傳輸原碼數(shù)據(jù)。

在此基礎(chǔ)上，利用NIOS向RAM中寫入多種類別錯(cuò)誤進(jìn)行糾錯(cuò)。大量數(shù)據(jù)的測(cè)試證明了BCH編譯碼設(shè)計(jì)的正確性。部分測(cè)試結(jié)果如表1所示。

使用硬件描述語言，基于Altera公司的Quartus8.0開發(fā)工具完成了應(yīng)用于NAND Flash的并行化BCH編譯碼器的設(shè)計(jì)。采用并行結(jié)構(gòu)縮短了編解碼周期，最大時(shí)鐘頻率可達(dá)101.84 MHz。搭建了基于SoPC技術(shù)的嵌入式驗(yàn)證平臺(tái)，在Nios II處理器的控制下高效地完成了BCH編譯碼算法的驗(yàn)證。驗(yàn)證結(jié)果表明該算法具有測(cè)試環(huán)境可配置、測(cè)試向量覆蓋率高及測(cè)試流程智能化的特點(diǎn)。

圖4 驗(yàn)證系統(tǒng)結(jié)構(gòu)圖

表1 糾錯(cuò)結(jié)果表

[1]孫怡，田上力，林建英.BCH碼譯碼器的FPGA實(shí)現(xiàn)[J].電路與系統(tǒng)學(xué)報(bào)，2000(12)：98-100.

[2]江建國.BCH編譯碼器的設(shè)計(jì)及驗(yàn)證[D].上海：上海交通大學(xué).2010.

[3]張彥，李署堅(jiān)，崔金.一種BCH碼編譯碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù)，2010，43(12)：24-26.

[4]劉冀，孫玲.可變碼率BCH碼編譯碼的FPGA實(shí)現(xiàn)[J].信號(hào)與信息處理，2010，40(7)：11-13.

[5]許錦.NAND Flash快速BCH編解碼算法及硬件實(shí)現(xiàn)[D].上海：上海復(fù)旦大學(xué)，2008.

[6]趙景琰，金鷹翰，趙培，等.并行化的BCH編解碼器設(shè)計(jì)[J].微處理機(jī)，2010(4)：42-45.