基于BM算法的BCH碼的譯碼硬件實(shí)現(xiàn)

摘要：BCH碼是一種理論上比較成熟的代數(shù)碼型，在電力通信系統(tǒng)，GSM標(biāo)準(zhǔn)的語音和數(shù)據(jù)業(yè)務(wù)，以及衛(wèi)星通信和數(shù)字廣播通信(DVB-S2)等多個(gè)領(lǐng)域均有著廣泛的應(yīng)用?；趦绱芜\(yùn)算，在線性反饋移位寄存器(LFSR)下實(shí)現(xiàn)了基于Berlekamp—Massey(BM)時(shí)域迭代譯碼算法的整個(gè)譯碼器構(gòu)架，以及BM簡化算法的硬件設(shè)計(jì)。通過計(jì)算機(jī)模擬仿真表明，兩種算法的譯碼速率分別可達(dá)到32 Mbps，37Mbps。
關(guān)鍵詞：BM迭代簡化算法；FPGA；譯碼器構(gòu)架

O 引言
    BCH碼是1959年由Hocquenghem，1960年由Bose和Chandhari分別獨(dú)立提出的一種能糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼，該碼有嚴(yán)格的代數(shù)結(jié)構(gòu)，具有糾錯(cuò)能力可控，在中短碼長情況下性能接近理論最佳值等優(yōu)點(diǎn)，并且構(gòu)造方便，編碼簡單，是實(shí)際使用最廣泛的碼型之一。
    1960年P(guān)eterson從理論上解決了二進(jìn)制BCH碼的譯碼算法，奠定了BCH碼譯瑪?shù)睦碚摶A(chǔ)。隨后，Gorensten和Zierler把它推廣到高階有限域中。1966年Berlekamp提出了迭代譯碼算法，Maxsey從線性反饋寄存器的角度對(duì)該算法進(jìn)行描述，不僅使算法硬件實(shí)現(xiàn)成為可能，也大大提高了譯碼速度，從實(shí)際上解決了BCH碼的譯碼問題。鑒于FP—GA具有較大塊RAM，本文以(15，5)BCH碼為例說明如何將BM迭代算法，以及后面的chien搜索都建立在有限域上進(jìn)行運(yùn)算，用域元素的冪次運(yùn)算代替原來的乘和除操作，從而節(jié)約了邏輯單元(slice)資源。文獻(xiàn)已經(jīng)給出了普通BM譯碼算法的流程圖，本文根據(jù)二元BCH碼的特點(diǎn)給出了簡化的BM算法流程圖。

1 BM算法介紹
1．1 有限域知識(shí)介紹
    BCH碼是在有限域中進(jìn)行運(yùn)算的，詳細(xì)的有限域知識(shí)參考文獻(xiàn)。
    以本文設(shè)計(jì)的BCH碼為例，p(x)=x4+x1+1是GF(2)上的本原多項(xiàng)式。令α為本原多項(xiàng)式的根，m=4，則由{l，α，α2，α3}中元素的線性組合可表示GF(24)上的所有非零元素{α0，α1，α2，…，α14}，這些非零元素構(gòu)成一個(gè)循環(huán)群如表l所示。最后一行是為了運(yùn)算的需要，人為加上去的，表示“無”這種狀態(tài)。

1．2 經(jīng)典BM算法
    普通的譯碼算法都可分為如下三步：
    (1)由接收碼字R(x)計(jì)算伴隨式S(x)．(用除法電路)
    (2)由伴隨式S(x)求差錯(cuò)圖樣E(x)．(用各種譯碼方式)
    (3)由差錯(cuò)圖樣E(x)求得譯出碼字C(x)．(用關(guān)系式C(x)=R(x)一E(x))
    上面的(1)(3)步是固定關(guān)系式的運(yùn)算，相對(duì)容易，最關(guān)鍵的是第(2)步。1966年，Berlekamp針對(duì)關(guān)鍵方程式S(x)D(x)≡ω(x)(mod x2t+1)的求解(這里的D(x)為錯(cuò)誤位置多項(xiàng)式)，提出一種復(fù)雜度隨糾錯(cuò)數(shù)目線性增加的迭代算法，而Massey對(duì)Berlekamp算法作為設(shè)計(jì)自回歸濾波器的過程進(jìn)行了重新的推導(dǎo)，采用反饋移位寄存器來完成關(guān)鍵方程的計(jì)算。自此以后這種譯碼算法被稱為BM迭代譯碼算法，其算法流程圖參考文獻(xiàn)。

2 二元域下的簡化算法
    經(jīng)典的BM算法流程適合任何有限域的BCH碼，對(duì)于GF(2)，我們可以證明當(dāng)r為偶數(shù)時(shí)，△r為0[2]，此時(shí)迭代可以省略。通過對(duì)經(jīng)典BM算法流程圖的改進(jìn)，得到下圖l，即GF(2)上的簡化BM算法流程圖。

    其中，Sn為伴隨式，D(x)為錯(cuò)誤位置多項(xiàng)式，B(x)為多項(xiàng)式修正項(xiàng)，△代表差值即下一個(gè)伴隨式與由當(dāng)前錯(cuò)誤位置多項(xiàng)式表示的移位寄存器所產(chǎn)生的值之間的差值，L為移位寄存器的當(dāng)前長度。

3 硬件設(shè)計(jì)與實(shí)現(xiàn)
3．1 基于冪次的運(yùn)算方式
    對(duì)表1進(jìn)行簡化，得到表2和表3：

    將運(yùn)算步驟都建立在域元素冪次運(yùn)算的基礎(chǔ)上，流程圖中的“*”，“／”，“+”運(yùn)算方式都會(huì)改變。例如：(1110)*(1111)mod(10011，這個(gè)為本原多項(xiàng)式)=1011010mod(10011)=0101，轉(zhuǎn)化成冪次后(1110)*(1111)→a12*a11=α23=α8，原來二進(jìn)制乘除法電路變?yōu)楹唵蝺绱蔚闹笖?shù)加法電路。“+”由原來的模二加運(yùn)算變成兩次查表和一次模二加運(yùn)算，例如，α12+α11→查表二(1l11)+(1110)=000l→查表三0001對(duì)應(yīng)α0，所以得到α12+αll=α0。在硬件實(shí)現(xiàn)中，表2，表3的第二列作為內(nèi)容存在FPGA的ROM中，第一列作為他們的地址。

3．2 整體譯碼結(jié)構(gòu)設(shè)計(jì)
    以上是BCH譯碼器的整體結(jié)構(gòu)模塊圖，分四個(gè)模塊，下面介紹這四個(gè)模塊的功能：
    (1)S_produce：根據(jù)接收碼字R(r0 r1 r2…r14)，產(chǎn)生伴隨式S(s1，s2，s3，s4，s5，s6)；
    (2)dr：根據(jù)伴隨式S(s1,s2，s3，s4，s5，s6)，產(chǎn)生位置差錯(cuò)式D(dl，d2，d3)；
    (3)chien：以錢搜索的方式，根據(jù)位置差錯(cuò)式D(d1，d2，d3)，產(chǎn)生錯(cuò)誤圖樣E(e0，el，e2…e14)；
    (4)shift_register：同步時(shí)鐘的功能，滿足chien產(chǎn)生e14時(shí)，r14恰好輸出：c14=r14+e14。
    整個(gè)結(jié)構(gòu)中，dr這個(gè)模塊最為復(fù)雜，對(duì)應(yīng)整個(gè)BM算法。圖3是dr模塊圖。計(jì)算的功能，并將計(jì)算得到的△r值和前一狀態(tài)的D(dl，d2，d3)傳給T_updata，和B_updata這兩個(gè)模塊；B_updata完成B(x)更新的功能(B(x)<一xB(x)或B(x)<一△-1nd(x))，將值傳給T_updata；T_updata完成T(x)更新的功能(T(x)=d(x)一△rxB(x))，并將計(jì)算結(jié)果反饋給top_dr，作為當(dāng)前狀態(tài)的D(dl，d2，d3)；control模塊完成控制整個(gè)模塊的時(shí)鐘同步。

4 仿真結(jié)果
    我們選用了Xilinx公司的xc4v1x60，仿真環(huán)境是xilinxISE6．0，moddsim SE 5．5e，在布線后的時(shí)序報(bào)告中得到的系統(tǒng)可以在70MHz的時(shí)鐘上對(duì)信號(hào)進(jìn)行實(shí)時(shí)的處理。在時(shí)序仿真中我們選用了50MHz的時(shí)鐘，連續(xù)輸入兩幀數(shù)據(jù)(每幀數(shù)據(jù)15bit)，一幀是正確的碼字(100010100110l1)，一幀是錯(cuò)誤的碼字(10001010001111)，普通算法在延遲23個(gè)時(shí)鐘周期后輸出結(jié)果，簡化算法在延遲20個(gè)周期后輸出結(jié)果。根據(jù)譯碼速度計(jì)算公式：譯碼速率=(幀長*系統(tǒng)頻率)僻碼一幀所需要的時(shí)鐘周期數(shù)，則兩種算法的譯碼速率分別為32Mbps，37Mbps。

5 結(jié)論
    在本文中我們利用FPGA實(shí)現(xiàn)了基于BM迭代譯碼算法的BCH碼譯碼器，并根據(jù)FPGA塊ROM資源充足的的優(yōu)勢(shì)，采用基于冪次的運(yùn)算方式，合理地對(duì)．BM流程算法進(jìn)行模塊劃分，同時(shí)實(shí)現(xiàn)了簡化的BM算法，縮短了譯碼延遲，提高了整個(gè)譯碼器的譯碼速度。計(jì)算機(jī)仿真結(jié)果表明，本設(shè)計(jì)所實(shí)現(xiàn)的BCH譯碼性能基本滿足傳輸要求，為后續(xù)長BCH碼的硬件實(shí)現(xiàn)作了較好的鋪墊。