殷 民， 易 波

(中國(guó)科學(xué)技術(shù)大學(xué) 微電子與固體電子實(shí)驗(yàn)室，安徽 合肥230001)

0 引言

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

BCH碼取自Bose、Ray-Chaudhuri與 Hocquenghem的縮寫(xiě)，是編碼理論尤其是糾錯(cuò)碼中研究得比較多的一種編碼方法，它的代數(shù)結(jié)構(gòu)優(yōu)美，硬件實(shí)現(xiàn)簡(jiǎn)單，廣泛應(yīng)用于通信行業(yè)和信息存儲(chǔ)。BCH的解碼過(guò)程通常分為伴隨子計(jì)算、關(guān)鍵方程求解、錢(qián)搜索驗(yàn)根這3個(gè)部分，在眾多關(guān)鍵方程求解算法中，簡(jiǎn)化伯利坎普-梅西算法最為有效。

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

本設(shè)計(jì)實(shí)現(xiàn)8 bit并行編解碼，每1 024 Byte能糾正32 bit的隨機(jī)錯(cuò)誤，冗余位56 Byte，可以應(yīng)用于美光MT29F32G08CBABA等系列。

1 并行編碼器

并行編解碼雖然提高硬件復(fù)雜度，但能夠降低系統(tǒng)工作頻率，提高數(shù)據(jù)帶寬。8 bit的并行編解碼非常適合閃存應(yīng)用。作為循環(huán)碼，BCH(n, k)的碼字由生成多項(xiàng)式?jīng)Q定，并且可以寫(xiě)成系統(tǒng)模式，也就是說(shuō)，碼字是通過(guò)原始消息和冗余效驗(yàn)位級(jí)聯(lián)組成。BCH的碼字u(x)是由生成多項(xiàng)式?jīng)Q定的：

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

2 并行伴隨子生成電路

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

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

此外，伴隨子的計(jì)算電路也可以直接實(shí)現(xiàn)

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

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

3 關(guān)鍵方程

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

表1 主要算法比較

文獻(xiàn)[5]中SiBM算法是文獻(xiàn)[6]中RiBM算法在2進(jìn)制 BCH碼上的優(yōu)化，優(yōu)化包括兩個(gè)方面，一是奇次迭代差異為零,可以忽略奇次迭代,二是沒(méi)有必要計(jì)算錯(cuò)誤多項(xiàng)式Ω(x)的系數(shù)。SiBM-2是采用Folding結(jié)構(gòu)，分時(shí)復(fù)用邏輯，所以它的邏輯幾乎是SiBM算法的一半，但譯碼的延遲變?yōu)閮杀?。在這里的設(shè)計(jì)中，更關(guān)注譯碼的延遲對(duì)系統(tǒng)性能的改善，而不是面積上的考慮，所以采用SiBM算法。算法偽碼如下所示：

Initialization:

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

在SIBM算法電路實(shí)現(xiàn)上，首先是定義最小處理單元，它是用來(lái)計(jì)算下次迭代的θ, δ值。最小處理單元實(shí)現(xiàn)和SIBM算法實(shí)現(xiàn)電路如圖4所示。

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

4 并行錢(qián)搜索電路

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

在錢(qián)搜索中， 由于乘法器都是固定系數(shù)的，可以進(jìn)行面積優(yōu)化，文獻(xiàn)[8]給出優(yōu)化的算法，然而，面積的優(yōu)化將會(huì)增加乘法器的延遲，使其從O(lb(M))增加為O(M)。時(shí)序分析表明，圖6中從λi輸入，經(jīng)過(guò)乘法器轉(zhuǎn)化為λi，通過(guò)選通器再經(jīng)過(guò)一個(gè)乘法器，和另外的32個(gè)λi相異或輸出，這是個(gè)關(guān)鍵路徑，可以通過(guò)Pipeline的操作，改善時(shí)序。

5 仿真綜合

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

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

6 結(jié)語(yǔ)

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

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

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

[3] 寧楠,宋文妙. 一種基于FPGA的糾錯(cuò)編碼器的設(shè)計(jì)和實(shí)現(xiàn)[J]. 通信技術(shù), 2008, 41(08): 95-97.

[4] 張彥,李署堅(jiān)，崔金.一種 BCH碼編譯碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù),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.