RS编译码的一种硬件解决方案

摘  要: 提出了基于欧氏算法和频谱分析相结合的RS码硬件编译码方法;利用FPGA芯片实现了GF(28)上最高速率为50Mbps、最大延时为640ns的流式译码方案,满足了高速率的RS编译码需求。

关键词: RS码  FPGA  伴随式  关键方程  IDFT

　　差错控制编码技术对改善误码率、提高通信的可靠性具有重要作用。RS码既可以纠正随机错误,又可以纠正突发错误,具有很强的纠错能力,在通信系统中应用广泛。由于RS码的译码复杂度高,数学运算量大,常见的硬件及软件译码方案大多不能满足高速率的传输需求,一般适用于10Mbps以下。本文提出的欧氏算法和频谱结构分析相结合的RS硬件解码方案,适用于FPGA单片实现,速率高、延迟小、通用性强、使用灵活。笔者在FPGA芯片上实现了GF(28)上符号速率为50Mbps的流式解码方案，最大延时为640ns,参数可以根据需要灵活设置。

　　1 RS码的结构

　　码字长度为N=q-1(q=2i),生成多项式为g(x)=(x-αm0)(x-αm0)…(x-αm0+1),的RS码有最小码距δ=2t+1,能够纠正t个随机或突发错误[1]。本文列举的方案测试中采用的RS码主要参数为N=255、m0=0、t=8,其中GF(28)的生成多项式为g(x)=x8+x4+x3+x2+1。由于RS码的编码逻辑结构比较简单,文中仅给出仿真结果。

　　2 RS码的译码算法

　　RS译码算法一般分为三步:伴随式计算、关键方程获得和错误图样的求解。其中关键方程的获得是RS译码中最困难、最为关键的一步。

　　在利用伴随式求解关键方程时,BM算法和Euclidean(欧氏)算法是两种较好的选择。BM算法涉及大量的变量存储和复杂的逻辑控制,适用于软件编程而不适合硬件实现。欧氏算法数据存储量少、控制便捷,适合硬件实现。且采用欧氏算法确定关键方程所需时间与错误个数成正比,因此从处理时间上考虑,欧氏算法也是较好的选择。

　　在获得关键方程后,采用时域处理方法,需要大量的运算单元和控制电路,在硬件实现中是不可取的。而采用频谱结构分析方法,利用最短线性移位寄存器综合及离散傅氏逆变换进行处理,逻辑简单、耗时少,适合硬件实现。虽然在傅氏变换时需要较多的逻辑单元,但对GF(2n)在n<10的情况下,变换域译码器要比时域译码器简单得多。因而本文提出了欧氏算法和频谱结构分析相结合的方案,并在实践中获得了较好的效果。

　　Euclidean算法[3]步骤如下:

　　3 方案流程

　　方案流程框图如图1所示。

　　3.1 伴随式S0，S1，…,S2t-1的计算

　　令r1，r2，…,rn为接收到的RS码字,根据系统码监督矩阵的特性,可构造如图2所示伴随式计算电路Si=(((r1αi+r2)αi+r3)αi…)αi+rn，从而实现伴随式序列的计算。

　　3.2 利用伴随式确定关键方程

　　Euclidean算法的难点主要在于迭代计算过程中存在的被除数多项式和除数多项式长度的不确定性,使每次计算中产生的商序列的长度不等,以及因此可能涉及到的不定长多项式的相乘和相加问题,增加了硬件设计的难度。系统采用了嵌套双循环的方法,利用‘时钟产生2’控制外循环,‘时钟产生1’控制内循环,从而优化了算法,得到了问题的解决方案。在获得伴随式的基础上,图3电路可具体完成Euclidean算法对关键方程的求解σ(x)=σtxt+σt-1xt-1+…+σ1x+1。

　　3.3 利用最短线性移位寄存器综合和离散傅氏变换

　　获取错误图样

　　在得到关键方程后,首先应进行错误位置(关键方程的根)的确定,这样可减小电路的规模;利用钱搜索[1](工程上求解σ(x)根的实用方法)的方法可以简捷地确定错误位置。然后,启动最短线性移位寄存器综合和离散傅氏逆变换,经过N次(运算所在域的长度)迭代,即可求得对应各个错误位置的错误图样，如图4所示。用错误图样对接收码字进行纠错,就可得到正确的信息序列。

　　3.4 RS编译码在FPGA上的实现

　　有限域的乘法、加法运算单元和各模块的控制逻辑设计是系统成功的关键。涉及有限域的各个运算单元的运算速度制约了译码器的速度,而控制逻辑引导了译码的流程。硬件电路的软件开发工具给设计复杂电路提供了简捷思路。系统采用了QUARTUS与第三方软件相结合的方法,用VHDL语言设计了大部分功能模块。特别是在乘法器设计中,乘数确定、被乘数不定的乘法器以及乘数、被乘数均不定的有限域乘法器,经逻辑综合和优化设计后,运算速度可分别在6.8ns和11.6ns内完成,完全可以满足系统符号速率50Mbps的要求。应该指出,系统速度的进一步提高受到求逆运算的限制,求逆运算没有明确的数学结构(通常采用查表的方法),这是制约运算速度的瓶颈。但针对流式译码算法,上述结构已能满足要求。

　　4 仿真结果

　　4.1 编码器的仿真

　　仿真的时钟频率为50MHz,在EN为高电平时输入信息有效。为简单起见,采用系统码的缩短型,即信息为(00，00，…,00,02,01,02)。编码器的仿真结果如图5所示。其中,IN为输入信息,CLK为系统时钟,C为编码输出(输入和输出均为16进制)。

　　4.2 译码器的仿真

　　首先,给出系统的仿真全貌,如图6所示。其中C为接收到的RS码,SP为伴随式S15,shang为运用欧氏算法得到的商序列,SeryDA为S序列,anssd和ERTD分别对应码字可能存在的第四个错误位置和错误值,仿真中的接收码字在位置(105,106,107,108,109,110,111,112)上错误均为(01)HEX。

　　伴随式的计算结果：S15,S14,…,S1,S0为(FD,8D,CE,4A,51,B2,A1,CA,C4,0D,73,56,A6,F5,01),图6和图7中的sp即为S15。

　　这里重点给出利用伴随式计算关键方程的电路仿真结果,如图7所示。当输入伴随式结果以后,运算电路启动,在计算商序列的同时进行联接多项式的迭代运算。欧氏算法的商序列shang为:(FF，58),(37，92),(50，45),(E9，C7),(F4，B9),(5D，33),(87,8F)。当满足终止条件以后显示标志QQC,同时,给出关键方程系数如图7中(AI，AH，AG，AF，AE，AD，AC，AB，AA)即(00，19，2E，EC，A8，AD，41，E6，95)，对应有限域上的表达式为：

　　δ(x)=α193x7+α130x6+α122x5+α144x4+α252x3+α191x2+α160x+α184；

　　有解为(α105，α106，α107，α108，α109，α110，α111)，与假定错误位置完全一致。然后求解S序列,同时针对各错误位置进行IDFT,就可以得到对应的错误值。图6中anssd和ERTD表示位置108上存在的错误为(01)HEX。

　　系统仿真表明,译码器获得的错误位置和错误图案与实际假设的错误位置(105,106,107,108,109,110,111)和错误值(01)HEX完全一致。

　　基于APEX架构的可编程单芯片RS编译码硬件解决方案在中国普天集团西安蓝牙通讯设备有限公司的二次群无线扩频通信机的改造项目中得到了应用。它可用于离散译码、流式译码,在添加一级缓存的基础上,同样适用于连续译码。

　　参考文献

　　1 王新梅，肖国镇.纠错码-原理与方法.西安：西安电子科技大学出版社, 2001

　　2 I.S.Reed. A Comparison of VLSI Architecture for Time and Transform Domain Decoding of Reed-Solomon Codes.

　　University of Southern California， 1990

　　3 I.S.Reed. A Single Chip VLSI Reed-Solomon Decoder.University of Southern California， 1990

　　4 I.S.Reed.A VLSI Single Chip (255，233) Reed-Solomon Encoder. University of Southern California, 1990

　　5 赵雅兴.FPGA原理、设计与应用.天津：天津大学出版社,1999

　　6 侯伯亨，顾新.VHDL硬件描述语言与数字逻辑电路设计.西安：西安电子科技大学出版社,2001