基于FPGA的RS（255，239）譯碼器的設計與實現(xiàn)

胡雪川，劉會杰

（1.上海微小衛(wèi)星工程中心 上?！?01210；2.上?？萍即髮W 信息學院，上海200031）

基于FPGA的RS（255，239）譯碼器的設計與實現(xiàn)

胡雪川1，2，劉會杰1

（1.上海微小衛(wèi)星工程中心 上海201210；2.上?？萍即髮W 信息學院，上海200031）

為了解決在RS譯碼中存在的譯碼過程復雜、譯碼速度慢和專用譯碼器價格高等問題，以RS（255，239）碼為例，采用了基于改進的無求逆運算的 Berlekamp-Massey（BM）迭代算法。結合FPGA平臺，利用Xilinx ISE軟件和Verilog硬件描述語言，對譯碼器中各個子模塊進行了設計和仿真。整個譯碼器設計過程采用流水線處理方式。時序仿真結果表明在保證錯誤符號不大于8個的情況下，經(jīng)過295個固有延遲之后，每個時鐘周期均可連續(xù)輸出經(jīng)校正的碼字，該RS譯碼器的糾錯能力能夠達到預期要求。

RS譯碼器；FPGA；改進型BM算法；流水線

Reed-Solomon（RS）碼是一類具有很強糾錯能力的BCH碼，可以同時糾正突發(fā)錯誤和隨機錯誤，目前已經(jīng)被廣泛應用在各種通信系統(tǒng)中。很多國際標準采用了RS碼，例如在遙測信道編碼中將 RS（255，223）系統(tǒng)碼作為標準使用。

美國的蜂窩數(shù)字分組數(shù)據(jù)系統(tǒng) （CDPD）中采用了（63，47）RS碼。在數(shù)字電視領域中，DVB標準中使用的都是RS（204，188），ATSC標準中使用的是RS（207，187）[1]。

在近十年，國內對糾錯碼的研究也越來越重視，許多行業(yè)都根據(jù)自身的特點把糾錯碼應用到實際場合中以此來改善其行業(yè)系統(tǒng)性能。

文中以光纖通信中采用的RS（255，239）碼為例，詳細分析了基于改進的無求逆運算的 Berlekamp-Massey（BM）迭代算法的 RS譯碼原理，并用 Xilinx公司的可編程邏輯門陣列（FPGA）芯片進行了設計和實現(xiàn)。

1　RS碼結構及其譯碼原理

1.1RS碼的結構

根據(jù)CCSDS相關規(guī)定，RS（255，239）碼[2]參數(shù)如下：

1）碼長:n=255，為 RS（255，239）碼一個碼字所包含的符號個數(shù)；

2）信息位:k=239，為 RS（255，239）碼一個碼字信息位的符號個數(shù)；

3）校驗位：2t=n-k=16，為RS（255，239）碼一個碼字檢驗位的符號個數(shù)；

4）糾錯能力：t=8，為 RS（255，239）碼一個碼字內所能糾正的最大錯誤符號個數(shù)；

5）每個符號數(shù)：m=8，為RS（255，239）碼一個符號數(shù)表示信息位個數(shù)；

6）GF（28）域上的生成多項式為F（x）=x8+x7+x2+x+1；

1.2RS碼的譯碼原理

RS譯碼主要分為時域譯碼和頻域譯碼兩種算法，常見的算法有 PGZ算法、歐式算法 （Euclid's Algorithm）和 BM （Berlekamp-Massey）迭代算法[3-5]。

PGZ算法容易理解，實現(xiàn)起來也簡單，但計算量隨著碼長的增加呈指數(shù)增長，這要求譯碼器的運算速度很高。所以PGZ算法通常只用在實現(xiàn)較短的RS譯碼中。

BM算法可分為時域算法和頻域算法。時域算法主要利用Forney算法和錯誤位置獲取錯誤圖樣。頻域譯碼則是根據(jù)錯誤位置多項式來獲得相應的校驗子序列，然后對所得到的所有校驗子進行傅里葉反變換，從而獲得錯誤圖樣。雖然頻域算法可利用快速傅里葉算法使得譯碼速度大幅度提高，但是實現(xiàn)過程相對比較復雜。

Euclid's算法是通過求解兩個多項式最大公因式，獲得錯誤位置多項式及錯誤值多項式，其它的計算同BM算法。Euclid's算法與BM算法的主要區(qū)別在于關鍵方程計算的迭代過程，BM迭代是基于自回歸濾波器綜合原理求最短反饋連接多項式代數(shù)迭代過程，Euclid迭代是基于多項式分解原理求兩個多項式的最大公因式的迭代過程，需進行多項式次數(shù)的判斷。

在RS譯碼中，求解關鍵方程是最重要的環(huán)節(jié)。根據(jù)以上3種算法的各自特點，結合譯碼器譯碼時延遲小、資源消耗少、電路簡單等設計要求，本文采用改進后無求逆運算的BM迭代時域譯碼算法并以該算法為基礎在FPGA平臺上進行了RS譯碼器的實現(xiàn)。

RS譯碼主要分為5步[3]（如圖1所示）：

1）根據(jù)接收到的碼組計算伴隨式；

2）根據(jù)已得到的伴隨式計算關鍵方程得到錯誤位置多項式；

3）根據(jù)錯誤位置多項式得到錯誤位置；

4）根據(jù)錯誤位置多項式和伴隨式得到錯誤樣值；

5）根據(jù)錯誤位置、錯誤樣值和由先入先出緩存延遲輸出的接收碼組進行錯誤校正。

圖1　RS譯碼器的一般框圖Fig.1　General block diagram of RS decoder

將n=255，b0=1代入，則有：

在工程設計中，通常使用流水線結構硬件實現(xiàn)伴隨式的計算，其計算框架如圖2所示。其中，“茚”代表有限域乘法，“茌”代表有限域加法。模塊初始化時，所有的寄存器被置為0。隨著每個時鐘沿的到來，依次將R1，R2，…，R255移入移位寄存器。16個伴隨式在經(jīng)過 255個時鐘周期之后即可計算出來。如果伴隨式系數(shù)都為0，則表明接收到的碼字全部正確，錯誤個數(shù)為 0；否則錯誤個數(shù)大于0。

圖2　通用伴隨式計算框圖Fig.2　Universal block diagram of syndrome computation

1.2.2改進的BM算法模塊

當2t個伴隨式都求出后，錯誤位置多項式Λ（x）就可以通過改進的BM算法來求解了。

因為最早提出的BM算法需要用到有限域元素求逆運算。這種算法在每次迭代中都需要有限域的除法運算，有限域求逆（除法）運算很復雜，其復雜性使得這種算法不適合高速實現(xiàn)。因此，人們提出無需求逆的BM算法[4-6]，改進后的算法過程如下：

1）初始化：Λ（0）（x）=1，T（0）（x）=1，L（0）（x）=0，γ（0）（x）=1，k=0；

2）下面步驟從式（2）到式（6）循環(huán)迭代，直到k=2t-1時，循環(huán)結束：

當Δ（k-1）=0或者2L（k）>k時，

否則當Δ（k-1）≠0或者2L（k）≤k時，

其中，Λ（k-1）（x）是錯誤位置多項式。

很顯然，式（2）中Δ是Λ（x）與S（x）的卷積和運算。為了實現(xiàn)流水線處理，可以采用有限脈沖響應 （FIR）濾波器技術來實現(xiàn)流水線處理，如圖3所示。初始化時，所有寄存器置0，然后隨著每個時鐘的上升沿到來，依次將S1，S2，…，S2t移入移位寄存器，最終可得到錯誤位置多項式Λ（x）的各個系數(shù)。

圖3　FIR濾波器計算ΔFig.3　Computing Δ using FIR filter

1.2.3Chien搜索算法模塊

求解錯誤位置多項式σ（x）的根，本質就是找出接收多項式R（x）中哪幾位出現(xiàn)錯誤。由于用硬件直接解方程比較復雜，人們通常使用Chien搜索算法來搜索錯誤位置，即搜索解空間所有可能發(fā)生錯誤的位置來求根。根據(jù)有限域性質，當σ（αi）=0時差錯位置為（n-i），即出錯Rn-i；否則σ（αi）≠0，Rn-i正確。

圖4　Chien搜索模塊框架Fig.4　Chien search module frame

具體實現(xiàn)方法是，依次將有限域元素的倒數(shù)（即σ（x）的根）α-（n-1），α-（n-2），…α-1，1代入等價的錯誤位置多項式 Λ（x）。若Λ（α-i）=0，則可斷定該位置出現(xiàn)了誤碼[5]。等效的實現(xiàn)框圖如圖4所示。

1.2.4Forney算法模塊

在求出等價的錯誤位置多項式Λ（x）后，可以利用等價的錯誤計算多項式Ω（x）[6-7]，即

因為Ω（x）的結果為modx2t，所以的最高次數(shù)為2t-1。因此，對于RS（255，239），Ω（x）可表示為：

Ω（x）的系數(shù)可分別表示為：

可以看出，兩個多項式的相乘其實質是多項式對應的系數(shù)卷積求和。因此式（9）運算也可以用FIR濾波器技術來實現(xiàn)。

在計算錯誤值ei時，還需要計算錯誤位置多項式Λ（x）的導數(shù)Λ′（x）。Λ（x）可表示為：

對于RS（255，239）碼而言，Λ（x）=Λ0+Λ1x+Λ2x2+…+Λ8x8。根據(jù)有限域的知識，域GF（qm）的特征為q，即域中的任一元素累加q次的和為0。所以，對于RS（255，239）碼而言，錯誤位置多項式Λ（x）的導數(shù)Λ′（x）可表示為：

根據(jù)式（12）和事先存好求逆查找表，即可求出錯誤樣值。

1.2.5先入先出緩存模塊

先入先出（FIFO，F(xiàn)irst In First Out）是一種用于存儲、緩沖不同時鐘之間的數(shù)據(jù)傳輸?shù)碾娐贰S譯碼器檢錯糾錯需要一定的時間延遲，需要設計 FIFO控制器來實現(xiàn)接收數(shù)據(jù)的緩存。本文中并未單獨設計FIFO，而是使用了ISE系統(tǒng)庫中的FIFO模塊，固有延遲時間為295個周期。

對于RS（255，239）碼而言，

2　RS譯碼器的FPGA實現(xiàn)與仿真

采用XIlinx公司生產(chǎn)的Virtex4芯片XC4VSX55，在ISE 13.4環(huán)境下，結合圖1所示的流程對RS譯碼器進行了設計，設計完成的RS譯碼器模塊截圖如圖5所示。

圖5　RS譯碼器模塊Fig.5　RS decoder module

圖5中，輸入信號為clk，Din[7..0]和sync。輸出信號為Err_Indicator、BLK_STRT_output、BLK_END_output、INFO_END_output和Dout[7..0]。

其中，在輸入信號中，clk為時鐘，Din[7..0]為接收到的并已經(jīng)編碼好之后的碼組，sync為同步信號，且高脈沖的時候表示譯碼器開始工作。在輸出信號中，Err_Indicator用來指示錯誤位置，BLK_STRT_output為高脈沖時，表示經(jīng)過糾錯的完整碼組的起始位置，BLK_END_output為高脈沖時，表示經(jīng)過糾錯的完整碼組的結束位置，INFO_END_output為高脈沖時，表示經(jīng)過糾錯的完整信息位的結束位置，Dout[7..0]為經(jīng)過糾錯的完整碼組。

仿真過程中，在事先由MATLAB計算出的一組正確的RS（255，239）碼（設定該碼字的信息位為1到239，則計算可得校驗碼為 37，133，225，126，37，59，132，133，56，168，179，4，9，99，79，148）中輸入錯碼，為體現(xiàn) RS譯碼器糾錯能力，分別進行兩次測試。

在第一次時序仿真測試中，錯碼為1組連續(xù)3個錯碼，2組連續(xù)2個錯碼，1個錯碼，將這4組錯碼隨機分布在碼組中（括號內為正確值）：1，2，19（3），20（4），37（5），6，7，24（8），41（9），10，11，44（12），29（13），14，15，64（16），17，18，…，238，239，…，79，148

圖6　RS譯碼器糾錯仿真一Fig.6　The first error correction simulation of RS decoder

通過本譯碼器糾錯后仿真結果如圖6（a）、圖6（b）所示。

在第二次時序仿真測試中，錯碼為1組連續(xù)8個錯碼，將這組錯碼隨機分布在碼組中 （括號內為正確值）：

1，2，3，...，33，34，66（35），53（36），41（37），152（38），119 （39），135（40），85（41），67（42），43，44，...，239，...，79，148

通過本譯碼器糾錯后仿真結果如圖7所示。

圖7　RS譯碼器糾錯仿真二Fig.7　The second error correction simulation of RS decoder

如圖6、圖7所示，錯誤位置Err_Indicator與預期結果一致。此外，RS[8-10]譯碼器將接收碼組中出現(xiàn)的8個隨機錯碼和連續(xù)錯碼全部糾正為正確碼字，實現(xiàn)了譯碼糾錯的功能。此外，還可以正確地指示出譯碼后整個碼字的起始、結束位置和信息位結束位置。在保證錯誤符號不大于8個的情況下，每個時鐘周期均可連續(xù)輸出經(jīng)校正的碼字。

3　結束語

文中根據(jù)改進的無求逆運算的BM迭代譯碼算法，實現(xiàn)了RS（255，239）譯碼器的設計。在對譯碼器的測試過程中，分別假定出現(xiàn)隨機出現(xiàn)8個誤碼和連續(xù)8個誤碼的情況，并用ISim對所設計的譯碼器進行驗證。由時序仿真結果表明，設計的RS（255，239）譯碼器正確有效，該RS譯碼器的糾錯能力能夠達到預期要求。

[1]陸松.基于DVB標準的RS糾錯編解碼器的設計與實現(xiàn)計與實現(xiàn)[D].桂林：桂林電子科技大學，2009.

[2]石俊峰，王宇，孫輝先.符合CCSDS標準的RS（255，223）碼譯碼器的 FPGA實現(xiàn)及其性能測試[J].空間科學學報，2005，25（4）:309-314.

[3]You J，Wu S.Design and realization of Reed-Solomon code based on FPGA technique[C]//Mechatronic Science，Electric Engineering and Computer（MEC），2011 International Conference on.IEEE，2011:2086-2089.

[4]王鋒.RS譯碼器算法研究與實現(xiàn)[D].蘇州：蘇州大學，2010.

[5]莫新康，牛強軍，宋家友.基于 FPGA的 RS譯碼器的設計與實現(xiàn)[J].信息安全與通信保密，2010（12）:84-85.

[6]劉福奇，劉波.Verilog HDL應用程序設計實例精講[M].北京：電子工業(yè)出版社，2009.

[8]王鵬，涂友超，龔克.彈載數(shù)據(jù)鏈系統(tǒng)實時RS譯碼器設計[J].電訊技術，2015（5）:527-532.

[9]任朋利，劉峰華，邵志豪.引信RS422總線全雙工通訊裝定方法[J].電子設計工程，2014（3）:66-68.

[10]孟凱.基于FPGA的RS（255，239）編譯碼器[J].電子科技，2014（8）:33-35.

Design and implementation of RS（255，239）decoder based on FPGA

HU Xue-chuan1，2，LIU Hui-jie1
（1.Shanghai Engineering Center For Microsatellites，Shanghai 201210，China；2.School of Information Science and Technology，ShanghaiTech University，Shanghai 200031，China）

In order to solve the problem such as the complexity of RS decoding process，low decoding speed，expensive specific RS decoder and so on that exists when the RS code is decoded，the RS（255，239）code is taken as an example，and the RS decoding theory based on the improved non-inversion Berlekamp-Massey（BM）iterative algorithm is introduced. On the FPGA platform，each submodule of the decoder has been designed and simulated by using the Verilog hardware description language and the software of Xilinx ISE 13.4.Pipeline approach is used in the entire decoder design process. Timing simulation results show that if there exists no more than eight errors，after 295 inherent delay，the decoder can output the corrected code word continuously in each clock cycle，and the ability of error correcting of RS decoder meets the expectations.

RS decoder；FPGA；improved BM algorithm；pipeline

TN914

A

1674－6236（2016）01-0099-04

2015-06-14稿件編號：201506141

國防科技創(chuàng)新基金（CXJJ-15S086）

胡雪川（1993—），男，江西吉安人，碩士研究生。研究方向：衛(wèi)星通信信號處理。