BCH編譯碼器的FPGA設計及SoPC驗證*

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

（武漢大學物理科學與技術學院微電子學與固體電子學，湖北武漢430072）

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

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

1 BCH編譯碼FPGA設計

結合實際使用NAND Flash的情況，16 bit糾錯是NAND Flash使用的趨勢。本設計采用并行化結構實現16 bit BCH碼算法。

1.1 并行BCH編碼器的設計

BCH 編碼器通過除法電路得到余數作為系統碼的校驗位，實現公式為：

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

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

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

則余式求解如下：

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

1.2 并行BCH譯碼器的設計

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

1.2.1 伴隨式求解

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

1.2.2 關鍵方程求解

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

圖2 關鍵方程求解電路結構圖

1.2.3 錢搜索

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

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

2 基于SoPC技術的驗證系統

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

在此基礎上，利用NIOS向RAM中寫入多種類別錯誤進行糾錯。大量數據的測試證明了BCH編譯碼設計的正確性。部分測試結果如表1所示。

使用硬件描述語言，基于Altera公司的Quartus8.0開發工具完成了應用于NAND Flash的并行化BCH編譯碼器的設計。采用并行結構縮短了編解碼周期，最大時鐘頻率可達101.84 MHz。搭建了基于SoPC技術的嵌入式驗證平臺，在Nios II處理器的控制下高效地完成了BCH編譯碼算法的驗證。驗證結果表明該算法具有測試環境可配置、測試向量覆蓋率高及測試流程智能化的特點。

圖4 驗證系統結構圖

表1 糾錯結果表

[1]孫怡，田上力，林建英.BCH碼譯碼器的FPGA實現[J].電路與系統學報，2000(12)：98-100.

[2]江建國.BCH編譯碼器的設計及驗證[D].上海：上海交通大學.2010.

[3]張彥，李署堅，崔金.一種BCH碼編譯碼器的設計與實現[J].通信技術，2010，43(12)：24-26.

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

[5]許錦.NAND Flash快速BCH編解碼算法及硬件實現[D].上海：上海復旦大學，2008.

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