王莞，魏敬和，于宗光

(1.江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122；2.中國電子科技集團第58 研究所，江蘇 無錫 214072)

0 引言

Nand Flash 是一種非易失性存儲器，與NOR Flash 相比具有讀寫速度快和存儲密度高等優(yōu)勢，但由于NAND Flash 本身結構特點，其存儲單元出現(xiàn)數(shù)據(jù)位翻轉現(xiàn)象比NOR Flash 中更常見[1]，與此同時，隨著NAND Flash技術的飛快發(fā)展，NAND Flash 從SLC 結構發(fā)展為MLC結構及現(xiàn)在的TLC 結構，每個存儲單元可以存儲2 bit 以至更多的數(shù)據(jù)，使得數(shù)據(jù)位之間的相互干擾變大，進而導致出錯概率增大，隨著工藝水平的不斷提高，超深亞微米下的電荷效應進一步增加了數(shù)據(jù)出錯的可能性。因此，在對NAND Flash 存儲數(shù)據(jù)時，必須采用更高的糾錯技術，以提高存儲的穩(wěn)定性。文獻[2]中采用一種8 位并行BCH 編解碼器，但因為電路并行處理數(shù)據(jù)少，影響處理速度,文獻 [3] 中設計一種糾錯16 位的BCH 編解碼器，但糾錯位數(shù)較少。文獻[4]中設計一種校正32 位出錯位的BCH 編解碼器，相比較糾錯位數(shù)有所增加，但還不能滿足大容量存儲的數(shù)據(jù)校正。本文設計一種16 位并行BCH 編解碼器，并且具有最高48 位糾錯能力，糾錯速度和糾錯能力都有了進一步的提高。

1 BCH 編碼基本原理

矩陣BCH 碼是糾正多個隨機錯誤的循環(huán)碼，可以用生成多項式g(x)的根來描述。它是一種有限域中的線性分組碼，廣泛應用于存儲和通信領域中的編碼。定義如下：給定任一有限域GF(q)及其擴域GF(qm)，其中q 是素數(shù)或素數(shù)的冪，m 為某一正整數(shù)。若任一碼元取自GF(qm)上的循環(huán)碼(n，k)，其中n=2m-1，其生成多項式g(x)具有2t 根{a1，a2，…，a(2t-1)，a2t}時，t 位 數(shù)，則 由生成多項式g(x)生成的循環(huán)碼稱為q 進制BCH 碼，記為(n，k，t)[5]。最常用的BCH 碼通常為二進制的BCH 碼，二進制BCH 碼的碼元都是由0 和1 構成的，便于硬件電路的實現(xiàn)。本文以下討論的BCH 碼是二進制BCH 碼，二進制本原BCH 碼有以下重要參數(shù)，碼長為n=2m-1，信息長度為k，糾錯位數(shù)量為t，校檢碼長度為mt=n-k，對于本設計中，k=1 024 B=8 192 bit，t=48，n=8 192+48×14=8 864，因此BCH 碼為(8 864，8 192，48)，其中，校檢碼長度為672 bit。

2 BCH 并行編碼器設計

BCH 編碼可以按如下方式構造，假定信息多項式為：

其中，mi∈GF(2)，BCH 碼系數(shù)通常由計算機離線生成，首先找到生成多項式g(x)，記為：

則BCH 編碼后的碼組c(x)為：

其中校檢多項式為：

由n-k=672，故r(x)=(x672m(x))mod g(x)進行16 位并行編碼，記k=L·m，L=512，則有：

可以得到迭代計算的關鍵方程式：

所以BCH 編碼的實質就是有限域內以生成多項式為模的除法問題，是將xn-km(x)對生成多項式g(x)求模，可以通過線性移位寄存器(LFSR)來實現(xiàn)，16 位并行編碼器原理結構如圖1 所示。

圖1 16 位并行編碼器結構

16 位并行BCH 編碼器工作流程如下：

(1)在編碼開始之前，把所有寄存器初始化為0；

(2)把ri(x)=(ri-1(x)x16+Mi)mod g(x)式做循環(huán)迭代運算，Mi即為當前時刻要輸入到Nand Flash 中16 位數(shù)據(jù)，信息比特按照從高位到低位的方式依次進入。

(3)迭代到512 次的時候進入另一個階段，這時設置輸入Mi=0，再繼續(xù)迭代計算42 次，就完成并行編碼的計算，BCH 編碼寄存器儲存的值即為最終校檢位。

BCH 編碼過程包含3 個狀態(tài)，分別為空閑狀態(tài)(IDLE)、編碼狀態(tài)(ENC)、校檢因子傳輸狀態(tài)(WRITE)。在復位信號為低電平時，狀態(tài)機都被轉入IDLE 狀態(tài)，在時鐘上升沿，糾錯使能信號enable_ecc 為高電平，dir_sel 信號為低電平并且碼字有效信號data_in_valid 為高電平時轉入ENC 狀態(tài)；當1 024 B 數(shù)據(jù)編碼完成后進入WRITE 狀態(tài)，當完成校檢因子傳輸后回到IDLE 狀態(tài)，其狀態(tài)轉換圖如圖2 所示。

圖2 編碼過程狀態(tài)轉換圖

3 BCH 譯碼器設計

在所有的BCH 譯碼算法中最常用是Berlekamp-Massey 迭代算法(簡稱BM 法)，BCH 譯碼器首先通過計算校檢因子實現(xiàn)錯誤檢測，然后通過無逆BM 迭代算法和錢氏(Chien)搜索法實現(xiàn)糾錯，譯碼過程主要分為以下三個步驟完成[6]，BCH 譯碼流程如圖3 所示。

圖3 BCH 譯碼流程

第一步：由接收到的R(x)計算伴隨多項式S=(s1，s2，s3，…，s2t)，求出伴隨式系數(shù)。

第二步：根據(jù)伴隨多項式S 求解錯誤多項式σ(x)=σtxt+σt-1xt-1+…+σ1x1+1，進行錯誤多項式系數(shù)提取。

第三步：求解σ(x)的根，利用錢氏(Chien)搜索法進行錯誤位置定位，并進行錯誤糾正。

3.1 伴隨多項式計算

假定發(fā)送的碼字為：

接收到的碼字多項式為：

假設錯誤多項式為：

理論上，任何一個接收碼字R(x)均可看作發(fā)送碼字C(x)與錯誤多項式E(x)的疊加[7]，即：

由于ST=HRT，其中H 為校檢多項式，因此伴隨多項式可以表示為：

由于aj(j=0，1，2，…，2t)是生成多項式g(x)的根，因此，當x=aj時，可得到伴隨多項式的系數(shù)為Sj=R(aj)=mj(aj)g(aj)+Ej(aj)=Ej(aj)，伴隨多項式S=(s1，s2，…，s2t)的計算轉換為R(x)除以g(x)的除法運算，相除之后的余式即為伴隨式，如果伴隨多項式中任意一個元素Sj不為0，則表明有錯誤，否則沒有錯誤。

伴隨式電路硬件實現(xiàn)如下：

上式展開得：

16 位并行伴隨式電路結構如圖4 所示，每個時鐘周期可以處理16 bit 數(shù)據(jù)，其中，乘法器和加法器均為有限域乘法器和有限域的加法器，因為有限域的加法采用模2 進行運算，故加法器為直接的異或運算。在GF(214)域多項式的乘法過程和一般多項式乘法一樣，在各項相加的時候按照模2 規(guī)則進行，運算過程出現(xiàn)大于a14項需要通過GF(214)域上的本原多項式x14+x10+x6+x1進行高位消除[8]。首先計算S=(S1，S3，…，S2t-1)，然后由于伴隨系數(shù)滿足，通過計算得到S=(s2，s4，…，s2t)。由此可得伴隨多項式為：

圖4 并行伴隨式電路結構

BCH 譯碼首先要進行伴隨多項式求解，伴隨多項式計算作為流水線的第一級，設計伴隨式模塊有三個狀態(tài)分別為空閑狀態(tài)(SYN_IDLE)、接收碼字狀態(tài)(READ)、伴隨式計算狀態(tài)(SYND_CALC)，在復位信號為低電平時，無論伴隨式模塊在何種狀態(tài)，都被轉入SYND_IDLE 狀態(tài)，在時鐘上升沿，糾錯使能信號enable_ecc 和碼字有效信號data_in_valid 為高電平時轉入READ 狀態(tài)。當伴隨式模塊處READ 狀態(tài)，計數(shù)信號cnt_syn_r 為1 024 時，進入SYND_CALC 狀態(tài)。當在伴隨計算狀態(tài)，如果cnt_syn_r=6′b101110 并且data_in_valid 為低電平時，表明伴隨式計算完成，伴隨式計算模塊轉入SYN_IDLE 狀態(tài)；如果伴隨式系數(shù)有一個不為零，表明接收碼字有錯誤，需要進入后續(xù)的錯誤位置多項式和錢氏搜索操作，伴隨式計算狀態(tài)轉換如圖5 所示。

圖5 伴隨多項式計算狀態(tài)轉換圖

3.2 錯誤多項式提取

求解錯誤位置多項式是BCH 譯碼過程中最重要的一步，首先構造錯誤位置多項式如下所示：σ(x)=σtxt+σt-1xt-1+…+σ1x1+1，其中，錯誤位置為該式的根，由數(shù)學推演，可知錯誤多項式的系數(shù)σt，σt-1，…，σ2，σ1和伴隨式有如下關系：

將S(x)和σ(x)帶入上面方程式得到σ(x)的關鍵方程[9]：

由于BM 算法迭代效率，易于硬件實現(xiàn)，本文采用基于二進制BCH 碼的無求逆BM 迭代算法求解該方程，首先選擇一組合理的初始值σ(0)(x)和ω(0)(x)，經過第一次迭代運算求得σ(1)(x)和ω(1)(x)[10]，依次類推，由σ(i)(x)和ω(i)(x)求得σ(i+1)(x)和ω(i+1)(x)。迭代過程中定義第j+1 和第j 步的差值為dj，則有：

3.3 錢氏搜索法定位錯誤位置

通過上面的BM 算法，能夠得知錯誤位置多項式為σ(x)=σtxt+σt-1xt-1+…+σ1x1+σ0，如果直接對上式進行因式分解[13]，將得到σ(x)的分解等式：

隨著t 的值變大時，會發(fā)現(xiàn)求σ(x)的因式分解越來越困難，因此通常采用錢氏搜索法求出上式方程的根。錢氏搜索法原理如下[14]，當x=1/β1時，σ(x)=0，其中x 的取值范圍為ai，i=n-1，n-2，…，0。因此，將ai依次帶入σ(x)，如果σ(x)=0，則ai為根，說明第i 位發(fā)生了錯誤[15]。

BCH 譯碼過程第三級通過錢氏搜索法進行錯誤位置定位并進行糾錯，錢氏搜索過程包含四個狀態(tài)分別為錢氏搜索空閑狀態(tài)(CHI_IDLE)、接收碼狀態(tài)(CHIEN_NC)、搜索狀態(tài)(CHIEN)、錯誤信息發(fā)出狀態(tài)(STIG)。開始chien_state_next 寄存器為SYND_IDLE 狀態(tài)，在時鐘上升沿，chi_err_r 信號變?yōu)楦唠娖胶螅瑺顟B(tài)機跳轉到CHIEN_NC狀態(tài)。當cnt_chi_r 搜索計數(shù)信號滿足時，chien_state_next為CHIEN 狀態(tài)；在錢氏搜索找到錯誤總數(shù)chi_cnt_err_r信號等于cnt_exp_err_r 信號時，完成錢氏搜索chien_state_next 進入STIG 狀態(tài)，在下一個時鐘上升沿dec1_full 信號滿足為低電平時，chien_state_next 回到CHI_IDLE 狀態(tài)，錢氏搜索狀態(tài)轉換如圖6 所示。

圖6 錢氏搜索狀態(tài)轉換圖

4 仿真與驗證結果分析

利用Verilog 語言完成上述電路模塊的RTL 級設計，在Linux 系統(tǒng)下利用VCS 工具進行電路的仿真與驗證。發(fā)送8 192 比特信息位，通過BCH 并行編碼器電路生成672 位校檢碼，編碼過程仿真波形圖如圖7 所示。完成編碼后本文通過后門訪問FIFO 寄存器把1、3、5、7、9、11 字節(jié)的數(shù)據(jù)翻轉，共產生48 位錯誤，然后再通過BCH 譯碼器分別進行伴隨式因子的計算，錯誤多項式系數(shù)提取，最后通過Chien 搜索法找到發(fā)生了錯誤位置的定位并正了錯誤值，伴隨多項式計算與錯誤多項式提取仿真波形圖如圖8 所示，錢氏搜索仿真如圖9所示。

圖7 并行編碼過程仿真波形圖

圖8 伴隨多項式計算與錯誤多項式提取仿真波形圖

圖9 錢氏搜索仿真波形圖

5 結論

本文對編譯碼電路采用高效16 并行電路結構，與此同時譯碼過程采用流水線結構，BCH 解碼器可以在從內存中讀取數(shù)據(jù)時檢測錯誤，提出了一種對于Nand Flash 的48 bit 糾錯能力解決方案，同時減少資源的消耗，減少編解碼和解碼周期。與其他文獻中編解碼中的數(shù)據(jù)傳輸速度、工作頻率與糾錯能力對比如表1 所示。今后在此基礎上研究AES 加密算法，實現(xiàn)對數(shù)據(jù)的加密和解密方面有進一步研究。

表1 糾錯能力及頻率對比