基于BCH 糾錯(cuò)算法的編解碼器設(shè)計(jì)與實(shí)現(xiàn)*

王莞，魏敬和，于宗光

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

0 引言

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

1 BCH 編碼基本原理

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

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

BCH 編碼可以按如下方式構(gòu)造，假定信息多項(xiàng)式為：

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

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

其中校檢多項(xiàng)式為：

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

可以得到迭代計(jì)算的關(guān)鍵方程式：

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

圖1 16 位并行編碼器結(jié)構(gòu)

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

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

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

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

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

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

3 BCH 譯碼器設(shè)計(jì)

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

圖3 BCH 譯碼流程

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

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

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

3.1 伴隨多項(xiàng)式計(jì)算

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

接收到的碼字多項(xiàng)式為：

假設(shè)錯(cuò)誤多項(xiàng)式為：

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

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

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

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

上式展開得：

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

圖4 并行伴隨式電路結(jié)構(gòu)

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

圖5 伴隨多項(xiàng)式計(jì)算狀態(tài)轉(zhuǎn)換圖

3.2 錯(cuò)誤多項(xiàng)式提取

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

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

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

3.3 錢氏搜索法定位錯(cuò)誤位置

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

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

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

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

4 仿真與驗(yàn)證結(jié)果分析

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

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

圖8 伴隨多項(xiàng)式計(jì)算與錯(cuò)誤多項(xiàng)式提取仿真波形圖

圖9 錢氏搜索仿真波形圖

5 結(jié)論

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

表1 糾錯(cuò)能力及頻率對(duì)比