基于BM算法的RS(18,10)译码的软件实现和性能分析

王景煜， 景晓军

（北京邮电大学 信息与通信工程学院，北京 100876）

0 引言

RS(Reed-Solomon)码是一类具有优良性能的极大距离纠错码，RS码广泛地应用在卫星通信领域和地面无线移动通信领域。本文设计了RS(18,10)，RS(18,10)是RS(255,247)的缩短码，和RS(255,247)相比纠错能力更强。本文在对译码原理研究基础上,提出了一种RS(18,10)译码器的matlab解决方案。RS译码仿真程序为以后的算法验证和硬件设计调试中起着至关重要的作用。

1 译码原理

RS译码方法很多，根据关键方程的不同，可分为：BM迭代算法和Euclid迭代算法。还有人提出软入软出[1]的迭代译码算法。本文主要研究BM迭代算法硬判译码。

RS(18,10)是 RS(255,247)的缩短码，所在的有限域是GF(2^8)。每个码字有8个信息位，进行一次编码需要10个码字，生成8个码子的冗余信息。这18个码字中任意四个码字发生错误均可以纠错[2]。该码的本原多项式为：

该码的生成多项式为：

1.1 伴随式的计算

设R(x)是接收多项式，因为是RS(18,10)，所以一次编码完成会产生18个码字，可以表示为：

译码算法首先计算伴随多项式iS，i=1,2,3…8，如果伴随多项式的值为 0，则证明传输没有发生错误，如果有任何一位不为0，则在传输中发生错误了。

伴随多项式为：

式（2）可以写为 ：

这样根据式（3）就可以用硬件设计电路设计 8条同时处理的电路，这样在18个处理时钟就可以计算出8个伴随值了。相应的在进行matlab设计rs_bansui.m模块的时候，只要在m函数里做一个18次的循环就可以计算出伴随式。

1.2 求解错位位置多项式

错误位置多项式可以表示为：

求解关键方程是RS码解码器设计实现中最复杂的一个模块（rs_bm.m）。在此用BM算法迭代求解。迭代算法就是首先选择一组或者两组合理的初始值0()xσ，然后进行第一次迭代运算求解出1()xσ，简言之用0()xσ表示1()xσ。这样一直迭代下去，最终迭代出的各个系数。

迭代过程步骤：

① 初始化合理值，令：② 计算jd，如果jd为0，则：

如果jd不为0，则找出j之前某一行i，i行在j行之前的i-D(i)最大，且，然后按照:计算出()x；

③ 计算1jd+，然后重复步骤②，迭代进行8次，即可求解出错误位置多项式的系数。

1.3 钱搜索法求解错误位置

1.4 计算错误值

译码算法的最后一个步骤就是计算错误值，在1.3中我们已经求出在 R(x)的那些位置发生了错误，现在我们只需求出对应位置上的错误值就可以了。还是假设发生了v个错误，根据式子：

可以求出第j个错误值。其中的:

求出错误值jw之后，然后根据1.3步骤中记录的第j个错误的位置和相应位置的接收值进行有限域的加法就可以恢复出正确值。

2 译码基本模块的matlab实现和及其性能分析

RS码的运算全部都是在有限域内进行的，所以进行有限域的基本运算的设计是非常要的[3]。只要这些基本模块编写完成之后，按照上述的步骤即可进行译码软件代码的编写。

2.1 有限域加法器

rs_add.m模块：y=rs_add(a,b)入口参数a,b均为模255的十进制数，进入函数后先进行十进制到二进制的转换，然后按比特异或，将结果进行二进制到十进制的转换并赋值给y。

2.2 有限域乘法器

rs_multi.m模块：y=rs_multi(a,b) 口参数a,b均为模255的十进制数，进入函数后先进行十进制到二进制的转换，然后按比特进行GF(2^8)域RS(18,10)的简化的运算。这样硬件处理在一个运算周期就可以完成乘法。

2.3 求逆器

rs_invers.m模块：求逆运算比较复杂，为了加速译码速度，考虑到该有限域的元素数目总数不多，采用查找表法。在硬件实现时做一个rom的查找表即可。

2.4 性能仿真

图1是对RS(18,10)码在AWGN信道下的性能仿真，调制方式为bpsk，发送端和接收端对数据采用8倍过采样根升余弦滚降滤波进行成形滤波，假设接收端理想同步。‘*’为没有加RS码的性能曲线图，‘o’为加了RS码的性能曲线。横轴为Eb/N0（单位为dB）,纵轴为误比特率。

图1 性能曲线

3 结语

本文对RS(18,10)的译码算法进行了分析，并给出了进行 matlab软件实现的方法，其中算法考虑到硬件算法的设计，设计了很多基本运算的m函数和算法各个模块的m函数，这些都给算法验证和硬件设计提供了参考和指导。并且对该RS码进行了在AWGN信道下的性能仿真，可以看出，在Eb/N0比较小的时候RS码的作用不是很显著，但是随着Eb/N0的提高，RS（18,10）可以显著的提高误比特率，在误比特率为10-3的时候有3 dB的增益。

[1] 李国静,邹永忠,李道本.一种适用于RS的低复杂度软入软出译码方法[C]//第十二届全国青年通信学术会议.北京:北方工业大学,2007.

[2] [美] Schwarts M. Mobile Wireless Communications[M].许希斌,李云洲译.北京:电子工业出版社,2006:120-130.

[3] [美] Proakis J P, Salehi M, Bauch G. Contemporary Communication Systems Using MATLAB and Simulink[M].刘树棠译.第2版.北京:电子工业出版社,2005:285-296.