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

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

2、廣闊的市場(chǎng)前景。DVB-S2的前向糾錯(cuò)系統(tǒng)(FEC)中配合LDPC碼使用了長(zhǎng)BCH，其碼字長(zhǎng)度為16 20058 320 b(正常幀模式)及14 4003 240 b(縮短幀模式)不等。長(zhǎng)BCH碼極大地增加了硬件的實(shí)現(xiàn)難度，滿足芯片面積要求的同時(shí)，更要求其譯碼速度能夠符合前級(jí)LDPC譯碼器輸出。本文通過(guò)對(duì)長(zhǎng)BCH碼優(yōu)化方法的研究與討論，針對(duì)標(biāo)準(zhǔn)中二進(jìn)制BCH碼的特性，設(shè)計(jì)了實(shí)現(xiàn)該譯碼器的FPGA硬件結(jié)構(gòu)。2 BCH編譯碼原理及算法BCH碼是可以糾正多個(gè)隨即錯(cuò)誤的循環(huán)碼，可以用生成多項(xiàng)式g(x)來(lái)構(gòu)成，循環(huán)碼的生成多項(xiàng)式可以表示成g(x)=LCMg1(x)，g2(x)，gi(x)，其中g(shù)1(x)

3、，g2(x)，gi(x)是g(x)零點(diǎn)的最小多項(xiàng)式，LCM表示這些最小多項(xiàng)式的最小公倍式。倘若給定一個(gè)BCH碼的碼長(zhǎng)n和糾錯(cuò)能力t，我們可以計(jì)算a，a2，a3，a2t在GF(q)上的最小多項(xiàng)式gi(x)，i=1，2，2t(其中a是GF(qm)上的本原域元素)，來(lái)構(gòu)成該BCH碼的生成多項(xiàng)式：g(x)=LCMg1(x)，g2(x)，gi(x)BCH碼的譯碼方法主要分兩大類(lèi)：時(shí)域譯碼和頻域譯碼，目前普遍使用的是時(shí)域中迭代譯碼的方法。BCH碼的譯碼過(guò)程遵循循環(huán)碼和線性碼的一般譯碼步驟：(1)計(jì)算接收碼字R(x)的伴隨S(x)；(2)根據(jù)伴隨式S(x)找出估計(jì)錯(cuò)誤圖樣E(x)；(3)R(x)-E(x)=

4、C1，得到譯碼器輸出的估計(jì)值；若C1=C，則譯碼正確，否則譯碼錯(cuò)誤。其中對(duì)于可糾正t個(gè)錯(cuò)誤的BCH碼而言，需要計(jì)算2t個(gè)伴隨式。由伴隨式Sj求出錯(cuò)誤位置多項(xiàng)式(x)和錯(cuò)誤值多項(xiàng)式(x)。這一過(guò)程有多種實(shí)現(xiàn)算法，常用的有Peterson算法，Berlekamp算法以及Euclid算法。其中Peterson算法需要完成矩陣求逆運(yùn)算，當(dāng)糾錯(cuò)數(shù)t較小時(shí)，該算法有很高的效率，但隨著糾錯(cuò)能力t的增加，其運(yùn)算量迅速增加。對(duì)于糾錯(cuò)數(shù)t較大的情況下，后兩種基于迭代的方法更常用。之后一般利用錢(qián)氏搜索算法來(lái)計(jì)算錯(cuò)誤位置多項(xiàng)式(x)的根，即位錯(cuò)誤位置X1，X2，Xt。該算法實(shí)質(zhì)是一種窮盡法，將每個(gè)位置代人多項(xiàng)式驗(yàn)證是

5、否為錯(cuò)誤位置，在工程上很好地解決了錯(cuò)誤位置求解的問(wèn)題。同時(shí)一般利用Forney算法通過(guò)錯(cuò)誤位置多項(xiàng)式(x)和錯(cuò)誤值多項(xiàng)式(x)來(lái)計(jì)算錯(cuò)誤值Y1，Y2，Yt。最后由錯(cuò)誤位置Xi和錯(cuò)誤值Yi得到錯(cuò)誤圖樣E(x)，通過(guò)R(x)-E(x)=C1糾正錯(cuò)誤值，并輸出最終譯碼值。3 BCH譯碼器硬件結(jié)構(gòu)在這一節(jié)中，本文將針對(duì)DVB-S2中BCH碼的特性，提出一種高效、低復(fù)雜度的譯碼器硬件結(jié)構(gòu)。根據(jù)譯碼原理，譯碼器一般由5個(gè)部分組成，如圖1所示。其中R(x)為接收的碼字，S為所求的伴隨式，(x)為錯(cuò)誤位置多項(xiàng)式，C1為輸出的譯碼值。針對(duì)標(biāo)準(zhǔn)中二進(jìn)制BCH碼的特殊性，對(duì)各模塊作了如下優(yōu)化：(1)利用二進(jìn)制BCH

6、碼的特性，減少伴隨式的計(jì)算數(shù)量，以并行結(jié)構(gòu)實(shí)現(xiàn)；(2)采用無(wú)逆二進(jìn)制Berlekamp算法，減少迭代次數(shù)，并從算法上去除了錯(cuò)誤值多項(xiàng)式(x)的求解、求逆運(yùn)算，省去相應(yīng)硬件開(kāi)銷(xiāo)；采用序列化硬件結(jié)構(gòu)，復(fù)用迦羅華域乘法器數(shù)量；(3)并行結(jié)構(gòu)實(shí)現(xiàn)錢(qián)氏搜索；(4)利用遞歸匹配和群組遞歸匹配的方法，優(yōu)化伴隨式、錢(qián)氏搜索中使用的迦羅華域固定因子乘法器。3.1 伴隨式計(jì)算在BCH譯碼過(guò)程中所需計(jì)算的伴隨式個(gè)數(shù)為2t，即可糾正錯(cuò)誤數(shù)t的2倍。DVB-S2中正常幀長(zhǎng)模式下的BCH碼分別由(65 535，65 343，12)，(65 535，65 375，10)和(65 535，65 407，8)三種碼截短而得，可

7、糾正12，10，8個(gè)錯(cuò)誤，相應(yīng)需要計(jì)算24，20，16個(gè)伴隨式。伴隨式計(jì)算公式如下：從伴隨式的計(jì)算公式可知，完成一個(gè)伴隨式的計(jì)算，需要一個(gè)碼字所有碼元輸入花費(fèi)的時(shí)間。因此碼長(zhǎng)為n的情況下，碼元逐一輸入，計(jì)算一個(gè)伴隨式則需要n個(gè)時(shí)鐘。為了減少伴隨式計(jì)算時(shí)間，采用圖2并行結(jié)構(gòu)計(jì)算伴隨式。一個(gè)時(shí)鐘并行輸入P位，則計(jì)算一個(gè)伴隨式只需要nP個(gè)時(shí)鐘。因此對(duì)于DVB-S2中的BCH碼，最多只需計(jì)算12個(gè)伴隨式，減少了一半的計(jì)算數(shù)量。最后由于P位并行輸入，寄存器D中的值進(jìn)入下一次累加之前，需要乘以一個(gè)常數(shù)api。對(duì)于迦羅華域上的固定因子乘法器，可通過(guò)遞歸匹配的方法，消除冗余的公共子項(xiàng)，達(dá)到優(yōu)化的目的。3.2

8、關(guān)鍵方程的求解關(guān)鍵方程的求解有多種適于硬件實(shí)現(xiàn)的算法，例如Peterson、Berlekamp-Massey或者Euclid的算法。關(guān)鍵方程的求解主要用于計(jì)算錯(cuò)誤位置多項(xiàng)式(x)和錯(cuò)誤值多項(xiàng)式(x)，對(duì)于DVB-S2中的二進(jìn)制BCH碼，無(wú)需計(jì)算錯(cuò)誤值多項(xiàng)式(x)，此外還要考慮迦羅華域上求逆、乘法器等大面積的運(yùn)算單元數(shù)量。通過(guò)比較，本文選擇了針對(duì)二進(jìn)制BCH碼改進(jìn)的無(wú)逆Berlekamp算法(inversionless Berlekamp)。算法描述如下：其中d(2k)為(1+S)(2k)乘積項(xiàng)中X(2k+1)的系數(shù)，迭代至Ssk+1不存在時(shí)，迭代結(jié)束，(x)即為所求的錯(cuò)誤位置多項(xiàng)式。首先該算法

9、避免了迦羅華域上的求逆運(yùn)算，大大簡(jiǎn)化了電路，同時(shí)針對(duì)二進(jìn)制BCH碼，簡(jiǎn)化了迭代算法，所需的迭代步驟減少為原來(lái)的一半，因此對(duì)于可糾正錯(cuò)誤數(shù)t=12的BCH碼只需迭代12次就可以得到錯(cuò)誤位置多項(xiàng)式(x)，同時(shí)該算法中并未涉及到錯(cuò)誤值多項(xiàng)式(x)的計(jì)算，從算法上去除了錯(cuò)誤值多項(xiàng)式的求解，減少了不必要的硬件開(kāi)銷(xiāo)。 該算法易于硬件實(shí)現(xiàn)，但若使用并行結(jié)構(gòu)實(shí)現(xiàn)此算法，那么整個(gè)關(guān)鍵方程的求解只需12個(gè)時(shí)鐘，但需要38個(gè)16位的迦羅華域乘法器。16位的迦羅華域乘法器相當(dāng)消耗資源，該模塊所占的面積由乘法器的數(shù)量決定。若采用序列化的結(jié)構(gòu)復(fù)用乘法器，雖然增加了一定譯碼延時(shí)，但可將乘法器個(gè)數(shù)減至3個(gè)，大大減少了硬件面積

10、。因此本文采用圖3所示序列化的結(jié)構(gòu)，該結(jié)構(gòu)一共只使用了3個(gè)16位的迦羅華域乘法器，迭代一次需要14個(gè)時(shí)鐘，迭代次數(shù)為可糾正錯(cuò)誤數(shù)(t次)。當(dāng)t=12時(shí)，最多需要168個(gè)時(shí)鐘。增加了少量譯碼延時(shí)，但大大減少硬件面積，同時(shí)所增加的譯碼延時(shí)要遠(yuǎn)小于一個(gè)碼字的譯碼周期，對(duì)于整個(gè)碼字的譯碼速度影響不是很大。3.3 錢(qián)氏搜索得到錯(cuò)誤位置多項(xiàng)式(x)后，需要求解該方程的根來(lái)確定錯(cuò)誤位置，錢(qián)氏搜索法在工程上很好地解決了對(duì)于該方程求根的問(wèn)題。其本質(zhì)上是一種窮舉法，將可能的錯(cuò)誤位置逐一代入方程驗(yàn)證，以確定是否在該位置發(fā)生了錯(cuò)誤，即驗(yàn)證ai是否為(x)的根：同樣的n個(gè)可能的位置都需要逐一代人驗(yàn)證，一共需要n個(gè)時(shí)鐘；

11、同伴隨式計(jì)算一樣，為了提高運(yùn)算速度，本文采用并行結(jié)構(gòu)實(shí)現(xiàn)錢(qián)氏搜索。3.4 迦羅華域上固定因子乘法器的優(yōu)化在伴隨式及錢(qián)氏搜索模塊中都用到了迦羅華域上的固定因子乘法器，根據(jù)文獻(xiàn)1中描述的Iterative Matc- hing Algorithm(IMA)算法，通過(guò)迭代找出公共子項(xiàng)，減少冗余計(jì)算單元，以減小電路面積。算法描述如下：設(shè)B為迦羅華域上的變量，C是B與常數(shù)ai的乘積；用自然基表示法表示域上的常數(shù)，也即用ai0，ai1，ai2，aim-1來(lái)表示ai。由于ai為已知常數(shù)，故乘積C的各元素也就是B各元素的加權(quán)組合，二進(jìn)制加法可由異或門(mén)來(lái)實(shí)現(xiàn)，系數(shù)矩陣即由a的i(i+m-1)次方組成。通過(guò)迭代匹

12、配的算法，逐次找出系數(shù)矩陣中的公共子項(xiàng)，通過(guò)最大限度地共享公共項(xiàng)來(lái)減少面積。迭代過(guò)程分為以下4個(gè)步驟：(1)找出a系數(shù)矩陣中各行相匹配的位數(shù)；(2)確定最多匹配的位數(shù)；(3)從匹配的兩行中去除冗余部分(匹配部分)，并將去除的冗余部分作為一個(gè)新行添加到系數(shù)矩陣末；(4)重復(fù)執(zhí)行步驟(1)(3)，直到匹配數(shù)2，尋找匹配時(shí)包括新添加的行。伴隨式計(jì)算中可以利用該算法，減少固定因子乘法器的面積，對(duì)于錢(qián)氏搜索模塊可以利用群組匹配作進(jìn)一步的優(yōu)化，如圖4中，P個(gè)位置并行驗(yàn)證時(shí)，系數(shù)i需要乘以P個(gè)固定常數(shù)，可將P個(gè)常數(shù)以組的形式進(jìn)行匹配，最大化地消除冗余子項(xiàng)。4 仿真結(jié)果用Verilog硬件描述語(yǔ)言完成了BCH碼譯碼器的RTL級(jí)設(shè)計(jì)，用Modelsim進(jìn)行了功能仿真，并用QuartusII進(jìn)行了綜合。本文提出的結(jié)構(gòu)中，關(guān)鍵方程模塊相對(duì)獨(dú)立、固定，伴隨式及錢(qián)搜索的并行位數(shù)取值，應(yīng)根據(jù)整個(gè)系統(tǒng)時(shí)鐘及內(nèi)碼LDPC輸出速率綜合考慮。仿真設(shè)計(jì)中采用了15位的并行輸入輸出，Modelsim功能仿真波形圖如圖5所示。5 結(jié)語(yǔ)本文針對(duì)DVB-B2標(biāo)準(zhǔn)中BCH碼的特殊性，提出了一種適合FPGA實(shí)現(xiàn)的硬件結(jié)構(gòu)。該