吳子靜，蘇凱雄

(福州大學(xué)物理與信息工程學(xué)院，福建 福州 350002)

BCH(Bose，Chauhuri and Hocquenghem)碼是循環(huán)碼中的一大子類，可以有效地糾正多個隨機錯誤。A.Hocquenghem在1959年、R.C.Bose和 D.K.Chaudhuri在1960年分別提出了二進制BCH碼。Peterson在1960年證明了BCH碼的循環(huán)結(jié)構(gòu)。Gorenstein和Zierler在1961年將二進制BCH碼推廣到多進制［1］。BCH碼的基本特征是其生成多項式g(x)包含2t個連續(xù)冪次的根，這使其具有不同于一般循環(huán)碼的編譯碼算法，實現(xiàn)相對簡單。從20世紀(jì)70年代起，BCH碼便成為了線性分組碼的主流。在現(xiàn)代通信的信道編碼中，BCH碼通常被用作級聯(lián)碼的外碼，可以有效地消除內(nèi)碼的誤碼平臺。如歐洲的第二代數(shù)字視頻廣播標(biāo)準(zhǔn) DVB－S2、DVB－C2、DVB－T2 及我國的數(shù)字電視地面廣播標(biāo)準(zhǔn)DTMB都采用了BCH碼作為外碼、LDPC碼作為內(nèi)碼的信道編碼方案。

BCH碼最經(jīng)典、最通用的譯碼算法是伯利坎普(Berlekamp)迭代譯碼 +錢氏搜索法［1－5］，該算法適用于各種糾錯能力、多進制的BCH碼的譯碼。由于DTMB標(biāo)準(zhǔn)中采用的是縮短的二進制BCH碼，且糾錯能力是1，故本文根據(jù)該BCH碼的特性，提出一種更簡單的BCH碼譯碼算法，并設(shè)計出基于FPGA的BCH譯碼器。其硬件復(fù)雜度低、資源占用少、譯碼時延小。

1 傳統(tǒng)BCH碼的譯碼算法

BCH的譯碼算法比編碼算法復(fù)雜得多，由于它是線性分組碼，故其最基本的思路與一般的線性分組碼類似:

1)由接收到的碼字r(X)計算校正子S(X);

2)根據(jù)校正子S(X)找出錯誤圖樣e(X);

3)計算c(X)=r(X)－e(X)，得到譯碼器的估值碼字。

又由于BCH碼連續(xù)冪次根的性質(zhì)，為它的譯碼帶來了特殊算法，其中最經(jīng)典最通用的是伯利坎普迭代譯碼+錢氏搜索法，具體有如下幾個步驟:

1)校正子S(X)的計算

首先，用接收到的碼字r(X)分別除以2t個根αi所對應(yīng)的最小多項式mi(X)，得到2t個余式bi(X)，其中i=1，2，…，2t。由于 r(X)=ai(X)mi(X)+bi(X) ，且有mi(αi)=0，可得校正子的分量為

由于Si=r(αi)=c(αi)+e(αi)=e(αi) ，故求出校正子便可以進一步求出錯誤圖樣，從而完成譯碼。

2)錯誤圖樣e(X)的計算

錯誤圖樣由錯誤位置和錯誤值決定，對于二進制BCH碼而言，其錯誤值為1，只需求出錯誤位置。若一個碼字中共有 v(0≤v≤t) 個錯誤，令j1，j2，…，jv，(0≤jv≤n)表示錯誤的位置。則錯誤圖樣和校正子分量分別為

式中:βl=αjl，稱為錯誤位置數(shù)。若求出錯誤位置數(shù)，則其冪次就是錯誤的位置。

錯誤圖樣有很多組解，其中具有最小錯誤數(shù)的錯誤模式就是正確的解。定義了一個錯誤位置多項式

該多項式的根是錯誤位置數(shù)的倒數(shù)。

因此，求錯誤圖樣具體分為以下2個步驟:

(1)用伯利坎普迭代算法求錯誤位置多項式

錯誤多項式的系數(shù)可以由伯利坎普迭代算法求得。迭代的第1步是求最低次數(shù)多項式σ(1)(X)，使它的系數(shù)滿足第1個牛頓恒等式。第2步是檢驗σ(1)(X)的系數(shù)是否也滿足第2個牛頓恒等式。若滿足，則取σ(2)(X)=σ(1)(X)。若不滿足，則對σ(1)(X)增加一個修正項構(gòu)成σ(2)(X)，使σ(2)(X)滿足前兩個牛頓恒等式。如此迭代下去，得到σ(2t)(X)為止，即為錯誤位置多項式。

(2)用錢氏搜索算法求錯誤位置

首先，計算錯誤位置多項式的根。將 1，α，α2，…，αn－1代入σ(X)，若σ(αl)=0，則αl為它的根。那么，錯誤位置數(shù)為其根的倒數(shù)，即βl=αn－l，則錯誤位置為n－l。錢聞天提出了著名的錢氏搜索算法，從工程上解決了此問題，成為求取σ(X)的根的標(biāo)準(zhǔn)算法。即對碼的每個位置逐位檢驗來確定其錯誤位置，從最高位rn－1開始譯碼。譯第rn－l位碼時，譯碼器檢驗 αn－l是否為錯誤位置數(shù)，也就是檢驗它的倒數(shù)αl是否為σ(X)的根。若αl是根，則1+ σ1αl+ σ2α2l+… + σvαvl=0，即該位碼是錯誤的，否則是正確的。

3)計算c(X)=r(X)－e(X)得到譯碼器的估值碼字

從以上步驟可以看出，傳統(tǒng)的二進制BCH碼譯碼算法雖然適用于各種糾錯能力的BCH碼，但譯碼過程比較復(fù)雜，特別是錯誤位置多項式與錯誤位置的求取最為繁瑣，電路實現(xiàn)復(fù)雜度高、譯碼時延較長。在實際工程應(yīng)用中往往采用的是糾錯能力不那么強的BCH碼，故本文以DTMB標(biāo)準(zhǔn)中的BCH碼為研究對象，提出比傳統(tǒng)譯碼算法更簡單的BCH碼譯碼算法和實現(xiàn)電路。

2 適用于DTMB標(biāo)準(zhǔn)的BCH譯碼算法

2.1 DTMB標(biāo)準(zhǔn)中的BCH碼

我國數(shù)字電視地面廣播國家標(biāo)準(zhǔn)(DTMB)中，輸入的比特碼率經(jīng)過PN序列加擾后，接著進行前向糾錯編碼。前向糾錯編碼是由外碼(BCH)和內(nèi)碼(LDPC)級聯(lián)實現(xiàn)的。其BCH(762，752)是由 BCH(1023 ，1013 )系統(tǒng)碼縮短而成的［6］。在 752 bit數(shù)據(jù)擾亂碼前添加261 bit“0”形成 1013 bit，編碼成 1023 bit。然后去除前261 bit“0”，形成762 bit BCH碼字。該BCH碼的生成多項式為

二進制本原 BCH(n，k，t)碼滿足

式中:n為碼長;k為信息位長度;t為糾錯能力;dmin為碼的最小距離。根據(jù)式(6)，可以得到BCH(1023 ，1013 )中m=10，糾錯能力 t=1。

BCH碼的生成多項式由它在伽羅華域GF(2m)上的根確定。令α為GF(2m)的本原，2t個連續(xù)冪次根α，α2，…，α2t所對應(yīng)的二元域上的最小多項式為m1(x)，m2(x)，…，m2t(x)，則糾t個錯誤的BCH碼的生成多項式為這些多項式的最小公倍數(shù)，即

由于α的每個偶次冪都與其前面的每個奇數(shù)冪具有相同的最小多項式，因此有

根據(jù)式(8)，可得糾單個錯誤的BCH碼的生成多項式為

由于α是GF(2m)的本原，故m1(x)是m次本原多項式。因此可得碼長為2m－1，糾單個錯誤的BCH碼是循環(huán)漢明碼。即可以把DTMB標(biāo)準(zhǔn)中的BCH(1023 ，1013 )碼看作是糾錯能力為1的循環(huán)漢明碼。

2.2 DTMB標(biāo)準(zhǔn)中BCH碼的譯碼算法

通過上述分析，已經(jīng)證明了DTMB標(biāo)準(zhǔn)中的BCH碼是循環(huán)漢明碼。循環(huán)漢明碼的譯碼過程與一般線性碼相同，需要3個步驟，但實現(xiàn)方式不同。

1)校正子的計算

對于循環(huán)碼，其校正子的計算公式為

式中:r(X)為接收到的序列，表示為r(X)=r0+r1X+…+rn－1Xn－1;g(X)為生成多項式;s(X) 為校正子。即用r(X)除以g(X)，得到的余式就是s(X)。這可以用一個除法電路來計算它的校正子，這個電路的復(fù)雜度線性正比于校驗位的數(shù)目，即n－k。若校正子為0，則表示接收的碼字是正確的，否則是錯誤的。

2)由校正子檢測錯誤模式

循環(huán)碼的循環(huán)結(jié)構(gòu)可以對接收序列r(X)進行串行譯碼，每次只譯1位接收碼，且每一位數(shù)據(jù)可以使用相同的電路進行譯碼。首先對r(X)的最高位Xn－1進行譯碼，即錯誤多項式為

若單個錯誤發(fā)生在最高位，則其校正子為Xn－1/g(x)的余式;若單個錯誤發(fā)生在其他位置上，則校正子不相同。因此，僅需一個m輸入的異或門，就可以檢測出該校正子的圖樣。若單個錯誤不是發(fā)生在最高位，則將接收多項式r(X)和校正子同時循環(huán)移位1位。這樣便得到r(1)(X)=rn－1+r0X+ … +rn－2Xn－1，及 r(1)(X) 的校正子S(1)(X)。此時r(X)的第2位變?yōu)閞(1)(X)的第1位，使用同樣的檢測電路，便可檢測S(1)(X)是否與Xn－1位存在差錯的錯誤模式相對應(yīng)。以此類推，便可完成對所有位的檢測。

3)差錯糾正

若檢測出r(X)的校正子S(X)與Xn－1位的錯誤模式相對應(yīng)，則rn－1為差錯位。可以通過式(12)糾正，即

同時將錯誤模式與校正子模2加，消除差錯位en－1對校正子的影響。

從以上步驟可以看出，該算法與傳統(tǒng)譯碼算法最大的差別在于錯誤模式(圖樣)的檢測上。該算法錯誤模式的計算簡單，且錯誤模式的檢測電路只需一個m輸入的異或門即可實現(xiàn)，極大地簡化了譯碼過程，降低了電路的復(fù)雜度。

3 BCH譯碼算法的FPGA實現(xiàn)

3.1 BCH碼串行譯碼器的實現(xiàn)

根據(jù)上述的譯碼算法，可以設(shè)計出相應(yīng)的譯碼電路，主要由3個部分組成:校正子寄存器、錯誤模式檢測器和存儲接收向量的緩沖寄存器。為消除錯誤對校正子的影響，需將差錯位通過一個異或門反饋到校正子移位寄存器。譯碼器工作原理如下［1］:

1)接收向量全部移入校正寄存器得到校正子，同時接收向量存入到緩沖寄存器中。

2)將校正子讀入檢測器中，檢測相應(yīng)的錯誤模式。檢測器為組合邏輯電路，當(dāng)且僅當(dāng)校正子寄存器中的校正子所對應(yīng)的接收向量的最高位存在差錯時，輸出為1。

3)從緩沖寄存器中讀取第1個接收符號，并將校正子寄存器移位1次。若檢測到第1個接收符號存在差錯，則被檢測器的輸出糾正，同時e(X)=Xn－1的校正子被反饋回校正子寄存器來修正校正子。

4)接著對第2個接收符號(此時處于緩沖寄存器的第1位)進行譯碼。譯碼器重復(fù)步驟2)～3)。

5)譯碼器按以上步驟對接收到的符號逐位譯碼，直到從緩沖寄存器讀出整個接收序列為止。

BCH碼譯碼器的實現(xiàn)電路如圖1所示。圖中，接收碼字r(X)是從校正子寄存器右端輸入的，等價于錯誤多項式預(yù)先移位m位，即需要修改差錯檢測電路。若單個錯誤發(fā)生在最高位，則其校正子為Xm·Xn－1/g(x)的余式。

圖1 BCH碼串行譯碼器

對于BCH(1023 ，1013 )碼，可計算得其校正子應(yīng)為X10·X1023－1/g(x) 的余式，即

用一個與門便可檢測校正子圖樣(0，0，0，0，0，0，0，0，0，1)，與門輸入端為 s'0，s'1，…，s'm－2和 sm－1。其中 si為校正子，s'i為si的取反。

另外，DTMB標(biāo)準(zhǔn)中，BCH碼是縮短的循環(huán)碼，信息位中前261位為0，故在計算校正子時，不影響校正子最后的值，可以省去，故校正子的計算只需762個時鐘。但對應(yīng)的檢測電路是從最高位r1022開始檢測并輸出。之后的261位都為0，并且是無用的信息。為了避免這額外的校正子寄存器的261次移位，需修改原先的差錯檢測電路。第r761位對應(yīng)的校正子為X10·X1023－261－1/g(x)的余式，即

校正子圖樣為(0，0，0，1，1，0，0，0，0，1)，與門輸入端為 s'0，s'1，s'2，s3，s4，s'5，s'6，s'7，s'8，s9。

圖2為BCH碼串行譯碼的ModelSim波形仿真圖。

圖2 BCH碼串行譯碼ModelSim波形仿真(截圖)

從圖2中可以看到，譯碼器輸入的第5位為0，輸出為1，該差錯已被譯碼器糾正，譯碼的結(jié)果是正確的。一個完整的譯碼從完全輸入到開始輸出有762個時鐘的延時。采用Altera的Stratix II系列EP2S90F1020C4平臺進行綜合，綜合結(jié)果表明該譯碼器僅占用48個ALUT邏輯單元，資源消耗極小。

3.2 BCH碼并行譯碼器的實現(xiàn)

為了滿足系統(tǒng)速率的要求，本文在串行BCH譯碼器的基礎(chǔ)上設(shè)計了BCH碼并行譯碼器，實現(xiàn)10位的并行輸入輸出譯碼。本文首先在接收到的762位符號前補8位0，形成770位，再進行譯碼，輸出也為770位，再將前8位的0丟棄。譯碼器電路的校正子單元與錯誤模式檢測需要進行相應(yīng)改變。校正子循環(huán)移位單元在每個時鐘周期需得到串行譯碼中循環(huán)移位10次后的值。校正子可通過式(15)計算得到，即

式中:Si為校正子寄存器的值;si為移位前寄存器中的值;ri為并行輸入的第i個接收位。

另一個需要修改的部分是錯誤模式檢測的組合邏輯單元。本文設(shè)計的是10位并行輸出，需要設(shè)計10個組合邏輯單元來同時檢測10位不同的錯誤模式，并進行糾正輸出。計算 Xm·Xi－1/g(x) 的余式，其中 i=770，769，…，761，可得各個位置的組合邏輯檢測電路為

若檢測器輸出ei為1，則ei(X)=X770+i的校正子將被反饋回校正子寄存器，通過模2加修正當(dāng)前寄存器中的值。

圖3為BCH碼并行譯碼的ModelSim波形仿真圖。

圖3 BCH碼并行譯碼ModelSim波形仿真(截圖)

從圖3中可以看出，譯碼器輸入“3ED”已被糾正為“36D”(十六進制)，譯碼結(jié)果準(zhǔn)確無誤。一個完整的譯碼從完全輸入到輸出僅77個時鐘的延時。在Altera的Stratix II系列EP2S90F1020C4平臺的綜合結(jié)果僅占用76個ALUT邏輯單元，資源占用極少。

4 結(jié)論

傳統(tǒng)的BCH碼的譯碼算法是伯利坎普迭代譯碼+錢氏搜索法，該算法雖然通用，但算法和硬件實現(xiàn)比較繁瑣。本文研究了DTMB標(biāo)準(zhǔn)中的BCH碼的特性，證明了該碼是糾錯能力為1的循環(huán)漢明碼，提出了適用于該BCH碼的譯碼方法，該方法比傳統(tǒng)的BCH碼的譯碼算法簡單。并設(shè)計出兩種譯碼電路:串行譯碼器和并行譯碼器。另外由于DTMB標(biāo)準(zhǔn)采用的是縮短的BCH碼，在信息位前加上了261位的0，本文通過修改差錯檢測電路，使串行/并行譯碼器縮短了34%的譯碼時延，并行譯碼器的譯碼時延僅為77個時鐘周期。該譯碼器硬件實現(xiàn)簡單，F(xiàn)PGA的資源占用極少。

［1］LIN Shu，COSTELLO D J.Error control coding［M］.San Antonio:Pearson Education Inc.，2007.

［2］張博.數(shù)字電視傳輸系統(tǒng)中BCH碼編/譯碼器的研究與FPGA實現(xiàn)［D］.北京:北京交通大學(xué)，2008.

［3］馮林浩.基于DTMB的糾錯碼譯碼器的研究與設(shè)計［D］.成都:電子科技大學(xué)，2010.

［4］許苑豐，王鵬.DTMB標(biāo)準(zhǔn)BCH譯碼器設(shè)計［J］.電子產(chǎn)品世界，2012，19(2):47－49.

［5］QIN Zhang，HU Qingsheng.Implementation of 10－Gb/s parallel BCH decoder based on Virtex－5 FPGA［J］.Advanced Materials Research，2012(429):159－164.

［6］GB20600—2006，數(shù)字電視地面廣播傳輸系統(tǒng)幀結(jié)構(gòu)、信道編碼和調(diào)制［S］.2006.