RS编码算法的优化与FPGA实现-AET-电子技术应用

RS编码算法的优化与FPGA实现

2020年电子技术应用第2期

李锦明，刘梦欣，成乃朋

中北大学仪器与电子学院，山西太原030051

摘要： 针对常用RS编码算法中伽罗华域(Galois Field，GF)的乘法运算在FPGA中实现时存在的数据运算量大、复杂度高等问题，对RS编码模块进行优化，通过增加乘法器因子求取模块，完成RS编码乘法器因子的求取，降低伽罗华域乘法运算在FPGA实现过程中的复杂度，减少运算量。测试结果表明，优化后的RS编码FPGA实现简单有效，且编码准确无误，编码结果与MATLAB计算所得理论结果一致，可适用于任意码长的RS编码，在移动通信、航天通信等复杂多因素通信领域有着广泛的应用价值。

关键词： RS编码伽罗华域算法优化 FPGA

中图分类号： TN911.22；TN914
文献标识码： A
DOI：10.16157/j.issn.0258-7998.190901
中文引用格式： 李锦明，刘梦欣，成乃朋. RS编码算法的优化与FPGA实现[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)线性分组码中纠错能力最强的码型，可同时纠正随机错误和突发错误。随着大规模集成电路技术的发展，RS码凭借其优异的性能广泛应用于深空通信、移动通信、军用通信、光纤通信、磁盘阵列及光存储等领域，另外RS编码也可应用于保密通信中^[2-8]。

1 RS编码原理

对于码长为n=2^m-1(n>2)的RS(n，k)码，其码元符号均取GF(2^m)，其信息段具有k个符号，监督段具有n-k个符号，可纠正t个突发错误，其生成多项式为：

RS(n，k)编码的码多项式为：

其中，r(x)为RS(n，k)编码的校验多项式。

在实际应用中采用的RS码均为系统码，c(x)可被g(x)整除，mod为求余运算，则：

2 RS编码电路

根据RS编码原理可知，RS码的编码电路主要根据生成多项式g(x)进行设计，实际应用中的常用RS编码电路^[10-14]如图1所示。

图1中， g_2t-1，g_2t-2，…，g₁，g₀为生成多项式g(x)的系数：

电路工作前将所有寄存器清零，开关SW₁接至mr处，开关SW₂接至m处，信息码m_k-1，…，m₁，m₀依次进入编码电路，并同时由输出端进行输出。当m(x)送入电路后，开关SW₁接至0处，开关SW₂接至r处，依次输出寄存器R_2t-1，…，R₁，R₀的值，即校验子r_n-k-1，…，r₁，r₀的值，从而完成RS(n，k)编码。

3 基于FPGA的RS编码优化

其中，矩阵C为乘法器因子矩阵。观察RS编码电路可知，每个乘法器的系数g_k为固定值，即RS编码电路每个乘法器的乘法器因子为固定值。因此，可以在编码前根据生成多项式g(x)的系数g_2t-1，g_2t-2，…，g₁，g₀的值生成乘法器因子矩阵C^2t-1，C^2t-2，…，C¹，C⁰用于后续的RS编码。例如，RS(255，239)的生成多项式系数g₁₅=118，对应的乘法器因子矩阵C¹⁵为：

由此证明通过乘法器因子矩阵可以把RS编码中信息码与生成多项式系数g_k在伽罗华域上的乘法转换转为信息码数据位之间的加法运算。根据伽罗华域的加法运算法则，信息码数据位之间的伽罗华域加法运算在FPGA实现时可由异或操作(^)完成，从而使得FPGA实现伽罗华域的乘法运算简化，数据运算量减少。

4 RS编码优化后的FPGA实现

4.1 乘法器因子求取模块的FPGA实现

jsj2-4.1-x1.gif

在FPGA中实现GF(2⁸)域中RS(255，239)乘法器因子求取的结果如图3所示。

4.2 RS编码的FPGA实现

为了验证乘法器因子模块的有效性，采用所得的乘法器因子进行RS编码，将编码结果与MATLAB计算的理论结果进行对比验证^[15]。

RS编码的RTL原理图如图4所示，包括信息码数据缓存模块m_fifo、控制模块control、校验码生成模块R_top、编码数据输出模块c_fifo。其中，校验码生成模块R_top中包含乘法器因子求取模块，由其完成乘法器因子的求取。

采用乘法器因子模块所得的乘法器因子实现的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进行对比，可以验证采用乘法器因子求取模块实现的RS编码无误。

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)编码计算结果进行比对，可验证编码无误，证明采用乘法器因子求取模块优化的基于FPGA的RS编码可适应不同的生成多项式，完成有效RS编码。

5 结论

RS编码是一类很好线性纠错码，在工程实践中有着广泛应用。本文通过设计乘法器因子求取模块，将RS编码中信息码与乘法器系数在伽罗华域上乘法转换转为信息码数据位之间的加法运算，降低FPGA实现时的运算复杂度、减少运算量，且可根据不同的乘法器系数生成相应的乘法器因子，完成不同码长和校验子的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数字信号处理与工程应用实践[M].北京：中国铁道出版社，2013.

[3] 于剑.基于FPGA的卫星通信信道编码设计与工程实现[D].石家庄：河北科技大学，2015.

[4] 胡晓莉，王丽雪，钱永杰，等.基于H-PPM的可见光通信系统RS编码性能分析[J].应用光学，2017，38(5)：751-757.

[5] 张翔.无线光通信中的编码与调制技术研究及应用[D].北京：北京邮电大学，2015.

[6] 杨家旺，曹阳，彭小峰，等.RS编码与交织级联在室内VLC中的应用研究[J].光通信技术，2016，40(2)：37-39.

[7] 董光亮，崔健雄，李海涛，等.物理层网络编码在深空通信中的应用展望[J].电子技术应用，2016，42(5)：21-23，31.

[8] 单慧琳，张银胜.基于改进DEA算法的声波加密传输系统[J].电子技术应用，2019，45(4)：104-108.

[9] 周炯槃，庞沁华.通信原理[M].北京：北京邮电大学出版社，2008：382-383.

[10] 袁志东.基于Verilog语言的RS(255，247)编译码器设计[D].合肥：安徽大学，2015.

[11] 胡智宽.基于RS编译码的数字通信电路FPGA设计研究[D].北京：北京理工大学，2015.

[12] 杨晓玲，郭烜.基于FPGA的RS编码的设计与实现[J].河南机电高等专科学校学报，2016，24(4)：11-14.

[13] 孙健，张辉，王宇飞，等.一种基于RS(24，20)的编译码器设计[J].微电子学与计算机，2016，33(12)：75-79.