宋洋军， 权进国， 林孝康

（清华大学 深圳研究生院现代通信实验室，广东 深圳 518055）

0 引言

DMR[1]的全称是 Digital Mobile Radio（数字移动无线电），是2006年欧洲电信标准协会（ETSI）颁布的数字对讲机标准。它采用FDMA接入，每个射频载波带宽为12.5 kHz；对每个载波而言，又采用TDMA分成两个时隙。

它比模拟对讲机具有更窄的频带宽度、频谱效率更高、邻带干扰更小、功耗更低和支持数据业务等优点，是对讲机未来发展的方向。

DMR标准的数据和控制帧采用了多种信道编码，Reed-Solomon(RS)码是其中的一种。具体采用的是 RS(12,9,4)。本文根据RS(12,9,4)码的特性，设计了一种新的译码方式，减少了ROM查找表的使用，降低了译码的复杂度，并在Xilinx FPGA上得到了验证。

1 RS码的表示和运算

RS码[2]通常表示为RS（n, k, δ），其中n, k, δ分别表示码长、信息码位和最小码重。RS码采用称为伽罗华域（Galois Field, GF）的有限域中的数据来表示。对于任何质数q，存在一个有限域，表示为GF(q)，其中包含有q个元素，可以将GF(q)延伸为一个含有qm个元素的域，这称为GF(q)的扩展域，表示为GF(qm)，m是一个正整数。GF(q)是GF(qm)的子集。RS码一般采用GF(2m)，这种情况下的1码元相当于m比特。对于m阶本原多项式p(x)，假设α是p(x)=0的根，那么α也会满足式（1）:

GF(2m)中任何非 0元素都可以用 α的幂次表示，所以GF(2m)中的元素构成一个有限元素的集合F，表示为式（2），其中α0=1：

GF(2m)的每个元素除了用α的幂表示外，还可以表示为F的线性组合，为了表示方便，用x代替α：

两个元素的和仍然在有限域F中。两个元素的积定义为对应的幂次方之和，幂次方之和可能大于2m-2，可以表示为式（5）,两个元素的积仍然在有限域F中：

2 RS码编码算法

RS 码一般为外码且是较长的码组，如RS(255,239)[3]，RS(255,223)[4]，也有采用缩短码的应用，例如使用在跳频通信系统中的前向纠错码 RS(31,25)[5]，和蜂窝数字分组数据（CDPD）系统中的RS(63,47)[6]。DMR标准采用的RS(12,9,4)是用于内码，它是将RS(255,252,4)前 243个码元设为 0，截取后 12个码元得到的。它是在GF(28)域中的，每个码元包含8比特。它有3个校验码元，因此能纠正1个错误码元，或者发现2个错误码元。它的生成多项式有两种表示方法[1]：

其中式（7）中的数字为16进制。两个生成多项式是等效的，是数据的不同表示方法，这里即有α6=40H。在GF(28)域中，本原多项式为：

根据生成多项式（7），编码器电路可以用图1表示。在开始编码的前9个周期，switch1闭合，switch2连接至B，输出序列c和输入序列i相同；第10至12个周期，switch1断开，switch2连接至A，输出保存在P中的监督码元。有限域加法器和有限域乘法器是设计的关键。有限域加法器直接由位异或运算实现，有限域乘法器可以通过构造有限域乘法器单元、查表、多项式系数模2和实现。有限域乘法器结构清晰，通用性强，但比多项式系数模2和延时要大；查表法需要一片ROM存储幂次与多项式系数的映射关系；多项式系数模2和只需最多2级异或运算即可实现，但要求一个乘数为常数。以图1为例，乘以16进制数40相当于乘以α6，设输入可表示为式（9），输出为式（10）：

根据本原多项式（8）化简幂次大于等于 8的项，设化简后有式（11）：

那么有：

类似地，其他两个乘法器也可以转化为多项式系数模2和。特别地，译码时需要的乘α-1也是可以这样计算的。

图1 RS(12,9,4)编码器结构

3 RS码译码算法

RS(12,9,4) 码译码主要分三部分：伴随式计算、逐码元计算新的伴随式和错误值、译码输出。如图2所示。

图2 RS(12,9,4)译码器结构

其中i=1,2,3。计算S需要的有限域乘法器可以采用和编码器相同的方法实现。如图3所示。

图3 RS(12,9,4)译码器伴随式的计算

需要12个周期把S计算出来。构造一个新的矩阵N：

根据文献[7]，可知当错误码元数为1或0时，N为奇异矩阵；当错误码元数为2时，N为非奇异矩阵。由于判定N是否奇异仍然需要有限域乘法器，并且判定后，计算错误位置和错误值也要有限域乘法器，用 Step-by-Step算法则可采用和编码器相同的方法实现有限域乘法器。假设接收码元中有1个错误：

j表示错误位置。译码的任务就是求出错误位置 j和错误值ej。由于伴随式S为：

那么，经过j次乘法运算，有：

该部分的乘法运算采用和编码器相同的有限域乘法器。若有2个码元错误，N为非奇异矩阵，上述等式不成立。若有0个错误，把ej=0当成1个错误处理。由此译码算法可以表示如下：

② 初始化错误值e′、错误位置j′和新的伴随式S′；

③ 如果j′ =12，说明码元错误个数大于2，译码结束；如果 S′1=S′3，跳至下一步，否则：

④ 译码码字：

4 RS码硬件实现

根据第2部分的编码算法和第3部分的译码算法，设计Verilog HDL寄存器传输级（RTL）的实现。使用Xilinx ISE 9.2i综合代码，FPGA选择Xilinx Virtex-II Pro XC2VP30型号，综合的结果是：编码器为797 gates，译码器是2 800 gates，总计3597 gates。将综合结果下载到Xilinx Virtex-II Pro XC2VP30 FF896的FPGA内，再使用ChipScope Pro 9.2i内嵌逻辑分析仪获得关键引脚的波形，如图 4，为了方便比较，这里使用了Visio对原图进行重绘。

i,c,r,i_dec分别表示发送的信息码(9 symbols)、编码后的码组(12 symbols)、接收的码组(12 symbols)和译码后的信息码(9 symbols)。 经编码后在发送信息码后增加了3个校验码元。r是对c添加1码元错误后得到的接收码组。通过图4可以得知，当第5个码元从35加噪声变成D0后，在state=4的末尾，译码输出i_dec得到了正确的结果35。

图4 RS(12,9,4)码FPGA的实现

5 结语

本文提出了一种适合缩短码RS(12,9)的译码算法，该算法通过计算伴随式并按照 Step-by-Step算法逐码元检查错误值和错误位置，简化了有限域内的负幂次方的运算，从而无需用于有限域负幂次方运算的查找表等，在译码性能和译码复杂度之间达到很好的折中。该算法经Verilog HDL硬件描述语言表示，下载到Xilinx FPGA内，使用线性反馈移位寄存器构成的随机数错误来模拟噪声，并用ChipScope工具获得内部信号波形得到验证。该算法已经应用在DMR标准的RS编译码器的FPGA实现上了。类似的算法也可以用于其他RS缩短码。

[1] ETSI. TS 102361-1, 2006，Electromagnetic compatibility and Radio spectrum Matters (ERM);Digital Mobile Radio (DMR)Systems; Part 1: DMR Air Interface (AI) protocol[S]. Sophia Antipolis Cedex, France: ETSI:130-132. http://www.etsi.org.

[2] Sklar B. Digitsal Communications-2nd ed[M]. New Jersey:Prentice Hall PTR, 2001:445-450.

[3] 胡庆生,王志功,张军,等. 2.5Gb/s Reed-Solomon译码器的VLSI优化实现[J].电路与系统学报,2005,10(02):57-65.

[4] 戴小红,潘志文.Reed-Solomon编译码器的设计与FPGA实现[J].现代电子技术,2006(03):119-124.

[5] 张珣,罗汉文,宋文涛.跳频通信系统中的纠错码设计与实现[J].通信技术,2001(02):11-13.

[6] 董威，蒋铃鸽，戎蒙恬.CDPD系统中RS译码器的改进设计与实现[J].通信技术,2002(11):10-12.

[7] Massey J L. Step-by-Step Decoding of the Bose-Chaudhuri-Hocquenghem Codes[J].IEEE Trans. Inform. Theory,1965(11):580-585.