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

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

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

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

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

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

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