DTMB系統中BCH譯碼算法及其FPGA實現

吳子靜，蘇凱雄

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

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

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

1 傳統BCH碼的譯碼算法

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

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

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

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

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

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

首先，用接收到的碼字r(X)分別除以2t個根αi所對應的最小多項式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，稱為錯誤位置數。若求出錯誤位置數，則其冪次就是錯誤的位置。

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

該多項式的根是錯誤位置數的倒數。

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

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

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

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

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

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

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

2 適用于DTMB標準的BCH譯碼算法

2.1 DTMB標準中的BCH碼

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

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

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

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

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

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

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

2.2 DTMB標準中BCH碼的譯碼算法

通過上述分析，已經證明了DTMB標準中的BCH碼是循環漢明碼。循環漢明碼的譯碼過程與一般線性碼相同，需要3個步驟，但實現方式不同。

1)校正子的計算

對于循環碼，其校正子的計算公式為

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

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

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

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

3)差錯糾正

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

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

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

3 BCH譯碼算法的FPGA實現

3.1 BCH碼串行譯碼器的實現

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

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

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

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

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

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

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

圖1 BCH碼串行譯碼器

對于BCH(1023 ，1013 )碼，可計算得其校正子應為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標準中，BCH碼是縮短的循環碼，信息位中前261位為0，故在計算校正子時，不影響校正子最后的值，可以省去，故校正子的計算只需762個時鐘。但對應的檢測電路是從最高位r1022開始檢測并輸出。之后的261位都為0，并且是無用的信息。為了避免這額外的校正子寄存器的261次移位，需修改原先的差錯檢測電路。第r761位對應的校正子為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，該差錯已被譯碼器糾正，譯碼的結果是正確的。一個完整的譯碼從完全輸入到開始輸出有762個時鐘的延時。采用Altera的Stratix II系列EP2S90F1020C4平臺進行綜合，綜合結果表明該譯碼器僅占用48個ALUT邏輯單元，資源消耗極小。

3.2 BCH碼并行譯碼器的實現

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

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

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

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

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

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

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

4 結論

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

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

［2］張博.數字電視傳輸系統中BCH碼編/譯碼器的研究與FPGA實現［D］.北京:北京交通大學，2008.

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

［4］許苑豐，王鵬.DTMB標準BCH譯碼器設計［J］.電子產品世界，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，數字電視地面廣播傳輸系統幀結構、信道編碼和調制［S］.2006.