一種優化的BCH編解碼器的設計與實現?

雷水艷 焦繼業 陳亞南

（西安郵電大學電子工程學院 西安 710121）

1 引言

隨著汽車電子技術的廣泛應用，用于海量汽車數據存儲的 NAND Flash［1］，因其自身缺點，在使用時會出現差錯，這種差錯主要來自兩種情況:一是由于工藝原因在生產及使用過程中會產生壞塊；二是由于存儲單元問題使用時會發生位反轉，以及空間環境的輻射也會導致位反轉［2］。因此，如何糾錯成為汽車電子NAND Flash可靠存儲的關鍵問題。文獻［3］中設計一種校正4位出錯位的BCH編解碼器，但校正位數較少。文獻［4］中設計一種校正8位出錯位的BCH編解碼器，相比文獻［3］校正位數有所增加，但還不能滿足大容量存儲的數據校正；文獻［5］中設計一種校正32位出錯位的BCH編解碼器，其校正位數較多，但因為電路復雜度的增加，導致編解碼速度降低。在此基礎上，本文提出一種優化的BCH編解碼器的設計，在保證編解碼速度的同時，最高校正位數達到48位。

2 BCH編解碼器整體設計

BCH碼取自Bose、Ray-Chaudhuri與Hocquenghem的縮寫［6～7］，是一種有限域中的線性分組碼，具有糾正多個隨機錯誤的能力，通常用于通信和存儲領域中的糾錯編碼。定義如下:給定任意一個有限域GF(q)及其擴展域GF(qm)，其中q是素數或素數的冪，m為正整數，對于任意一個碼元取自擴展域GF(qm)的循環碼（n，k），其中 n=2m-1，其生成多項式 g(x)具有2t個連續的根為，則由生成多項式g(x)編碼產生的循環碼稱為q進制的BCH碼，記為（n，k，t）［8～9］。

本文使用MICRON NAND devices，頁可配置為4KB+128B，并且每頁又分為4個子頁，即每個子頁為1KB+32B，內部存儲結構如圖1。

圖1 內部存儲結構

校正一個出錯位需要14個校驗位，所以校正48個出錯位需要48*14=672個校驗位，由此可得該BCH碼的參數為

1）碼元長度:n=4*1024*8+672=33440bits

2）檢驗位長度:r=14*48=672bits

3）糾錯能力:t=48bits

4）信息位長度:k=n-r=32768bits

其電路模塊框圖如圖2。

圖2 BCH算法模塊框圖

數據在寫入NAND Flash時進行編碼，生成校驗位，編碼完成后，將結果送入解碼模塊。在讀取數據時進行解碼，首先進入伴隨式計算模塊，完成伴隨式的計算，然后將結果送入錯誤位置多項式模塊，其次進入錯誤位置多項式模塊，完成錯誤位置多項式系數的計算，然后將結果送入Chien搜索模塊，最后進入Chien搜索模塊，完成錯誤位置多項式根的計算，然后找到出錯位，完成糾錯。對于二進制BCH碼，糾錯就是對相應位進行取反操作［10］。

2.1 編碼器設計

令信息位多項式為m(x)=m0x0+m1x1+…+mk-2xk-2+mk-1xk-1，假定生成多項式為 g(x)=g0x0+g1x1+…+gn-k-2xn-k-2+gn-k-1xn-k-1，則碼字表達式如下:

可以看出，校驗位是由-m(x)xr對g(x)求模得到，由于二進制BCH的碼元都取自二元域GF（2），在二元域中減法操作等同于加法操作，因此碼字表達式也可以寫成下式:

BCH碼的編碼過程就是一次有限域的模乘運算 m(x)xrmod g(x)，可以利用LFSR 電路實現［11］。一般的串行LFSR電路，在每個時鐘周期只能輸入1位數據，對于數據端口為16位的NAND Flash存儲器來說，這就意味著編碼的速率只有數據端口速率的1/16，為了等待編碼，數據寫入的速率不得不降低到原來的1/16。因此，為了提高編碼速度，將一般的串行LFSR電路改為16位并行，即在每個時鐘周期可以輸入16位數據，正好等于數據端口的速率，這樣編碼過程就與數據的寫入完全同步，最后一個字節寫入后，編碼也隨之結束如圖3所示。

圖3 并行化的線性反饋移位寄存器

2.2 解碼器設計

解碼模塊包括三個子模塊，分別是伴隨式計算模塊、錯誤位置多項式計算模塊和Chien搜索模塊［12］，在一次解碼過程中，這三個子模塊只能順序執行，不能使用流水線操作。所以本設計采用把NAND Flash的每頁都均勻的劃分為四組子頁的方法，使每組子頁都有數據區和校驗區，并且不同組的數據的解碼過程沒有任何聯系，使得三個子模塊可以采用3級流水線模式工作。第一級是伴隨式計算模塊，第二級是錯誤位置多項式計算模塊，第三級是Chien搜索模塊，這樣提高了糾正速度。除此之外，在解碼完成后，解碼模塊能夠檢測出錯位是否被全部校正，以及出錯位的數量是否超過了設計的校正能力。三級流水線結構如圖4所示。

圖4 三級流水線結構

2.2.1 伴隨式計算

設解碼模塊接收到的信息多項式為

接收端接收到的碼元多項式為

錯誤多項式為

則有:

設ai(i=0,1,2,…,2t)是生成多項式 g(x)的根，其中t為最大糾錯位數，伴隨式的計算就是將ai代入接收到的碼元多項式R(x)中，求出R(ai)的值，si=R(ai)，若計算得到的si的值全部為0，則認為信息在傳輸過程中沒有發生錯誤，否則為發生錯誤。由此可得伴隨式多項式:

2.2.2 錯誤位置多項式計算

設錯誤位置多項式為

要求的就是錯誤位置多項式的系數?i（i=0，1…，t），而錯誤位置多項式?(x)與伴隨式多項式S(x)存在如下關系:

代入關鍵方程可得:

由上式可知，關鍵方程的奇次項系數都為0，偶次項系數未知，所以可將迭代次數減少為t次，把經過簡化的伯利坎普-梅西算法稱之為簡化的無求逆伯利坎普-梅西算法，其迭代過程如下。

2）j=j+2 ，判斷 dj是否等于0，若是則轉3），否則轉4）；

6）判斷 j是否等于2t-2，是則終止迭代，否則轉到2）繼續迭代。

2.2.3 Chien搜索

上一步求出了錯誤位置多項式:

Chien搜索算法的基本思路是通過遍歷的方法求解錯誤位置多項式的根，要確定第k位是否為出錯位，只需將a-k代入?(x)，然后判斷?(x)是否為0，若為0則證明第k位是出錯位，否則，不是出錯位。

3 設計仿真驗證

用verilog語言完成BCH編解碼電路的RTL級設計，并用Questasim完成仿真驗證。編碼模塊主要完成校驗位的計算，校驗位為672位。伴隨式計算模塊主要完成伴隨式的計算，伴隨式為96組，每組為14位。錯誤位置多項式計算模塊主要完成錯誤位置多項式系數的計算，Chien搜索模塊主要完成錯誤位置多項式根的計算。仿真驗證結果表明:在人為注入48位出錯位后，電路可以正確地對所有出錯位完成校正。

4 ASIC設計綜合

使用SMIC 0.11μm工藝庫，工藝角為tt，溫度為25℃，借助Synopsys公司的DC工具完成電路綜合，當工作頻率為200MHz時，面積為716520μm2，功耗為479mW。性能比較如表1，可以看出本文設計的BCH編解碼器數據容量最大，可校正位數最多，工作頻率最高，功耗優于文獻［14］，次于文獻［13］。由于電路功耗主要來源于時鐘單元、運算單元和存儲單元，對于本設計而言，時鐘頻率高，運算復雜，存儲容量大，所以電路功耗相對較大。

表1 性能比較

5 結語

本文在分析BCH編解碼原理的基礎上，提出一種優化的BCH編解碼設計，用于汽車電子存儲NAND Flash的校驗，所設計的BCH編解碼器最大可糾錯48位，提高了NAND Flash中數據存儲的可靠性。完成電路的功能仿真和DC綜合，分析電路性能可知，優化后的設計在校正位數、工作頻率和電路功耗方面都有很大的改善，為了得到更好的糾錯性能，今后將會對算法做進一步的優化，平衡工作頻率和電路功耗之間的關系，使得電路延時達到最小并且功耗最低。