閃存控制器中BCH編解碼器設計和驗證

殷 民， 易 波

(中國科學技術大學 微電子與固體電子實驗室，安徽 合肥230001)

0 引言

隨著生產工藝的進步和諸如智能手機平板電腦、SSD等消費電子市場對高密度非易失性存儲的需求，MLC代替 SLC成為閃存市場的主流趨勢。與此同時，MLC伴隨的多比特隨機錯誤，對系統的數據可靠性提出新的挑戰，例如美光(Micron)的MT29F32G08CBABA系列要求每 540 Byte有 12 bit的糾錯能力。SLC中常用的 SEC-DEC編解碼已經不再適用，新一代的閃存控制器需要使用糾錯能力更強大的BCH編解碼。

BCH碼取自Bose、Ray-Chaudhuri與 Hocquenghem的縮寫，是編碼理論尤其是糾錯碼中研究得比較多的一種編碼方法，它的代數結構優美，硬件實現簡單，廣泛應用于通信行業和信息存儲。BCH的解碼過程通常分為伴隨子計算、關鍵方程求解、錢搜索驗根這3個部分，在眾多關鍵方程求解算法中，簡化伯利坎普-梅西算法最為有效。

雖然很多文獻中分別實現了閃存控制的BCH編解碼，不過這些大多不適合當前閃存控制器，主要原因是，糾錯能力太低,不符合閃存芯片的要求。例如文獻[1-4]分別實現 4 bit/512 Byte、8 bit/512 Byte、2 bit/21 bit、4 bit/223 bit的糾錯能力，遠遠低于美光系列每540 Byte/12 bit糾錯要求。另外，關鍵方程算法實現主要是歐幾里德方法，或是最初的 iBM，無論是從面積還是譯碼延遲考慮，這些算法并不是最優的算法。本設計中還對碼長作了靈活的配置，提供幾種可選的碼率，只需要在錢搜索中做簡單地修改。碼長靈活配置是由于軟件算法實現的時候，希望把某些關鍵數據存儲在閃存的剩余空間，這些關鍵數據也希望和普通的數據一樣受到ECC的保護，而這些數據長度較短，不同于主要數據部分。具體實現時只需要在錢搜索中做相應的修改。

本設計實現8 bit并行編解碼，每1 024 Byte能糾正32 bit的隨機錯誤，冗余位56 Byte，可以應用于美光MT29F32G08CBABA等系列。

1 并行編碼器

并行編解碼雖然提高硬件復雜度，但能夠降低系統工作頻率，提高數據帶寬。8 bit的并行編解碼非常適合閃存應用。作為循環碼，BCH(n, k)的碼字由生成多項式決定，并且可以寫成系統模式，也就是說，碼字是通過原始消息和冗余效驗位級聯組成。BCH的碼字u(x)是由生成多項式決定的：

反饋矩陣F第i行是xi+R除以 g(x)的余式的系數，也就是說，高比特的系數移位后，超過 g(x)次數，對低比特產生影響。電路實現如圖1所示。

2 并行伴隨子生成電路

BCH譯碼的第一步是計算接收向量的伴隨子，伴隨子的計算和編碼過程非常相似。對接收向量r(x)，有：

式中，φi(x)是以αi為根的最小多項式，這樣，求伴隨子的過程就轉為求余式b(x)，然后再代入αi，得到伴隨子。該做法好處是，在伽羅華域 GF(2M)中，αi, αj(i=j 2l)的最小多項式相同，對應余式b(x)也就相同，這樣可以復用求余式 b(x)部分邏輯。將編碼過程中生成多項式g(x)換成φi(x)，并注意到輸入是從左邊進入反饋移位寄存器的，就得到伴隨子生成電路，圖2是一個φi(x)的求余過程和相應伴隨子計算電路。

此外，伴隨子的計算電路也可以直接實現

S=rαi(n-1)+rαi(n-2)+ ···+rαi+r，

in-1n-210這樣不難得到串行伴隨子計算電路和并行的伴隨子計算電路如圖3所示。圖3(a)是串行的伴隨子計算電路，圖3(b)是并行的伴隨子計算電路。

3 關鍵方程

關鍵方程S( x)Λ(x)=Ω(x)modx2t解法很多，主要算法比較如表1所示。

表1 主要算法比較

文獻[5]中SiBM算法是文獻[6]中RiBM算法在2進制 BCH碼上的優化，優化包括兩個方面，一是奇次迭代差異為零,可以忽略奇次迭代,二是沒有必要計算錯誤多項式Ω(x)的系數。SiBM-2是采用Folding結構，分時復用邏輯，所以它的邏輯幾乎是SiBM算法的一半，但譯碼的延遲變為兩倍。在這里的設計中，更關注譯碼的延遲對系統性能的改善，而不是面積上的考慮，所以采用SiBM算法。算法偽碼如下所示：

Initialization:

在該算法中，涉及到伽羅華域 GF(2M)乘法運算。乘法器可以通過線性反饋移位寄存器實現，作為時序邏輯，雖然面積最優，不過會增加M個時鐘延遲，也可以通過組合邏輯實現。在這里的設計中，采用文獻[7]中的乘法器設計，該設計將有限域上乘法運算分為普通乘法運算網絡和反饋網絡，并在面積和延遲上權衡，延遲數量級O(lb(M))。

在SIBM算法電路實現上，首先是定義最小處理單元，它是用來計算下次迭代的θ, δ值。最小處理單元實現和SIBM算法實現電路如圖4所示。

圖5是SIBM算法的直接實現。此外，文獻[5]還討論了2-FOLDING和T-FOLDING的實現形式，面積分別減少2、T倍，但會增加譯碼的延遲時間也會增加相應的倍數。

4 并行錢搜索電路

錢搜索是從高位開始驗根，如果λ( αi)==0，表明 i位置為錯誤位置，需要將該比特求反。由于在閃存控制器中，數據都是Byte為單位存儲，是縮短的BCH(n, k)碼，驗根不是從2M-1開始，而是從n開始，所以要用λ?i=(α^((2M-1-n) i ))·λi代替λi，代入錢搜索中，如圖6所示。對不同的碼率n,相應λ?i/λi=α^((2M-1-n) i )的會不同，為實現多碼率，可以根據碼率，選擇相應的乘法系數，根據乘法系數得到該碼率對應的λ?i，再代入錢搜索電路。

在錢搜索中， 由于乘法器都是固定系數的，可以進行面積優化，文獻[8]給出優化的算法，然而，面積的優化將會增加乘法器的延遲，使其從O(lb(M))增加為O(M)。時序分析表明，圖6中從λi輸入，經過乘法器轉化為λi，通過選通器再經過一個乘法器，和另外的32個λi相異或輸出，這是個關鍵路徑，可以通過Pipeline的操作，改善時序。

5 仿真綜合

這里是使用System Verilog搭建驗證環境，將編解碼器對接，并利用約束隨機，在信道上產生不多于32 bit的隨機錯誤，生成不同的激勵，并判斷解碼器能否正確的糾正錯誤。實際仿真證明文中的設計能夠每1 024 Byte信息量糾正不超過 32 bit的隨機錯誤。典型的VCS的仿真時序圖如圖7所示(由于波形太大，只列出示意圖)。首先，讀取閃存中信息，寫入解碼器中，共需1 080個時鐘周期，信息位使用1 024個時鐘周期，冗余校驗位使用56個時鐘周期；其次利用 SiBM求解關鍵方程，共需32個時鐘周期；最后，從解碼器中讀取糾正后信息，共需 1 024個周期。此外，BCH解碼器可以和 CRC校驗級聯，用于發現錯誤多于32 bit的情況。

這里使用TSMC 90 nm工藝庫綜合，在輸入延遲70%、輸出 30%的約束下，提出的設計可以工作在200 MHz，面積0.445 mm2，典型的功耗7.8 mW。

6 結語

文中結合實際的項目經驗，闡述BCH編解碼設計中的設計思想和一些重要的細節。提出的設計相對于其他的設計，主要特點有：首先，提出的設計采用并行的編解碼，在相同的系統頻率下，可提高譯碼帶寬；其次，在關鍵方程求解電路中，采用SiBM算法，極大地減小編碼器面積；最后，在錢搜索前加入乘法邏輯，可以容易地實現多碼率。該BCH編解碼器已經成功地應用閃存控制器中，其強大的糾錯能力，滿足目前市場上主流FLASH的可靠性需求。并在此感謝記憶科技蘇州研究院 IC部門同事給予的技術上支持。

[1] 李璐,周海燕. 一種含BCH編解碼器的控制器的SLC/MLC NAND FLASH控制器的 VLSI設計[J]. 現代電子技術,2009, 32(07): 167-170.

[2] 王杰,沈海斌. NAND Flash 控制器的 BCH編/譯碼器設計[J]. 計算機工程, 2010, 16(36): 222-225.

[3] 寧楠,宋文妙. 一種基于FPGA的糾錯編碼器的設計和實現[J]. 通信技術, 2008, 41(08): 95-97.

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

[5] LIU W, JUNRYE R, SUNG W Y. Low Power High throughput BCH Error Correction VLSI Design for Multi level Cell NAND FI ASH Memorie[C]//IEEE. Signal Processing Systems Design and Implementation.Canada: IEEE Signal Processing Society, 2006:303-308.

[6] SARWATE D V, SHANBHAG N R. High-speed Architectures for Reed-Solomon Decoders[J]. IEEE Trans. on Very Large Scale Integration,2001, 9(05): 641-655.

[7] REYHANI-MASOLEH A, HASAN M A. Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2)[J]. IEEE Trans. on Computers,2004, 53(08): 945-959.

[8] PAAR C. Optimized Arithmetic for Reed-Solomon Encoders[C]//IEEE.1997 IEEE InternationaSymposium on Information Theory.Germany: IEEE,1997:250.