BCH三種譯碼算法之比較

BCH譯碼中三種譯碼算法之比較北京大學(xué)微電子系SoC實驗室BCH三種譯碼算法之比較龍進(jìn)凱崔小欣北京大學(xué)信息科學(xué)技術(shù)學(xué)院微電子學(xué)研究院摘要本文從BCH譯碼中錯位多項式的求解這一關(guān)鍵步驟入手，詳細(xì)分析了彼得森算法（Peterson）、伯利坎普算法（Berlekamp）和歐幾里得算法（Euclidean）這三種譯碼算法的數(shù)學(xué)原理，并給出了三種算法相應(yīng)的硬件實現(xiàn)。文章的最后還給出了三種算法的實現(xiàn)比較，希望能夠?qū)CH譯碼工作起到一定的參考價值。關(guān)鍵詞：錯位多項式，彼得森算法，伯利坎普算法，歐幾里得算法1引言二進(jìn)制BCH譯碼一般來說分為四個步驟，如圖1所示。首先根據(jù)接收到的碼字R(x)來計算伴隨多項式S(x)，然后通過伴隨多項式S(x)的系數(shù)S1，S2，…,S2t(t為最多可糾正的錯誤個數(shù))來計算錯誤位置多項式σ(x)，最后再根據(jù)錯誤位置多項式σ(x)的系數(shù)σ1，σ2，…,σt利用Chien搜索算法來求出錯誤位置并對接收碼字進(jìn)行糾錯譯碼。圖SEQ圖\*ARABIC\s11譯碼器結(jié)構(gòu)框圖在上述的四個步驟中，決定BCH譯碼器的復(fù)雜性和速度的關(guān)鍵在于錯位多項式σ(x)系數(shù)的計算。因此，本文著重對錯位多項式σ(x)的各種計算方法以及相應(yīng)的硬件實現(xiàn)展開討論。2算法描述2.1彼得森（Peterson）譯碼算法定義錯誤圖案為，則有 （STYLEREF3\s2.11）若傳輸過程中有個錯誤，則對于，有 （STYLEREF3\s2.1SEQ公式\*ARABIC\s32）令，則有 （STYLEREF3\s2.1SEQ公式\*ARABIC\s33）稱為錯誤位置。定義錯誤位置多項式 （STYLEREF3\s2.1SEQ公式\*ARABIC\s34）的根的倒數(shù)為。因此需要求出錯誤位置多項式的系數(shù)。的系數(shù)可以通過解下面的方程組得出： （STYLEREF3\s2.1SEQ公式\*ARABIC\s35）這種通過直接解方程組來得到錯位多項式系數(shù)的方法稱為彼得森(Peterson)譯碼算法。假設(shè)某種碼的糾錯能力t=2，則方程（2.1-5）變?yōu)椋⊿TYLEREF3\s2.16）從而解得，2.2伯利坎普（Berlekamp）譯碼算法令 （2.21）且滿足 稱式2.2-1為Berlekamp關(guān)鍵方程。滿足方程2.2-1的解不唯一，而由最小距離譯碼原理，求得的應(yīng)該是對應(yīng)發(fā)生錯誤碼元最少的錯誤圖案，即是次數(shù)最低的解，記作。求一個，使得 （2.22）滿足 解關(guān)鍵方程的迭代步驟如下：設(shè)；若，則 若，則 其中，且有最大值；如果，則迭代結(jié)束，否則執(zhí)行4)；令，計算 回到2)。2.3歐幾里得（Euclidean）譯碼算法定義錯誤值多項式 （2.31）且滿足 式2.3-1的等價表達(dá)為 （2.32）其中，是除以的商，是余數(shù)?？捎上旅鎯墒介_始迭代計算得到： 具體迭代步驟如下：初始化，迭代次數(shù)；，；，；如果，則停止迭代；否則就進(jìn)行以下運算：，；，；，；如果，；否則，；；迭代次數(shù)，返回2）。當(dāng)進(jìn)行完2t次迭代計算后，的個系數(shù)中的高個為錯誤位置多項式的個系數(shù)。3硬件實現(xiàn)下面我們以（15,7）二元BCH碼（最多可以糾正2個隨機錯誤）為例，將以上的三種譯碼算法分別用硬件描述語言加以實現(xiàn)，以供比較。1）對于彼得森（Peterson）算法，如果輸入的伴隨多項式的系數(shù)S1=S2=S3=S4=0，則表示接收到的碼字沒有錯誤，那么相應(yīng)的錯位多項式的系數(shù)σ1=σ2=0；有一個或者兩個錯誤時的情況如下：2）對于改進(jìn)的伯利坎普（Berlekamp）算法，有一個或者兩個錯誤時的情況如下：3）對于歐幾里得（Euclidean）算法，有一個或者兩個錯誤時的情況如下：4分析比較從以上的仿真結(jié)果可以看出，對于三種算法，同樣的一組伴隨多項式的系數(shù)得到了相同的錯位多項式的系數(shù)；但是三種算法所花費的計算時間是不一樣的。Peterson算法對于三種情況（接收碼字沒有錯誤、有一個錯誤、有兩個錯誤）來說計算時間都是相等的，都只要經(jīng)過2拍就能得到結(jié)果；Berlekamp算法對于接收碼字沒有錯誤或者只有一個錯誤時，也只需要2拍就能得到結(jié)果，但是對于兩個錯誤，該算法則需要（t+e+2=6）拍；而Euclidean算法對于接收碼字有一個或兩個錯誤的情況則分別需要（2t+4=8）拍和（4t+7=15）拍來得到結(jié)果。對三種算法的硬件描述進(jìn)行FPGA綜合，結(jié)果如下（所選器件為XilinxVirtex2:XC2V40:CS144:-6）：1）三種算法在該器件上可以達(dá)到的最高頻率如下表所示：算法RequestedFrequencyEstimatedFrequency彼得森（Peterson）算法250.0MHz259.5MHz伯利坎普（Berlekamp）算法120.0MHz121.0MHz歐幾里得（Euclidean）算法120.0MHz128.6MHz2）三種算法在最高頻率下所占用的資源情況如下表所示：算法時序邏輯（使用率）組合邏輯（使用率）IOPADS彼得森（Peterson）算法60(11%)281(54%)28伯利坎普（Berlekamp）算法99(19%)232(45%)28歐幾里得（Euclidean）算法137(26%)438(85%)285結(jié)論綜合以上考慮，當(dāng)二元BCH碼的糾錯能力t=2時，彼得森算法相對于另外兩種算法來說，無論是速度方面還是所占用資源方面都具有很大的優(yōu)勢，因此應(yīng)當(dāng)優(yōu)先采用；但是當(dāng)糾錯能力t變得很大時，直接求解方程組（2.1-5）幾乎變得不可能，這時