《電子技術應用》
您所在的位置：首頁 > 可編程邏輯 > 設計應用 > RS編碼算法的優(yōu)化與FPGA實現(xiàn)
RS編碼算法的優(yōu)化與FPGA實現(xiàn)
2020年電子技術應用第2期
李錦明，劉夢欣，成乃朋
中北大學 儀器與電子學院，山西 太原030051
摘要： 針對常用RS編碼算法中伽羅華域(Galois Field，GF)的乘法運算在FPGA中實現(xiàn)時存在的數(shù)據運算量大、復雜度高等問題，對RS編碼模塊進行優(yōu)化，通過增加乘法器因子求取模塊，完成RS編碼乘法器因子的求取，降低伽羅華域乘法運算在FPGA實現(xiàn)過程中的復雜度，減少運算量。測試結果表明，優(yōu)化后的RS編碼FPGA實現(xiàn)簡單有效，且編碼準確無誤，編碼結果與MATLAB計算所得理論結果一致，可適用于任意碼長的RS編碼，在移動通信、航天通信等復雜多因素通信領域有著廣泛的應用價值。
中圖分類號： TN911.22；TN914
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.190901
中文引用格式： 李錦明，劉夢欣，成乃朋. RS編碼算法的優(yōu)化與FPGA實現(xiàn)[J].電子技術應用，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年提出的一種特殊的非二進制BCH碼[1]，是所有(n，k)線性分組碼中糾錯能力最強的碼型，可同時糾正隨機錯誤和突發(fā)錯誤。隨著大規(guī)模集成電路技術的發(fā)展，RS碼憑借其優(yōu)異的性能廣泛應用于深空通信、移動通信、軍用通信、光纖通信、磁盤陣列及光存儲等領域，另外RS編碼也可應用于保密通信中[2-8]。

1 RS編碼原理

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

jsj2-gs1-2.gif

    RS(n，k)編碼的碼多項式為：

    jsj2-gs3.gif

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

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

jsj2-gs4-6.gif

2 RS編碼電路

    根據RS編碼原理可知，RS碼的編碼電路主要根據生成多項式g(x)進行設計，實際應用中的常用RS編碼電路[10-14]如圖1所示。

jsj2-t1.gif

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

    jsj2-gs7.gif

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

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

jsj2-gs8-10.gif

jsj2-gs11.gif

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

    jsj2-gs12.gif

jsj2-gs13-14.gif

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

jsj2-4-s1.gif

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

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

jsj2-4.1-x1.gif

jsj2-t2.gif

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

jsj2-t3.gif

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

    為了驗證乘法器因子模塊的有效性，采用所得的乘法器因子進行RS編碼，將編碼結果與MATLAB計算的理論結果進行對比驗證[15]。

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

jsj2-t4.gif

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

jsj2-t5.gif

jsj2-t6.gif

4.3 乘法器因子求取模塊的適應性驗證

    為了驗證乘法器因子求取模塊的適應性，采用乘法器因子求取模塊完成RS(255，223)的乘法器因子求取，輸入data_in為(0，1，2，…，222)，RS(255，223)編碼測試結果如圖7所示，編碼輸出的32個校驗子為(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)編碼計算結果進行比對，可驗證編碼無誤，證明采用乘法器因子求取模塊優(yōu)化的基于FPGA的RS編碼可適應不同的生成多項式，完成有效RS編碼。

jsj2-t7.gif

jsj2-t8.gif

5 結論

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

參考文獻

[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ù)字信號處理與工程應用實踐[M].北京：中國鐵道出版社，2013.

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

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

[5] 張翔.無線光通信中的編碼與調制技術研究及應用[D].北京：北京郵電大學，2015.

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

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

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

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

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

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

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

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

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

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




作者信息：

李錦明，劉夢欣，成乃朋

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

此內容為AET網站原創(chuàng)，未經授權禁止轉載。