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

　　1 引言

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

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

　　2 BCH編譯碼原理及算法

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

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

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

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

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

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

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

　　3 BCH譯碼器硬件結構

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

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

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

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

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

　　(3)并行結構實(shí)現錢(qián)氏搜索;

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

　　3.1 伴隨式計算

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

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

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

　　3.2 關(guān)鍵方程的求解

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

　　算法描述如下：

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

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

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

　　3.3 錢(qián)氏搜索

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

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

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

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

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

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

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

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

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

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

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

　　4 仿真結果

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

　　5 結語(yǔ)

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