RS譯碼的BM迭代算法及其FPGA實現(xiàn)

1、RS譯碼的BM迭代算法及其FPGA實現(xiàn)發(fā)布日期:2006-04-21作者:張輔云 葛建華 來源：電訊技術(shù)TQ2440+3. 5寸寸TFT觸摸屏 58。元送USB轉(zhuǎn)串口線摘 要：介紹了運用于RS譯碼中的BM迭帶算法及利用BM迭帶進(jìn)行RS譯碼的基本原理，同時給 出了該算法的FPGA實現(xiàn)，并通過在高清晰度數(shù)字電視接收機(jī)中驗證了設(shè)計的可行性與可靠性。關(guān)鍵詞：RS譯碼；BM迭帶算法；FPGA；高清晰度數(shù)字電視一、引言RS碼是一類具有很強(qiáng)的糾錯能力的BCH碼，也是一類典型的代數(shù)幾何碼，它首先由里德(Reed) 和索羅蒙(Solomon)應(yīng)用MS多項式于1960年構(gòu)造出來。在一般的應(yīng)用中，RS碼可以作為單碼

2、單獨 使用；而在信道條件極為惡劣的應(yīng)用中，如移動通信、衛(wèi)星通信等具有多徑衰落特性的信道中，也可 以作為外碼提供糾錯能力更強(qiáng)的串行級聯(lián)碼，這樣在不增加譯碼復(fù)雜度的情況下，可以得到高的編碼 增益和與長碼相同的糾錯能力，最常見的一種結(jié)構(gòu)就是將RS碼作為外碼，卷積碼作內(nèi)碼的級聯(lián)碼。 RS譯碼主要有時域譯碼和頻域譯碼，時域譯碼通常采用BM迭代算法或者歐式算法(EuclidsAlgorithm)。本文主要介紹BM迭代算法原理及以此算法為基礎(chǔ)的RS譯碼器的FPGA實現(xiàn)。RS譯碼可分為3步：第一步由接收到的碼組計算伴隨式；第二步由伴隨式計算出錯誤圖樣；最后 由錯誤圖樣和接收碼組計算出可能發(fā)送的碼字。二、BM迭

3、代譯碼算法的基本原理時域上的RS譯碼的關(guān)鍵在于求解錯誤位置多項式,1966年伯利坎普(Berlekamp)提出了可以由 伴隨式計算錯誤位置多項式的迭代譯碼算法，這極大地加快了求解錯誤位置多項式的速度，該方法簡 單且易于實現(xiàn)，從而從工程上解決了 RS譯碼的問題；1969年梅西(Massey)指出了該算法與序列的 最短線形移位寄存器綜合之間的關(guān)系，并進(jìn)行了簡化，因此，此譯碼算法就稱為BM迭代譯碼算法。如果由接收碼組已經(jīng)求出了伴隨式S=耳疽,其中，t為RS碼的糾錯距離,記S(x)=1+ 命+中錯誤位置舉項式r(x) = I + 0 x+ 電J令*=to(x) ,則經(jīng)過一系列椎恥可知S(x)(x)和y

4、(x)滿足下式：(x) KiJ，f1 )( I)上式即為求解錯誤位置多項式的關(guān)鍵方程，且它其實說明了 S(x)o (x)的最 高次數(shù)不會大于2t。在上式中，S(x)是已知的，因此，可以利用上式進(jìn)行迭代。先人為設(shè)定o (x)和3 (x)的初始值，然后以此初始值表示下一次迭代的結(jié)果，并使得下一迭代結(jié)果的次數(shù)不減，如此反 復(fù)迭代求出滿足(1)式的方程即可。由于每一次迭代都使得O(X)和3(X)的次數(shù)不減，故迭代至第j 步時，應(yīng)有：鋼損/(*) M(2)通常，滿足(2)式的每一步迭代都不是唯一的，因此必須對迭代過程加以條件限制。在m進(jìn)制無記憶離散對稱信道中，如果信道轉(zhuǎn)移概率p(x)=(*) *1/ (

5、土)= Z)否則由式和式求出O j+1 (如3 j,1 (X)，然后進(jìn)行下一次迭代。三、FPGA實現(xiàn)及調(diào)試1.FPGA實現(xiàn)電路該算法的FPGA實現(xiàn)電路如圖1所示。其中，Syndrome模塊主要完成伴隨式的計算,Dj和Di模塊分別完成dj和dj/di的計算,Iterator 模塊則完成迭代的更新及計算，Sj和Oj分別為需要求出的b仲)和3 0。當(dāng)同步信號SYN到來時, 所有模塊完成初始化，di、Sj和Oj初始化為1。Syndrome模塊求出伴隨式Spoly后串行輸出，同時 將此刻的迭代次數(shù)Ite_Num輸出，而且當(dāng)?shù)_(dá)到要求的次數(shù)時，輸出一個CLR信號，在Dj模塊接 收到此信號后，將dj置為0

6、,于是后面的輸出不再改變，直到下一同步信號SYN到來；Dj模塊用一組 移位寄存器將伴隨式的當(dāng)前狀態(tài)和之前的t個狀態(tài)緩存,和當(dāng)前Sj 一起可以求出dj,當(dāng)dj不為0時，同時計算輸出到J_rank中；為了讓下一步的計算更間單，Di模塊中計算直接dj/di和rank=j-i的值，di的逆元用一個查找表來完成，同時預(yù)設(shè). =0,當(dāng)該值小于 J_rank時，將此時的存儲值作相應(yīng)的更新，同時輸出一個fresh信號以標(biāo)明這種更新；Iterater模 塊在收到fresh信號后進(jìn)行相應(yīng)的更新。在設(shè)計過程中，可以將(4)式和(5)式中求滿足i-最大的過程谷略，不用拖索前面的每一 行.這里因為,幔定匪代到J時，滿足

7、i-儼行。最 大的伉為k,則顯然.對于任意iwj - 1.k-護(hù)/(x) 方-臚寸&).旦&不為。.故時于下一步送代如果 可二0,取任、否則.取i為混足卜喝(。和j- Wh)之間的較大者即叫 這樣不僅可以提高電路 的性能村速度，而且也訶以節(jié)省存儲空間白一個完整的RS譯碼原理框圖如圖2所示。其中，伴隨式計算電路由輸入的碼組計算出相應(yīng)的伴隨 式，同時將結(jié)果送到下一模塊中，該模塊即為實現(xiàn)BM迭代算法的電路。伴隨式經(jīng)BM迭代后，計算出 錯誤位置多項式b (x),同時也計算出3 (x)。Chien搜索電路則由給定的b (x)找出錯誤位置，然后 控制門打開或者關(guān)閉，當(dāng)該位置有錯時，門打開，輸出該位置上的錯

8、誤值，當(dāng)該位置沒有錯時，門關(guān) 閉，此時錯誤值為0。利用b (x)和3 (x)可以進(jìn)行錯誤值的計算。因為整個譯碼過程中存在延遲，為 使相應(yīng)的數(shù)據(jù)互相對齊而必須加入一個移位存儲器。2.電路調(diào)試經(jīng)過軟件仿真和硬件電路仿真后，就需要將編譯后的程序下載到實際的FPGA芯片中調(diào)試，以驗 證實際電路的正確性和可靠性，這是電路設(shè)計中的一個重要步驟。軟件仿真主要是產(chǎn)生正確的數(shù)據(jù)源 以驗證硬件電路仿真的結(jié)果，軟件仿真主要采用的是Matlab6.1。Matlab是Mathworks公司推出的一 套仿真軟件，其數(shù)學(xué)運算功能非常強(qiáng)大，是工程中一種非常理想的仿真工具，在調(diào)試過程中主要是提 供調(diào)試數(shù)據(jù)、結(jié)果數(shù)據(jù)，包括中間結(jié)

9、果。硬件電路仿真是用電路設(shè)計軟件完成電路設(shè)計，我們使用的 是ALTERA公司的Quartus2.0軟件，再進(jìn)行編譯、仿真，仿真的結(jié)果要與上面Matlab的仿真結(jié)果一致。當(dāng)上面的驗證完成后，就可將編譯后的程序下載到實際的FPGA芯片中調(diào)試，然后用邏輯分析儀 隨機(jī)抓取數(shù)據(jù)，保存到文件中，并與Matlab仿真的結(jié)果進(jìn)行比較，如果不正確，則對電路中的每一 模塊進(jìn)行查錯、修改，直到用邏輯分析儀隨機(jī)抓取數(shù)據(jù)完全正確為止，此時可認(rèn)為電路調(diào)試完成。 Quartus2.0電路仿真結(jié)果如圖3。圖3的仿真圖給出了在GF(256)內(nèi)用Quartus2.0進(jìn)行BM迭代算法的電路仿真結(jié)果，為了進(jìn)行詳細(xì) 對比，我們將每一次

10、迭代結(jié)果都保留下來。經(jīng)比較，該結(jié)果和Matlab仿真的結(jié)果完全一致。四、結(jié)語本文的FPGA實現(xiàn)是用Verilog硬件描述語言編寫，并在Altera公司QuartusII電路仿真環(huán)境下 仿真、選用該公司APEX TM EP20K600EBC6521XES系列芯片來完成的，結(jié)合別的FEC模塊，將其應(yīng) 用于數(shù)字高清晰度電視(HDTV )接收機(jī)機(jī)頂盒的設(shè)計中，經(jīng)過性能測試，達(dá)到了系統(tǒng)指標(biāo)要求。而且由 于該設(shè)計是用Verilog硬件描述語言編寫調(diào)試的，因此，可移植性較強(qiáng)。在調(diào)試通過后，將該模塊植 入基于Xilinx的Virtex2系列芯片設(shè)計的電路中同樣能滿足系統(tǒng)要求。因此，該設(shè)計不僅可以和別的 FEC技術(shù)結(jié)合，提供強(qiáng)大的糾錯能力，同時，也可以專門應(yīng)用于ASIC設(shè)計中。與此同時，我們也用 FPGA實現(xiàn)了基于歐式算法的RS譯碼器，但比較而言，BM迭代算法較為簡單，易于實現(xiàn)，且比歐式算 法能節(jié)省一半左右的資源。參考文獻(xiàn)王新梅，肖國鎮(zhèn).糾錯碼M.西安：西安電子科技大學(xué)出