DVB-S2中BCH譯碼器的硬件設計

　　1 引言

　　第二代數(shù)字衛(wèi)星廣播標準DVB-S2自發(fā)布以來一直廣受關注，他采用了由BCH外碼和LDPC內碼級聯(lián)而成的前向糾錯編碼(FEC)系統(tǒng)，有效地降低了系統(tǒng)解調門限，幾乎可以接近香農限，此外還使用了多種具有高頻帶利用率的調制方式，大幅度提高了信道傳輸能力。DVB-S2技術上的突破擴大了他的應用范圍，服務范圍包括廣播業(yè)務(BS)、數(shù)字新聞采集(DSNG)、數(shù)據(jù)分配/中繼，以及Internet接人等交互式業(yè)務。同時新的編碼技術使其可以工作在更為惡劣的信道環(huán)境中，保證了衛(wèi)星傳輸?shù)耐ㄐ刨|量。衛(wèi)星數(shù)字電視直播產業(yè)已經在全球形成發(fā)展熱點，隨著業(yè)務的拓展，數(shù)字衛(wèi)星接收機將具有廣闊的市場前景。

　　DVB-S2的前向糾錯系統(tǒng)(FEC)中配合LDPC碼使用了長BCH，其碼字長度為16 200～58 320 b(正常幀模式)及14 400～3 240 b(縮短幀模式)不等。長BCH碼極大地增加了硬件的實現(xiàn)難度，滿足芯片面積要求的同時，更要求其譯碼速度能夠符合前級LDPC譯碼器輸出。本文通過對長BCH碼優(yōu)化方法的研究與討論，針對標準中二進制BCH碼的特性，設計了實現(xiàn)該譯碼器的FPGA硬件結構。

　　2 BCH編譯碼原理及算法

　　BCH碼是可以糾正多個隨即錯誤的循環(huán)碼，可以用生成多項式g(x)來構成，循環(huán)碼的生成多項式可以表示成g(x)=LCM[g1(x)，g2(x)，…，gi(x)]，其中g1(x)，g2(x)，…，gi(x)是g(x)零點的最小多項式，LCM表示這些最小多項式的最小公倍式。倘若給定一個BCH碼的碼長n和糾錯能力t，我們可以計算a，a2，a3，…，a2t在GF(q)上的最小多項式gi(x)，i=1，2，…，2t(其中a是GF(qm)上的本原域元素)，來構成該BCH碼的生成多項式：

　　g(x)=LCM[g1(x)，g2(x)，…，gi(x)]

　　BCH碼的譯碼方法主要分兩大類：時域譯碼和頻域譯碼，目前普遍使用的是時域中迭代譯碼的方法。BCH碼的譯碼過程遵循循環(huán)碼和線性碼的一般譯碼步驟：

　　(1)計算接收碼字R(x)的伴隨S(x);

　　(2)根據(jù)伴隨式S(x)找出估計錯誤圖樣E(x);

　　(3)R(x)-E(x)=C1，得到譯碼器輸出的估計值;若C1=C，則譯碼正確，否則譯碼錯誤。

　　其中對于可糾正t個錯誤的BCH碼而言，需要計算2t個伴隨式。由伴隨式Sj求出錯誤位置多項式Λ(x)和錯誤值多項式ω(x)。這一過程有多種實現(xiàn)算法，常用的有Peterson算法，Berlekamp算法以及Euclid算法。其中Peterson算法需要完成矩陣求逆運算，當糾錯數(shù)t較小時，該算法有很高的效率，但隨著糾錯能力t的增加，其運算量迅速增加。對于糾錯數(shù)t較大的情況下，后兩種基于迭代的方法更常用。之后一般利用錢氏搜索算法來計算錯誤位置多項式Λ(x)的根，即位錯誤位置X1，X2，…，Xt。該算法實質是一種窮盡法，將每個位置代人多項式驗證是否為錯誤位置，在工程上很好地解決了錯誤位置求解的問題。同時一般利用Forney算法通過錯誤位置多項式Λ(x)和錯誤值多項式ω(x)來計算錯誤值Y1，Y2，…，Yt。最后由錯誤位置Xi和錯誤值Yi得到錯誤圖樣E(x)，通過R(x)-E(x)=C1糾正錯誤值，并輸出最終譯碼值。

　　3 BCH譯碼器硬件結構

　　在這一節(jié)中，本文將針對DVB-S2中BCH碼的特性，提出一種高效、低復雜度的譯碼器硬件結構。根據(jù)譯碼原理，譯碼器一般由5個部分組成，如圖1所示。

　　其中R(x)為接收的碼字，S為所求的伴隨式，Λ(x)為錯誤位置多項式，C1為輸出的譯碼值。

　　針對標準中二進制BCH碼的特殊性，對各模塊作了如下優(yōu)化：

　　(1)利用二進制BCH碼的特性，減少伴隨式的計算數(shù)量，以并行結構實現(xiàn);

　　(2)采用無逆二進制Berlekamp算法，減少迭代次數(shù)，并從算法上去除了錯誤值多項式ω(x)的求解、求逆運算，省去相應硬件開銷;采用序列化硬件結構，復用迦羅華域乘法器數(shù)量;

　　(3)并行結構實現(xiàn)錢氏搜索;

　　(4)利用遞歸匹配和群組遞歸匹配的方法，優(yōu)化伴隨式、錢氏搜索中使用的迦羅華域固定因子乘法器。

　　3.1 伴隨式計算

　　在BCH譯碼過程中所需計算的伴隨式個數(shù)為2t，即可糾正錯誤數(shù)t的2倍。DVB-S2中正常幀長模式下的BCH碼分別由(65 535，65 343，12)，(65 535，65 375，10)和(65 535，65 407，8)三種碼截短而得，可糾正12，10，8個錯誤，相應需要計算24，20，16個伴隨式。伴隨式計算公式如下：

　　從伴隨式的計算公式可知，完成一個伴隨式的計算，需要一個碼字所有碼元輸入花費的時間。因此碼長為n的情況下，碼元逐一輸入，計算一個伴隨式則需要n個時鐘。為了減少伴隨式計算時間，采用圖2并行結構計算伴隨式。一個時鐘并行輸入P位，則計算一個伴隨式只需要[n/P]個時鐘。

　　因此對于DVB-S2中的BCH碼，最多只需計算12個伴隨式，減少了一半的計算數(shù)量。最后由于P位并行輸入，寄存器D中的值進入下一次累加之前，需要乘以一個常數(shù)api。對于迦羅華域上的固定因子乘法器，可通過遞歸匹配的方法，消除冗余的公共子項，達到優(yōu)化的目的。

　　3.2 關鍵方程的求解

　　關鍵方程的求解有多種適于硬件實現(xiàn)的算法，例如Peterson、Berlekamp-Massey或者Euclid的算法。關鍵方程的求解主要用于計算錯誤位置多項式Λ(x)和錯誤值多項式ω(x)，對于DVB-S2中的二進制BCH碼，無需計算錯誤值多項式ω(x)，此外還要考慮迦羅華域上求逆、乘法器等大面積的運算單元數(shù)量。通過比較，本文選擇了針對二進制BCH碼改進的無逆Berlekamp算法(inversionless Berlekamp)。

　　算法描述如下：

　　其中d(2k)為(1+S)Λ(2k)乘積項中X(2k+1)的系數(shù)，迭代至Ssk+1不存在時，迭代結束，Λ(x)即為所求的錯誤位置多項式。

　　首先該算法避免了迦羅華域上的求逆運算，大大簡化了電路，同時針對二進制BCH碼，簡化了迭代算法，所需的迭代步驟減少為原來的一半，因此對于可糾正錯誤數(shù)t=12的BCH碼只需迭代12次就可以得到錯誤位置多項式Λ(x)，同時該算法中并未涉及到錯誤值多項式ω(x)的計算，從算法上去除了錯誤值多項式的求解，減少了不必要的硬件開銷。

　　該算法易于硬件實現(xiàn)，但若使用并行結構實現(xiàn)此算法，那么整個關鍵方程的求解只需12個時鐘，但需要38個16位的迦羅華域乘法器。16位的迦羅華域乘法器相當消耗資源，該模塊所占的面積由乘法器的數(shù)量決定。若采用序列化的結構復用乘法器，雖然增加了一定譯碼延時，但可將乘法器個數(shù)減至3個，大大減少了硬件面積。因此本文采用圖3所示序列化的結構，該結構一共只使用了3個16位的迦羅華域乘法器，迭代一次需要14個時鐘，迭代次數(shù)為可糾正錯誤數(shù)(t次)。當t=12時，最多需要168個時鐘。增加了少量譯碼延時，但大大減少硬件面積，同時所增加的譯碼延時要遠小于一個碼字的譯碼周期，對于整個碼字的譯碼速度影響不是很大。

　　3.3 錢氏搜索

　　得到錯誤位置多項式Λ(x)后，需要求解該方程的根來確定錯誤位置，錢氏搜索法在工程上很好地解決了對于該方程求根的問題。其本質上是一種窮舉法，將可能的錯誤位置逐一代入方程驗證，以確定是否在該位置發(fā)生了錯誤，即驗證ai是否為Λ(x)的根：

　　同樣的n個可能的位置都需要逐一代人驗證，一共需要n個時鐘;同伴隨式計算一樣，為了提高運算速度，本文采用并行結構實現(xiàn)錢氏搜索。

　　3.4 迦羅華域上固定因子乘法器的優(yōu)化

　　在伴隨式及錢氏搜索模塊中都用到了迦羅華域上的固定因子乘法器，根據(jù)文獻[1]中描述的Iterative Matc- hing Algorithm(IMA)算法，通過迭代找出公共子項，減少冗余計算單元，以減小電路面積。

　　算法描述如下：設B為迦羅華域上的變量，C是B與常數(shù)ai的乘積;

　　用自然基表示法表示域上的常數(shù)，也即用[ai0，ai1，ai2，…，aim-1]來表示ai。由于ai為已知常數(shù)，故乘積C的各元素也就是B各元素的加權組合，二進制加法可由異或門來實現(xiàn)，系數(shù)矩陣即由a的i～(i+m-1)次方組成。通過迭代匹配的算法，逐次找出系數(shù)矩陣中的公共子項，通過最大限度地共享公共項來減少面積。迭代過程分為以下4個步驟：

　　(1)找出a系數(shù)矩陣中各行相匹配的位數(shù);

　　(2)確定最多匹配的位數(shù);

　　(3)從匹配的兩行中去除冗余部分(匹配部分)，并將去除的冗余部分作為一個新行添加到系數(shù)矩陣末;

　　(4)重復執(zhí)行步驟(1)～(3)，直到匹配數(shù)<2，尋找匹配時包括新添加的行。

　　伴隨式計算中可以利用該算法，減少固定因子乘法器的面積，對于錢氏搜索模塊可以利用群組匹配作進一步的優(yōu)化，如圖4中，P個位置并行驗證時，系數(shù)Λi需要乘以P個固定常數(shù)，可將P個常數(shù)以組的形式進行匹配，最大化地消除冗余子項。

　　4 仿真結果

　　用Verilog硬件描述語言完成了BCH碼譯碼器的RTL級設計，用Modelsim進行了功能仿真，并用QuartusII進行了綜合。本文提出的結構中，關鍵方程模塊相對獨立、固定，伴隨式及錢搜索的并行位數(shù)取值，應根據(jù)整個系統(tǒng)時鐘及內碼LDPC輸出速率綜合考慮。仿真設計中采用了15位的并行輸入/輸出，Modelsim功能仿真波形圖如圖5所示。

　　5 結語

　　本文針對DVB-B2標準中BCH碼的特殊性，提出了一種適合FPGA實現(xiàn)的硬件結構。該結構采用并行方式實現(xiàn)伴隨式計算、錢氏搜索，選擇針對二進制BCH碼的無逆Berlekamp算法，減少了迭代次數(shù)，并以序列化的結構實現(xiàn)該算法，將16位迦羅會域乘法器減少至3個，大幅度減少了所占硬件資源。并在伴隨式計算及錢氏搜索中使用利用遞歸匹配和群組遞歸匹配的方法，對固定因子乘法器作了優(yōu)化。本文提出者的硬件結構，對BCH譯碼器各模塊都作了一定的優(yōu)化處理，保證譯碼速度的前提下，盡可能地減少了芯片面積。