摘 要：介紹了運用于RS譯碼中的BM迭帶算法及利用BM迭帶進行RS譯碼的基本原理，同時給出了該算法的FPGA實現(xiàn)，并通過在高清晰度數(shù)字電視接收機中驗證了設計的可行性與可靠性。
關鍵詞：RS譯碼；BM迭帶算法；FPGA；高清晰度數(shù)字電視
一、 引言
RS碼是一類具有很強的糾錯能力的BCH碼，也是一類典型的代數(shù)幾何碼，它首先由里德（Reed）和索羅蒙（Solomon）應用MS多項式于1960年構造出來。在一般的應用中 ，RS碼可以作為單碼單獨使用；而在信道條件極為惡劣的應用中，如移動通信、衛(wèi)星通信等具有多徑衰落特性的信道中，也可以作為外碼提供糾錯能力更強的串行級聯(lián)碼，這樣在不增加譯碼復雜度的情況下，可以得到高的編碼增益和與長碼相同的糾錯能力，最常見的一種結構就是將RS碼作為外碼，卷積碼作內(nèi)碼的級聯(lián)碼。RS譯碼主要有時域譯碼和頻域譯碼，時域譯碼通常采用BM迭代算法或者歐式算法(Euclid′s Algorithm)。本文主要介紹BM迭代算法原理及以此算法為基礎的RS譯碼器的FPGA實現(xiàn)。
RS譯碼可分為3步：第一步由接收到的碼組計算伴隨式；第二步由伴隨式計算出錯誤圖樣；最后由錯誤圖樣和接收碼組計算出可能發(fā)送的碼字。
二、BM迭代譯碼算法的基本原理
時域上的RS譯碼的關鍵在于求解錯誤位置多項式,1966年伯利坎普（Berlekamp）提出了可以由伴隨式計算錯誤位置多項式的迭代譯碼算法，這極大地加快了求解錯誤位置多項式的速度，該方法簡單且易于實現(xiàn)，從而從工程上解決了RS譯碼的問題；1969年梅西（Massey）指出了該算法與序列的最短線形移位寄存器綜合之間的關系，并進行了簡化，因此，此譯碼算法就稱為BM迭代譯碼算法。
如果由接收碼組已經(jīng)求出了伴隨式S=［S1,S2,…,S2t］,其中，t為RS碼的糾錯距離,記S(x)=1+
上式即為求解錯誤位置多項式的關鍵方程，且
它其實說明了S(x)σ(x)的最高次數(shù)不會大于2t。在上式中，S(x)是已知的，因此，可以利用上式進行迭代。先人為設定σ(x)和ω(x)的初始值，然后以此初始值表示下一次迭代的結果，并使得下一迭代結果的次數(shù)不減，如此反復迭代求出滿足(1)式的方程即可。由于每一次迭代都使得σ(x)和ω(x)的次數(shù)不減，故迭代至第j步時，應有：
通常，滿足(2)式的每一步迭代都不是唯一的，因此必須對迭代過程加以條件限制。
在m進制無記憶離散對稱信道中，如果信道轉移概率p<1/m，則信道產(chǎn)生錯誤個數(shù)少的可能性最大，即σ(x)次數(shù)越低的可能性越大。故如果每一次迭代都能保證求的σj(x)次數(shù)最低，且滿足此時的譯碼結果就是滿足譯碼錯誤概率最小的最大似然譯碼，并且此時的解是唯一的。
其中i是j前面的某一行，且滿足
最大，這樣能保證每次迭代總是使σ(x)的次數(shù)最小化。因此，令j=-1和0，得到兩組初始值，利用(3)式求出dj，再結合(４)式和(５)式即可得到下一步的結果。迭代步驟如下：
否則，由(4)式和(5)式求出σj+1（x)、ωj+1(x)，然后進行下一次迭代。
三、FPGA實現(xiàn)及調試
1.FPGA實現(xiàn)電路
該算法的FPGA實現(xiàn)電路如圖1所示。
其中，Syndrome模塊主要完成伴隨式的計算，Dj和Di模塊分別完成dj和dj/di的計算，Iterater模塊則完成迭代的更新及計算，Sj和Oj分別為需要求出的σj(x)和ωj(x)。當同步信號SYN到來時，所有模塊完成初始化，di、Sj和Oj初始化為1。Syndrome模塊求出伴隨式Spoly后串行輸出，同時將此刻的迭代次數(shù)Ite－Num輸出，而且當?shù)_到要求的次數(shù)時，輸出一個CLR信號，在Dj模塊接收到此信號后，將dj置為0，于是后面的輸出不再改變，直到下一同步信號SYN到來；Dj模塊用一組移位寄存器將伴隨式的當前狀態(tài)和之前的t個狀態(tài)緩存,和當前Sj一起可以求出dj,當dj不為0時，同時計算
輸出到J－rank中；為了讓下一步的計算更簡單，Di模塊中計算直接dj/di和rank=j-i的值，di的逆元用一個查找表來完成，同時預設
=0，當該值小于J－rank時，將此時的存儲值作相應的更新，同時輸出一個fresh信號以標明這種更新；Iterater模塊在收到fresh信號后進行相應的更新。
在設計過程中，可以將(4)式和(５)式中求滿足i-
一個完整的RS譯碼原理框圖如圖2所示。其中，伴隨式計算電路由輸入的碼組計算出相應的伴隨式，同時將結果送到下一模塊中，該模塊即為實現(xiàn)BM迭代算法的電路。伴隨式經(jīng)BM迭代后，計算出錯誤位置多項式σ(x),同時也計算出ω(x)。Chien搜索電路則由給定的σ(x)找出錯誤位置，然后控制門打開或者關閉，當該位置有錯時，門打開，輸出該位置上的錯誤值，當該位置沒有錯時，門關閉，此時錯誤值為0。利用σ(x)和ω(x)可以進行錯誤值的計算。因為整個譯碼過程中存在延遲，為使相應的數(shù)據(jù)互相對齊而必須加入一個移位存儲器。
2.電路調試
經(jīng)過軟件仿真和硬件電路仿真后，就需要將編譯后的程序下載到實際的FPGA芯片中調試，以驗證實際電路的正確性和可靠性，這是電路設計中的一個重要步驟。軟件仿真主要是產(chǎn)生正確的數(shù)據(jù)源以驗證硬件電路仿真的結果，軟件仿真主要采用的是Matlab6.1。Matlab是Mathworks公司推出的一套仿真軟件，其數(shù)學運算功能非常強大，是工程中一種非常理想的仿真工具，在調試過程中主要是提供調試數(shù)據(jù)、結果數(shù)據(jù)，包括中間結果。硬件電路仿真是用電路設計軟件完成電路設計，我們使用的是ALTERA公司的Quartus2.0軟件，再進行編譯、仿真，仿真的結果要與上面Matlab的仿真結果一致。
當上面的驗證完成后，就可將編譯后的程序下載到實際的FPGA芯片中調試，然后用邏輯分析儀隨機抓取數(shù)據(jù)，保存到文件中，并與Matlab仿真的結果進行比較，如果不正確，則對電路中的每一模塊進行查錯、修改，直到用邏輯分析儀隨機抓取數(shù)據(jù)完全正確為止，此時可認為電路調試完成。Quartus2.0電路仿真結果如圖3。
圖3的仿真圖給出了在GF(256)內(nèi)用Quartus2.0進行BM迭代算法的電路仿真結果，為了進行詳細對比，我們將每一次迭代結果都保留下來。經(jīng)比較，該結果和Matlab仿真的結果完全一致。
四、結語
本文的FPGA實現(xiàn)是用Verilog硬件描述語言編寫，并在Altera公司QuartusⅡ電路仿真環(huán)境下仿真、選用該公司APEX TM EP20K600EBC652—1XES系列芯片來完成的，結合別的FEC模塊，將其應用于數(shù)字高清晰度電視(HDTV)接收機機頂盒的設計中，經(jīng)過性能測試，達到了系統(tǒng)指標要求。而且由于該設計是用Verilog硬件描述語言編寫調試的，因此，可移植性較強。在調試通過后，將該模塊植入基于Xilinx的Virtex2系列芯片設計的電路中同樣能滿足系統(tǒng)要求。因此，該設計不僅可以和別的FEC技術結合，提供強大的糾錯能力，同時，也可以專門應用于ASIC設計中。與此同時，我們也用FPGA實現(xiàn)了基于歐式算法的RS譯碼器，但比較而言，BM迭代算法較為簡單，易于實現(xiàn)，且比歐式算法能節(jié)省一半左右的資源。
參考文獻
［１］王新梅，肖國鎮(zhèn).糾錯碼［Ｍ］.西安：西安電子科技大學出版社，2001.
［２］Donald E Thomas, Philip R Moorby,劉明業(yè)，等.硬件描述語言Verilog［Ｍ］.北京：清華大學出版社，2001.
［３］劉寶琴，張芳蘭，田立生. Altera 可編程邏輯器件及其應用［Ｍ］.北京：清華大學出版社，1995.
［４］郝東來.COFDM傳輸系統(tǒng)中編解碼技術的研究［Ｄ］. 西安：西安電子科技大學.
