胡雪川，劉會(huì)杰

（1.上海微小衛(wèi)星工程中心 上?！?01210；2.上海科技大學(xué) 信息學(xué)院，上海200031）

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

胡雪川1，2，劉會(huì)杰1

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

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

RS譯碼器；FPGA；改進(jìn)型BM算法；流水線

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

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

在近十年，國(guó)內(nèi)對(duì)糾錯(cuò)碼的研究也越來(lái)越重視，許多行業(yè)都根據(jù)自身的特點(diǎn)把糾錯(cuò)碼應(yīng)用到實(shí)際場(chǎng)合中以此來(lái)改善其行業(yè)系統(tǒng)性能。

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

1　RS碼結(jié)構(gòu)及其譯碼原理

1.1RS碼的結(jié)構(gòu)

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

1）碼長(zhǎng):n=255，為 RS（255，239）碼一個(gè)碼字所包含的符號(hào)個(gè)數(shù)；

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

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

4）糾錯(cuò)能力：t=8，為 RS（255，239）碼一個(gè)碼字內(nèi)所能糾正的最大錯(cuò)誤符號(hào)個(gè)數(shù)；

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

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

1.2RS碼的譯碼原理

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

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

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

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

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

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

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

2）根據(jù)已得到的伴隨式計(jì)算關(guān)鍵方程得到錯(cuò)誤位置多項(xiàng)式；

3）根據(jù)錯(cuò)誤位置多項(xiàng)式得到錯(cuò)誤位置；

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

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

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

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

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

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

1.2.2改進(jìn)的BM算法模塊

當(dāng)2t個(gè)伴隨式都求出后，錯(cuò)誤位置多項(xiàng)式Λ（x）就可以通過(guò)改進(jìn)的BM算法來(lái)求解了。

因?yàn)樽钤缣岢龅腂M算法需要用到有限域元素求逆運(yùn)算。這種算法在每次迭代中都需要有限域的除法運(yùn)算，有限域求逆（除法）運(yùn)算很復(fù)雜，其復(fù)雜性使得這種算法不適合高速實(shí)現(xiàn)。因此，人們提出無(wú)需求逆的BM算法[4-6]，改進(jìn)后的算法過(guò)程如下：

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時(shí)，循環(huán)結(jié)束：

當(dāng)Δ（k-1）=0或者2L（k）>k時(shí)，

否則當(dāng)Δ（k-1）≠0或者2L（k）≤k時(shí)，

其中，Λ（k-1）（x）是錯(cuò)誤位置多項(xiàng)式。

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

圖3　FIR濾波器計(jì)算ΔFig.3　Computing Δ using FIR filter

1.2.3Chien搜索算法模塊

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

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

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

1.2.4Forney算法模塊

在求出等價(jià)的錯(cuò)誤位置多項(xiàng)式Λ（x）后，可以利用等價(jià)的錯(cuò)誤計(jì)算多項(xiàng)式Ω（x）[6-7]，即

因?yàn)棣福▁）的結(jié)果為modx2t，所以的最高次數(shù)為2t-1。因此，對(duì)于RS（255，239），Ω（x）可表示為：

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

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

在計(jì)算錯(cuò)誤值ei時(shí)，還需要計(jì)算錯(cuò)誤位置多項(xiàng)式Λ（x）的導(dǎo)數(shù)Λ′（x）。Λ（x）可表示為：

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

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

1.2.5先入先出緩存模塊

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

對(duì)于RS（255，239）碼而言，

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

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

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

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

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

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

在第一次時(shí)序仿真測(cè)試中，錯(cuò)碼為1組連續(xù)3個(gè)錯(cuò)碼，2組連續(xù)2個(gè)錯(cuò)碼，1個(gè)錯(cuò)碼，將這4組錯(cuò)碼隨機(jī)分布在碼組中（括號(hào)內(nèi)為正確值）：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譯碼器糾錯(cuò)仿真一Fig.6　The first error correction simulation of RS decoder

通過(guò)本譯碼器糾錯(cuò)后仿真結(jié)果如圖6（a）、圖6（b）所示。

在第二次時(shí)序仿真測(cè)試中，錯(cuò)碼為1組連續(xù)8個(gè)錯(cuò)碼，將這組錯(cuò)碼隨機(jī)分布在碼組中 （括號(hào)內(nèi)為正確值）：

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

通過(guò)本譯碼器糾錯(cuò)后仿真結(jié)果如圖7所示。

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

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

3　結(jié)束語(yǔ)

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

[1]陸松.基于DVB標(biāo)準(zhǔn)的RS糾錯(cuò)編解碼器的設(shè)計(jì)與實(shí)現(xiàn)計(jì)與實(shí)現(xiàn)[D].桂林：桂林電子科技大學(xué)，2009.

[2]石俊峰，王宇，孫輝先.符合CCSDS標(biāo)準(zhǔn)的RS（255，223）碼譯碼器的 FPGA實(shí)現(xiàn)及其性能測(cè)試[J].空間科學(xué)學(xué)報(bào)，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譯碼器算法研究與實(shí)現(xiàn)[D].蘇州：蘇州大學(xué)，2010.

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

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

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

[9]任朋利，劉峰華，邵志豪.引信RS422總線全雙工通訊裝定方法[J].電子設(shè)計(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稿件編號(hào)：201506141

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

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