《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > RS編碼算法的優(yōu)化與FPGA實(shí)現(xiàn)
RS編碼算法的優(yōu)化與FPGA實(shí)現(xiàn)
2020年電子技術(shù)應(yīng)用第2期
李錦明,，劉夢(mèng)欣,，成乃朋
中北大學(xué) 儀器與電子學(xué)院，山西 太原030051
摘要： 針對(duì)常用RS編碼算法中伽羅華域(Galois Field，GF)的乘法運(yùn)算在FPGA中實(shí)現(xiàn)時(shí)存在的數(shù)據(jù)運(yùn)算量大、復(fù)雜度高等問題，對(duì)RS編碼模塊進(jìn)行優(yōu)化，通過增加乘法器因子求取模塊，完成RS編碼乘法器因子的求取,，降低伽羅華域乘法運(yùn)算在FPGA實(shí)現(xiàn)過程中的復(fù)雜度，減少運(yùn)算量,。測(cè)試結(jié)果表明,，優(yōu)化后的RS編碼FPGA實(shí)現(xiàn)簡(jiǎn)單有效，且編碼準(zhǔn)確無誤,，編碼結(jié)果與MATLAB計(jì)算所得理論結(jié)果一致,，可適用于任意碼長的RS編碼，在移動(dòng)通信,、航天通信等復(fù)雜多因素通信領(lǐng)域有著廣泛的應(yīng)用價(jià)值,。
中圖分類號(hào)： TN911.22；TN914
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.190901
中文引用格式： 李錦明,，劉夢(mèng)欣,，成乃朋. RS編碼算法的優(yōu)化與FPGA實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2020,，46(2)：76-79,，83.
英文引用格式： Li Jinming，Liu Mengxin,，Cheng Naipeng. Optimization and FPGA implementation of RS coding algorithm[J]. Application of Electronic Technique,，2020，46(2)：76-79,，83.
Optimization and FPGA implementation of RS coding algorithm
Li Jinming，Liu Mengxin,，Cheng Naipeng
School of Instrument and Electronics,，North University of China，Taiyuan 030051,，China
Abstract： Aiming at the problems of large amount of computation and high complexity of multiplication of Galois Field(GF) in the common RS coding algorithm, the RS coding module is optimized and the multiplier factor is obtained. The module completes the calculation of the RS code multiplier factor, reduces the complexity of the Galois field multiplication operation in the FPGA implementation process, and reduces the amount of computation. The test results show that the optimized RS-coded FPGA is simple and effective, and the coding is accurate. The coding result is consistent with the theoretical results obtained by MATLAB. It can be applied to RS coding of arbitrary code length, and complex multi-factor communication in mobile communication and space communication.
Key words : RS coding,；Galois field；algorithm optimization,；FPGA

0 引言

    里得-所羅門碼(Reed-Solomon,，RS)是由REED I S和SOLOMON G在1960年提出的一種特殊的非二進(jìn)制BCH碼[1]，是所有(n,，k)線性分組碼中糾錯(cuò)能力最強(qiáng)的碼型,，可同時(shí)糾正隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤。隨著大規(guī)模集成電路技術(shù)的發(fā)展,，RS碼憑借其優(yōu)異的性能廣泛應(yīng)用于深空通信,、移動(dòng)通信、軍用通信、光纖通信,、磁盤陣列及光存儲(chǔ)等領(lǐng)域,，另外RS編碼也可應(yīng)用于保密通信中[2-8]。

1 RS編碼原理

    對(duì)于碼長為n=2m-1(n>2)的RS(n,，k)碼,，其碼元符號(hào)均取GF(2m)，其信息段具有k個(gè)符號(hào),，監(jiān)督段具有n-k個(gè)符號(hào),，可糾正t個(gè)突發(fā)錯(cuò)誤，其生成多項(xiàng)式為：

jsj2-gs1-2.gif

    RS(n,，k)編碼的碼多項(xiàng)式為：

    jsj2-gs3.gif

其中,，r(x)為RS(n，k)編碼的校驗(yàn)多項(xiàng)式,。

    在實(shí)際應(yīng)用中采用的RS碼均為系統(tǒng)碼,，c(x)可被g(x)整除，mod為求余運(yùn)算,，則：

jsj2-gs4-6.gif

2 RS編碼電路

    根據(jù)RS編碼原理可知,，RS碼的編碼電路主要根據(jù)生成多項(xiàng)式g(x)進(jìn)行設(shè)計(jì)，實(shí)際應(yīng)用中的常用RS編碼電路[10-14]如圖1所示,。

jsj2-t1.gif

    圖1中,， g2t-1，g2t-2,，…,，g1，g0為生成多項(xiàng)式g(x)的系數(shù)：

    jsj2-gs7.gif

    電路工作前將所有寄存器清零,，開關(guān)SW1接至mr處,，開關(guān)SW2接至m處，信息碼mk-1,，…,，m1，m0依次進(jìn)入編碼電路,，并同時(shí)由輸出端進(jìn)行輸出,。當(dāng)m(x)送入電路后，開關(guān)SW1接至0處,，開關(guān)SW2接至r處,，依次輸出寄存器R2t-1，…,，R1,，R0的值,，即校驗(yàn)子rn-k-1，…,，r1,，r0的值，從而完成RS(n,，k)編碼,。

3 基于FPGA的RS編碼優(yōu)化

jsj2-gs8-10.gif

jsj2-gs11.gif

其中，矩陣C為乘法器因子矩陣,。觀察RS編碼電路可知,，每個(gè)乘法器的系數(shù)gk為固定值，即RS編碼電路每個(gè)乘法器的乘法器因子為固定值,。因此,，可以在編碼前根據(jù)生成多項(xiàng)式g(x)的系數(shù)g2t-1，g2t-2,，…,，g1，g0的值生成乘法器因子矩陣C2t-1,，C2t-2,，…，C1,，C0用于后續(xù)的RS編碼,。例如，RS(255,，239)的生成多項(xiàng)式系數(shù)g15=118,，對(duì)應(yīng)的乘法器因子矩陣C15為：

    jsj2-gs12.gif

jsj2-gs13-14.gif

    由此證明通過乘法器因子矩陣可以把RS編碼中信息碼與生成多項(xiàng)式系數(shù)gk在伽羅華域上的乘法轉(zhuǎn)換轉(zhuǎn)為信息碼數(shù)據(jù)位之間的加法運(yùn)算。根據(jù)伽羅華域的加法運(yùn)算法則,，信息碼數(shù)據(jù)位之間的伽羅華域加法運(yùn)算在FPGA實(shí)現(xiàn)時(shí)可由異或操作(^)完成,，從而使得FPGA實(shí)現(xiàn)伽羅華域的乘法運(yùn)算簡(jiǎn)化，數(shù)據(jù)運(yùn)算量減少,。

jsj2-4-s1.gif

4 RS編碼優(yōu)化后的FPGA實(shí)現(xiàn)

4.1 乘法器因子求取模塊的FPGA實(shí)現(xiàn)

jsj2-4.1-x1.gif

jsj2-t2.gif

    在FPGA中實(shí)現(xiàn)GF(28)域中RS(255，239)乘法器因子求取的結(jié)果如圖3所示,。

jsj2-t3.gif

4.2 RS編碼的FPGA實(shí)現(xiàn)

    為了驗(yàn)證乘法器因子模塊的有效性,，采用所得的乘法器因子進(jìn)行RS編碼，將編碼結(jié)果與MATLAB計(jì)算的理論結(jié)果進(jìn)行對(duì)比驗(yàn)證[15],。

    RS編碼的RTL原理圖如圖4所示,，包括信息碼數(shù)據(jù)緩存模塊m_fifo、控制模塊control,、校驗(yàn)碼生成模塊R_top,、編碼數(shù)據(jù)輸出模塊c_fifo,。其中，校驗(yàn)碼生成模塊R_top中包含乘法器因子求取模塊,，由其完成乘法器因子的求取,。

jsj2-t4.gif

    采用乘法器因子模塊所得的乘法器因子實(shí)現(xiàn)的RS(255，239)編碼的測(cè)試結(jié)果如圖5所示,。當(dāng)輸入信息碼data_in為(1,，2，3,，…,，238，239)時(shí),，校驗(yàn)碼生成模塊R_top生成的16個(gè)校驗(yàn)子為(37,，133，225,，126,，37，59,，132,，133，56,，168,，179，4,，9,，99，79,，148),。圖6為MATLAB對(duì)(1，2,，…,，239)進(jìn)行RS(255，239)編碼輸出的計(jì)算結(jié)果,，將圖6的輸出結(jié)果與圖5的輸出碼字c進(jìn)行對(duì)比,，可以驗(yàn)證采用乘法器因子求取模塊實(shí)現(xiàn)的RS編碼無誤。

jsj2-t5.gif

jsj2-t6.gif

4.3 乘法器因子求取模塊的適應(yīng)性驗(yàn)證

    為了驗(yàn)證乘法器因子求取模塊的適應(yīng)性,，采用乘法器因子求取模塊完成RS(255,，223)的乘法器因子求取，輸入data_in為(0,，1,，2,，…，222),，RS(255,，223)編碼測(cè)試結(jié)果如圖7所示，編碼輸出的32個(gè)校驗(yàn)子為(102,，212,，116，164,，159,，61，229,，39,，17，244,，245,，67，253,，18,，156，217,，115,，73，31,，174,，27，140,，69,，159，104,，219,，254，187,，173,，169，10,，116)。將編碼輸出與圖8所示RS(255,，223)編碼計(jì)算結(jié)果進(jìn)行比對(duì),，可驗(yàn)證編碼無誤,，證明采用乘法器因子求取模塊優(yōu)化的基于FPGA的RS編碼可適應(yīng)不同的生成多項(xiàng)式，完成有效RS編碼,。

jsj2-t7.gif

jsj2-t8.gif

5 結(jié)論

    RS編碼是一類很好線性糾錯(cuò)碼,，在工程實(shí)踐中有著廣泛應(yīng)用。本文通過設(shè)計(jì)乘法器因子求取模塊,，將RS編碼中信息碼與乘法器系數(shù)在伽羅華域上乘法轉(zhuǎn)換轉(zhuǎn)為信息碼數(shù)據(jù)位之間的加法運(yùn)算,，降低FPGA實(shí)現(xiàn)時(shí)的運(yùn)算復(fù)雜度、減少運(yùn)算量,，且可根據(jù)不同的乘法器系數(shù)生成相應(yīng)的乘法器因子,，完成不同碼長和校驗(yàn)子的RS編碼，可廣泛應(yīng)用于短碼及中長碼通信領(lǐng)域,，具有很好的實(shí)際應(yīng)用價(jià)值,。

參考文獻(xiàn)

[1] REED I S，SOLOMON G.Polynomial codes over certain finite fields[J].Journal of the Society for Industrial and Applied Mathematics,，1960,，6(8)：300-304.

[2] 張春生，蘇開友.FPGA數(shù)字信號(hào)處理與工程應(yīng)用實(shí)踐[M].北京：中國鐵道出版社,，2013.

[3] 于劍.基于FPGA的衛(wèi)星通信信道編碼設(shè)計(jì)與工程實(shí)現(xiàn)[D].石家莊：河北科技大學(xué),，2015.

[4] 胡曉莉，王麗雪,，錢永杰,，等.基于H-PPM的可見光通信系統(tǒng)RS編碼性能分析[J].應(yīng)用光學(xué)，2017,，38(5)：751-757.

[5] 張翔.無線光通信中的編碼與調(diào)制技術(shù)研究及應(yīng)用[D].北京：北京郵電大學(xué),，2015.

[6] 楊家旺，曹陽,，彭小峰,，等.RS編碼與交織級(jí)聯(lián)在室內(nèi)VLC中的應(yīng)用研究[J].光通信技術(shù)，2016,，40(2)：37-39.

[7] 董光亮,，崔健雄，李海濤,，等.物理層網(wǎng)絡(luò)編碼在深空通信中的應(yīng)用展望[J].電子技術(shù)應(yīng)用,，2016，42(5)：21-23,，31.

[8] 單慧琳,，張銀勝.基于改進(jìn)DEA算法的聲波加密傳輸系統(tǒng)[J].電子技術(shù)應(yīng)用，2019,，45(4)：104-108.

[9] 周炯槃,，龐沁華.通信原理[M].北京：北京郵電大學(xué)出版社,，2008：382-383.

[10] 袁志東.基于Verilog語言的RS(255，247)編譯碼器設(shè)計(jì)[D].合肥：安徽大學(xué),，2015.

[11] 胡智寬.基于RS編譯碼的數(shù)字通信電路FPGA設(shè)計(jì)研究[D].北京：北京理工大學(xué),，2015.

[12] 楊曉玲，郭烜.基于FPGA的RS編碼的設(shè)計(jì)與實(shí)現(xiàn)[J].河南機(jī)電高等?？茖W(xué)校學(xué)報(bào),，2016，24(4)：11-14.

[13] 孫健,，張輝,，王宇飛，等.一種基于RS(24,，20)的編譯碼器設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī),，2016，33(12)：75-79.

[14] 俞旋.RS編碼算法及FPGA實(shí)現(xiàn)[J].科技咨詢導(dǎo)報(bào),，2007(28)：27-28.

[15] 翟勇,，唐凡.利用Matlab仿真RS編碼[J].有線電視技術(shù)，2010,，17(11)：41-44.




作者信息：

李錦明,，劉夢(mèng)欣，成乃朋

(中北大學(xué) 儀器與電子學(xué)院,，山西 太原030051)

此內(nèi)容為AET網(wǎng)站原創(chuàng),，未經(jīng)授權(quán)禁止轉(zhuǎn)載。