DVB-S2中BCH譯碼器的硬件設(shè)計(jì)

　　1 引言

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

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

　　2 BCH編譯碼原理及算法

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

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

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

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

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

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

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

　　3 BCH譯碼器硬件結(jié)構(gòu)

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

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

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

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

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

　　(3)并行結(jié)構(gòu)實(shí)現(xiàn)錢氏搜索;

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

　　3.1 伴隨式計(jì)算

　　在BCH譯碼過程中所需計(jì)算的伴隨式個數(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個錯誤，相應(yīng)需要計(jì)算24，20，16個伴隨式。伴隨式計(jì)算公式如下：

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

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

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

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

　　算法描述如下：

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

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

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

　　3.3 錢氏搜索

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

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

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

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

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

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

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

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

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

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

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

　　4 仿真結(jié)果

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

　　5 結(jié)語

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