高性能超低延遲BCH譯碼器電路結(jié)構(gòu)設計

楊宇恒， 劉海洋， 李金海， 原青， 劉建(中國科學院 微電子研究所， 北京 100029)

隨著工藝尺寸的不斷縮小，集成電路在成品率和可靠性等方面臨著諸多問題[1]。對于處理器而言，存儲器是重要的組成部分，存儲器與處理器的可靠性高度相關(guān)，決定了處理器是否能夠得到正確的指令或數(shù)據(jù)。處理器中常用的存儲器有靜態(tài)隨機存儲器(static random-access memory，SRAM)和閃存等，為了提高存儲器的可靠性，采用冗余設計的診斷或糾錯方法[2-4]，效率最高的容錯設計是糾錯碼(error correction code, ECC)方案，用于檢測和糾正存儲器中的錯誤[5-6]。目前，存儲器的ECC方案中最常用的是(bose-chaudhuri-hocquenghem，BCH)碼，雖具有于多比特糾錯能力[7]，但應用于處理器也存在許多問題[8]。首先，BCH碼的糾錯能力有限，當存儲器中的錯誤比特數(shù)超出BCH碼的糾錯能力時，譯碼器無法保證正確的譯碼輸出，處理器可能得到錯誤指令或數(shù)據(jù)[9]。另外，由于處理器是根據(jù)存儲器中的指令運行的，因此，對譯碼延遲和吞吐率要求較高，否則將影響處理器的執(zhí)行效率，隨著信息位長度的增加，譯碼過程中需要存儲規(guī)模較大的元素查找表，將大幅提升處理器的面積成本。

針對處理器中的閃存類型存儲器，本文提出了一種具有低譯碼延遲的適用于處理器的BCH譯碼器結(jié)構(gòu)，用于提高處理器的可靠性，以獨立的有限域運算單元代替了譯碼算法中的查表結(jié)構(gòu)[10]，縮減了譯碼器電路面積，此外，通過對譯碼算法迭代過程的優(yōu)化，使用逆向錯誤搜索電路，降低了譯碼器的延遲。

1 BCH譯碼算法

假設α是有限域GF(2m)的本源元，則糾錯能力為t的BCH碼C的生成多項式g(x)是以α、α2、α3、…、α2t為根的最低次多項式：

g(x)=LCM(g1(x),g2(x),…,g2t(x))

(1)

式中：LCM表示若干多項式的最小公倍式。

BCH碼C的參數(shù)應滿足：1)碼字長度n=2m-1；2)維度數(shù)量k=n-mt；3)最小距離d≥2t+1。

在實際應用中，信息序列的碼字長度往往不能滿足上述形式，一般通過對信息序列補零的形式，以滿足對BCH編碼對碼字長度的要求，進而進行編碼，編碼后的數(shù)據(jù)再刪除數(shù)據(jù)段補充的零比特，形成最終編碼后的碼字。

BCH碼的譯碼過程可簡述如下：假設C的碼字為c=(c0,c1,…,cn-1)，其對應的多項式為：

c(x)=c0+c1·x+…+cn-1·xn-1

(2)

同時，假設在數(shù)據(jù)的讀取過程中可能產(chǎn)生的錯誤為：

e(x)=e0+e1·x+…+en-1·xn-1

(3)

實際的讀取過程中的接收序列可表示為：

r(x)=c(x)+e(x)

(4)

對于糾錯能力為t的BCH碼，其2t個伴隨式為：

Si=r(αi), 1≤i≤2t

(5)

式中：αi為有限域GF(2m)的元素，通常以位寬為m、深度為n的查找表的方式實現(xiàn)。

假定接收序列中v(v≤t)個位置出現(xiàn)錯誤，可定義錯誤位置多項式為：

(6)

式中σi為有限域GF(2m)的元素，σ0=1。

BCH的譯碼過程就是根據(jù)2t個伴隨式Si(1≤i≤2t)求解上述錯誤位置多項式σ(x)的過程，進而通過σ(x)的根找到錯誤位置，即σ(x)的所有根表示碼字中的錯誤位置。

圖1 BCH譯碼算法流程Fig.1 The flowchart of BCH decoding process

在圖1所示的BCH碼譯碼算法中，錯誤位置多項式計算是復雜度最高的部分，通常采用Berlekamp-Massey(BM)算法實現(xiàn)。該算法需要對元素αi進行求逆運算(αi)-1=αn-i。通常元素求逆運算可以通過查表的形式實現(xiàn)，在信息序列長度較小的譯碼器設計中，查找表的規(guī)模較小，可以通過簡單的地址映射完成元素求逆運算。當信息序列長度較大時，查找表的規(guī)模在硬件實現(xiàn)中是難以接收的，例如，對于4 096 bit信息位的BCH碼，需要深度8 191的元素查找表。而根據(jù)GF(2m)的運算規(guī)則αi·αj=αi+j可知，元素求逆計算也可以實時計算生成，但譯碼延遲將會顯著增加，難以適應譯碼在處理器應用中的低譯碼延遲的需求。

相對于標準的BM算法，避免求逆的BM算法的譯碼過程是一個迭代過程，避免有限域的元素求逆運算，能夠有效減少迭代過程中的運算量，以及減少電路面積成本，易于硬件實現(xiàn)。避免求逆的BM譯碼算法的實現(xiàn)步驟為：

初始化：σ0(x)=1，β0(x)=x，θ0=1，L0=0，j=1。

步驟1)：通過式(7)計算Δj，其中Sj為伴隨式：

(7)

步驟2)：根據(jù)Δj和變量L判斷變量δ：

(8)

步驟3)：更新錯誤位置多項式σj(x)以及中間變量βj(x)為：

σj(x)=θj-1σj-1(x)-Δjxβj-1(x)

(9)

βj(x)=δσj-1(x)+(1-δ)xβj-1(x)

(10)

步驟4)：根據(jù)式(11)和式(12)更新中間變量θj和Lj為：

θj=δΔj+(1-δ)θj-1

(11)

Lj=δ(j-Lj-1)+(1-δ)Lj-1

(12)

步驟5)：若j=2t停止；否則置j←j+1，返回步驟1)。

在避免求逆的BM譯碼算法中，錯誤位置多項式σ(x)的更新過程是計算復雜度最高的部分，其更新過程如圖2所示。

圖2 錯誤位置多項式求解流程Fig.2 Solution process of error location polynomial

在更新σ(x)后，對σ(x)=0進行求解得到v個根，σ(x)可分為：

σ(x)=(1+β1x)(1+β2x)…(1+βvx)

(13)

βk=αjk,k=1,2,…,v

(14)

由于在有限域的運算中α-jk=αn-jk，因此σ(x)=0的根與接收序列r(x)中錯誤位置之間應滿足若σ(αj1)=0，則r(x)中的第n-j1比特為實際的錯誤位置。即通過對σ(x)=0求解找到的v個根，即為接收序列r(x)中實際產(chǎn)生的v個錯誤位所對應的位置。

通過上述對譯碼過程的描述中可以看到，在錯誤位置搜索階段，當前參與計算的元素序號與對應的搜索碼字序號通過n-j1對稱，如果按照標準譯碼算法進行順序搜索，譯碼器的首個有效輸出位將延遲約n/2個譯碼周期，譯碼數(shù)據(jù)將逆序輸出。以本文的設計為例，根據(jù)NAND-FLASH的存儲器特點，以扇區(qū)為基本的存儲單元，每個扇區(qū)對應512 bit，則編碼的信息位字長為4 096 bit，順序搜索方式將導致2 048個周期的譯碼延遲。另外，根據(jù)式(6)中的描述，BCH碼的糾錯能力為t，當錯誤比特的數(shù)量v>t時，譯碼器將無法糾正碼字中的全部錯誤位，甚至得到錯誤的譯碼信息。

為盡量降低譯碼器的延遲，以滿足處理器的應用需求，本文對上述譯碼算法進行了改進，根據(jù)GF(2m)的運算規(guī)則α-i=αn-i和αn·α-i=αn-i可知，對錯誤位置進行逆序搜索，使譯碼器能夠產(chǎn)生正序的譯碼輸出，并且，對比于原始譯碼算法，譯碼器能夠減少約n/2個周期的譯碼延遲。

另外，為提高譯碼器電路的可靠性和數(shù)據(jù)利用率，本文對信息位中加入了CRC校驗。采用分段校驗的方式，具有以下2個優(yōu)點：1)當實際讀取的碼字中錯誤位大于t時，BCH譯碼器無法產(chǎn)生正確譯碼結(jié)果，則可通過CRC校驗對譯碼后數(shù)據(jù)進行二次校驗，確定譯碼器的輸出的正確性；2)碼字中的錯誤位可能隨機產(chǎn)生在信息位的任意位置，采用分段CRC校驗的方式，能夠使處理器分別識別每段數(shù)據(jù)的正確性，單獨讀取正確數(shù)據(jù)段的信息位，提高數(shù)據(jù)的利用率。

2 BCH譯碼器電路實現(xiàn)

2.1 譯碼器電路實現(xiàn)

編碼后的數(shù)據(jù)格式如圖3中所示，其中最大糾錯能力t設定為9，即最多能夠糾正隨機分布的9 bit錯誤。首先，將長度為4 096 bit的信息序列分為4段，每段長度為1 024 bit。然后，對于每段信息序列，分別通過CRC-16校驗產(chǎn)生16 bit的CRC校驗位，將4段信息比特和CRC校驗比特一起組成4 160 bit數(shù)據(jù)，最后補充3 914 bit，經(jīng)過BCH編碼，得到117 bit BCH校驗位后，刪除補充的零比特形成最終的編碼數(shù)據(jù)格式。

圖3 輸入數(shù)據(jù)編碼格式Fig.3 Encoding format of input data

圖4為本文提出的BCH譯碼器的整體電路結(jié)構(gòu)。主要由桶形移位寄存器，伴隨式生成器，錯誤位置多項式生成器，錯誤位置搜索和CRC-16校驗電路以及必要的控制邏輯組成。

圖4 譯碼器整體結(jié)構(gòu)Fig.4 Structure of proposed decoder circuit

譯碼器輸入數(shù)據(jù)的組織格式與圖3中一致，在電路的結(jié)構(gòu)上，為減少譯碼器的電路面積成本，針對GF(2m)的運算規(guī)則，以實時計算αi的方式代替了譯碼算法中的元素查找表，在圖4中對應為寄存器和有限域乘法器組成的累乘結(jié)構(gòu)，而有限域乘法可以通過異或門和與門級聯(lián)實現(xiàn)，以圖3中伴隨式生成電路為例，其中包含18條伴隨式計算支路，每條支路包括8組累乘單元，共144個累乘單元用于實時計算αi參數(shù)表，每個累乘單元的規(guī)模僅為37個門電路。而采用查找表的形式則需要8 191×13=106 483個寄存器，相同的累乘結(jié)構(gòu)，也應用于圖4中錯誤位置搜索電路中用于實時計算元素表，因此，本文采用的實時計算αi的電路結(jié)構(gòu)大幅縮減了譯碼器的電路面積。另外，為提高譯碼器的吞吐率和較少譯碼延遲，圖4中的桶形移位寄存器也采用了乒乓結(jié)構(gòu)，可將譯碼器的吞吐率提升一倍，以適應在高速處理器中的應用需求。

譯碼器的工作時序如圖5中所示，共分為3個階段：1)待譯碼數(shù)據(jù)以8 bit為一組向移位寄存器R1中填充，同時，圖4中的18條伴隨式計算支路同步接收輸入數(shù)據(jù)，并根據(jù)式(5)計算各支路對應的伴隨式，在一個機器周期內(nèi)，每條支路同時計算8 bit數(shù)據(jù)，當全部535 bit數(shù)據(jù)輸入R1后，同時得到18個伴隨式S1～S18；2)啟動錯誤位置多項式生成電路，經(jīng)過23個機器周期后，生成錯誤位置多項式σ0～σ9；3)啟動錯誤位置搜索和校驗電路，同時，桶形移位寄存器持續(xù)移位，將R1中數(shù)據(jù)順序彈出，并根據(jù)σ(αj1)是否為零，對錯誤位進行糾錯。

當搜索過程遍歷全部535 bit數(shù)據(jù)后，譯碼過程結(jié)束，通過圖5中對譯碼器工作時序的描述可以看到，本文提出的譯碼器結(jié)構(gòu)完成一次譯碼流程共需要消耗558個機器周期，其中，在錯誤位置搜索和校驗階段，下一組待譯碼數(shù)據(jù)可以向R2中同步填充，即除錯誤位置多項式的計算階段需要消耗獨立的23個機器周期外，其余譯碼過程可實現(xiàn)全流水線操作，大幅提高了譯碼器的吞吐率。

分析圖4中桶形移位寄存器的特點與譯碼器的工作時序可以看到，僅保留一組移位寄存器，譯碼器也能夠保持相同的吞吐率，即在譯碼器執(zhí)行錯誤位置搜索和校驗操作時，下一組待譯碼數(shù)可以由R1的底部逐比特向上填充，而原數(shù)據(jù)則可以同步由R1頂部向上逐比特彈出，同時，譯碼后的數(shù)據(jù)由圖4中輸出端口A同步輸出。雖然采用單一移位寄存器的結(jié)構(gòu)能夠有效降低譯碼器的面積與動態(tài)功耗，但在處理器的應用中會存在2方面問題：1)為充分保證移位寄存器中數(shù)據(jù)的正確性，譯碼器的讀/寫時鐘必須同步，處理器內(nèi)部總線的效率將會收到限制；2)譯碼信息必須等待全部碼字譯碼結(jié)束后才能得到，例如：錯誤數(shù)量和分段CRC-16的校驗結(jié)果，由于BCH碼的局限性，可能無法完全糾正碼字中的錯誤，導致在處理器在執(zhí)行應用程序時可能會接收到錯誤數(shù)據(jù)，從而導致不可恢復的錯誤執(zhí)行結(jié)果。

圖5 BCH譯碼工作時序Fig.5 Operation timing of BCH decoder

而使用乒乓結(jié)構(gòu)的桶形移位寄存器一方面能夠有效解決讀/寫時鐘的同步問題；另一方面，由于輸入碼字的數(shù)據(jù)段采用了分段式CRC-16的組織結(jié)構(gòu)，即使在BCH譯碼器無法糾正碼字中全部錯誤位的情況下，也能夠在處理器讀取譯碼信息后，分別判斷4段CRC-16的校驗情況，選擇4段數(shù)據(jù)中無錯誤位的數(shù)據(jù)，提高譯碼后數(shù)據(jù)的利用效率。

分析式(7)～(12)可以看到，根據(jù)Δj與Lj的取值，錯誤位置多項式σ(x)的計算過程可分解為2個獨立的更新過程，其電路結(jié)構(gòu)如圖6所示。

圖6 σ更新結(jié)構(gòu)Fig.6 σ update structure

根據(jù)式(9)與式(10)的更新迭代過程，當δ=1時，βj(x)=σj-1(x)，此時，中間變量βj(x)的更新過程可通過寄存器直接賦值的形式實現(xiàn)，即將σj-1(x)寄存器組的數(shù)據(jù)直接賦值給β(x)寄存器組；當δ=0時，βj(x)=xβj-1(x)，此時，β(x)的更新過程表現(xiàn)為β(x)寄存器組的向上循環(huán)移位過程。上述更新過程與圖6中的β(x)寄存器組和選通器結(jié)構(gòu)對應，其中，選通器的控制信號為δ。

根據(jù)Δj的狀態(tài)，圖6中σ(x)的更新過程可表示為有限域乘法或有限域乘累加的運算，因此，圖6中σ(x)寄存器組對應的選通器控制信號為Δj的取值狀態(tài)，當Δj=0時，選通器控制信號為0，反之，則為1。

在譯碼器的錯誤位置搜索階段，為求σ(x)的所有解，需要遍歷8 191個元素表，為適應處理器的設計需求以及FLASH的時序規(guī)范，在本文設計的譯碼器電路中以bit為單位進行讀寫操作，因此，在圖4所示的結(jié)構(gòu)中，錯誤位置搜索電路包含8條計算支路，每條計算支路具有相同的電路結(jié)構(gòu)，如圖7中所示。

根據(jù)式(6)與有限域運算規(guī)則可知，圖7中以有限域乘法級聯(lián)的結(jié)構(gòu)實現(xiàn)了式(6)的計算過程，并且，每條支路中以有限域乘法器和寄存器組成的累乘結(jié)構(gòu)實現(xiàn)了逆向的搜索過程，其中，對于每條支路，元素系數(shù)僅包含通過寄存器的復位值固化初始化系數(shù)α-k(k∈[1,8])和固定的計算間隔系數(shù)α-8，在完整的計算過程中，僅需要保留8個元素系數(shù)，避免了8 191個元素表的存儲，大幅縮減了譯碼器的電路面積。

圖7 錯誤位置搜索支路Fig.7 Error location search branch

通過量化分析，說明圖7中所示的錯誤位置搜索電路對整體譯碼器電路面積成本的縮減效果，根據(jù)本文設計的譯碼器參數(shù)，糾錯能力t=9，包含分段CRC-16校驗的信息位的總長度為4 160 bit。在標準的BM譯碼算法中，對應的元素αi查找表的深度為8 191，元素二進制表示的位寬為13位。而本文提出的錯誤位置搜索電路避免了元素查找表的使用，可減少8 191×13 bit的存儲器資源。以65 nm低功耗工藝為例，即使采用SRAM存儲作為元素查找表，也需要89 430.14 μm2的電路面積，約為35 489個等效門電路，因此，圖7中的錯誤位置搜索電路對譯碼器面積成本的縮減是顯著的，而對比于其它采用寄存器作為元素存儲的譯碼器電路，本文提出的錯誤位置搜索結(jié)構(gòu)在面積成本方面的收益將更加明顯。

圖7中所示的錯誤位置搜索電路在降低譯碼器電路面積的同時，也大幅提高了譯碼器的吞吐率，以及極大降低了譯碼延遲。為更清晰的說明圖7中電路在譯碼延遲方面的優(yōu)勢，圖8中給出了在錯誤位置搜索階段，本文提出的譯碼器電路的工作時序與標準BM譯碼算法的搜索時序的對比情況。

在圖8中可以看到，在標準的譯碼算法中使用Chien搜索算法，根據(jù)式(13)與(14)的推導結(jié)果，由于σ(αj1)=0對應接收序列r(x)中的第n-j1比特的實際錯誤位置，因此，譯碼器在前3 915個機器周期內(nèi)得到的錯誤位置搜索結(jié)果無法與實際接收序列r(x)中的信息位對應，從而無法得到正確的譯碼結(jié)果。而在3 915個機器周期后，錯誤位置搜索電路經(jīng)過順序搜索得到的結(jié)果與r(x)中n-j1對應，即采用標準的BM譯碼算法此時得到的譯碼結(jié)果是倒序輸出的，如果得到最終的完整的正序譯碼結(jié)果，則需要等待錯誤位置搜索過程結(jié)束，如圖8中所示，共需要至少8 191個機器周期，這將使譯碼器的譯碼延遲大幅增加，降低譯碼器的吞吐率以及實時性，另外，也需要額外的緩存電路接收逆序輸出的結(jié)果。

圖8 錯誤位置搜索時序?qū)Ρ菷ig.8 Timing comparison of error location search

如圖8中所示，對比于標準BM譯碼算法中的搜索過程，圖7中所示的結(jié)構(gòu)利用有限域的運算規(guī)則：α-i=αn-i和αn·α-i=αn-i，實現(xiàn)了錯誤位置搜索電路，具體的說，以α-i=αn-i的對稱關(guān)系，在搜索過程中以αn=αn-1·α-i代替了αn=αn-1·αi，其中，n表示順序搜索的序號，-i表示圖7所示結(jié)構(gòu)所組的成各支路中寄存器的初始元素的冪次，α0=α-i，因此，結(jié)合圖8中給出的搜索時序，以及根據(jù)α-i=αn-i，可以看到圖7中的搜索電路結(jié)構(gòu)可直接輸出與r(x)序列對應的搜索結(jié)果，并得到的譯碼結(jié)果是正序輸出的。因此，本文提出的錯誤位置搜索電路能夠降低至少3 915個機器周期，搜索階段的延遲周期為0，大幅降低了譯碼器的譯碼延遲。另外，結(jié)合圖4中的整體譯碼器的電路結(jié)構(gòu)也能夠看到，本文提出的譯碼器能夠在不增加額外緩存電路的情況下直接由輸出端口輸出譯碼結(jié)果，并且，由于圖7中的搜索電路采用了并行結(jié)構(gòu)，可同時搜索8個錯誤位置，也進一步提高了譯碼器的吞吐率。

2.2 實現(xiàn)結(jié)果與對比

為得到準確的評估結(jié)果，本文采用65 nm工藝對所提出的譯碼器電路進行了邏輯綜合，綜合條件為最差工藝角：電壓1.08 V，溫度125 ℃，時鐘頻率為200 MHz。面積綜合結(jié)果為436 333.323 μm2，約為125 819等效門，動態(tài)功耗約為34.451 mW。為提供更公平的比較結(jié)果，表1中給出了譯碼器面積指標的2種表示形式：布局布線前的器件面積和等效門數(shù)量。其中，等效門數(shù)量為相同工藝下器件面積所對應的扇出為4的2輸入與非門(NAND FO4的面積為1.4 μm×1.8 μm)的等效數(shù)量；功耗指標為50%翻轉(zhuǎn)率情況下，200 MHz工作頻率所對應的動態(tài)功耗評估結(jié)果；譯碼器電路的關(guān)鍵路徑延遲為4.363 ns，滿足最大200 MHz的工作頻率。

本文提出的譯碼器電路與其他報告中BCH譯碼器電路的對比情況如表1中所示，為全面的對比譯碼器電路的性能，其中包括了電路的面積，碼字長度，糾錯能力，最大工作頻率，以及譯碼延遲和數(shù)據(jù)吞吐率的對比情況。另外，為避免工藝尺寸不同對電路面積對比結(jié)果的影響，在表1中以等效門數(shù)量作為電路面積的比較參數(shù)。

表1 譯碼器性能對比Table 1 Performance comparison of decoder

根據(jù)式(3)可知，碼字長度n和糾錯能力t與計算量正比，譯碼過程的計算量不僅決定了譯碼延遲，同時也決定了電路的規(guī)模。對比表1中的數(shù)據(jù)，本文提出的BCH譯碼器與文獻[13]的碼字長度相同，糾錯能力提升近一倍，但電路面積僅為文獻[13]的約38.7%；與文獻[12]相比，在碼字長度和糾錯能力均相同的情況下，本文設計的譯碼器電路也得到了約20.8%的面積縮減，并且，最大數(shù)據(jù)吞吐率和譯碼延遲也得到了近一倍的提升；而表1中文獻[11]具有最高的數(shù)據(jù)吞吐率和最低的譯碼延遲，但由于使用了αn元素的查找表結(jié)構(gòu)，導致與其他成果相比，即使碼字數(shù)據(jù)長度最短，卻具有最高的面積成本，文獻[11]中譯碼器的碼字長度僅為本文的3.125%，但面積也是本文的3.4倍。綜合上述數(shù)據(jù)可知，本文提出的BCH譯碼器結(jié)構(gòu)在碼字數(shù)據(jù)長度與糾錯能力相同的情況下具有更低的譯碼延遲、更高的吞吐率以及更小的面積成本。

3 結(jié)論

1)基于避免求逆的BM算法實現(xiàn)譯碼器結(jié)構(gòu)，消除了元素求逆運算，并通過對元素參數(shù)的實時計算避免了原始算法中大規(guī)模查找表的使用，使譯碼器的電路面積得到了大幅縮減。

2)針對FLASH器件的時序特點和處理器對可靠性的要求，采用了CRC-16校驗與BCH編碼級聯(lián)的方式組織數(shù)據(jù)格式，克服了BCH算法的糾錯性能限制，使超出譯碼器糾錯能力的讀取數(shù)據(jù)的正確性能夠被譯碼器檢測，并采用了分段式CRC-16校驗的方式，使處理器能夠提取無錯誤的數(shù)據(jù)段，提高了對數(shù)據(jù)的利用率。

3)采用了乒乓結(jié)構(gòu)的桶形移位寄存器，使待譯碼數(shù)據(jù)與譯碼過程并行進行，并采用了全流水線的并行譯碼過程，獲得了更高的吞吐率。