截短Reed_Solomon码译码器的FPGA实现

截短Reed_Solomon码译码器的FPGA实现RS码(Reed-Solomon)是一种有很强纠错能力和很高编码效率的多进制BCH码，特别是纠正突发错误的能力很强，并且其码字构造简单，有严格的代数结构，便于用硬件实现，目前已广泛应用于通信领域中。RS码译码算法中对关键方程的求解是最重要和耗时最多的部分，采用传统BM算法[1，2]来求解，其结构较为复杂，不利于用硬件实现。对此，本文提出了一种改进的BM算法，该算法便于用循环方式实现，能有效简化RS译码器的结构，并在此基础上提出了一种大量采用并行结构的截短RS码译码器的硬件电路实现方式，相比软件译码方式，其速度优势十分明显，适合应用于嵌入式系统中。1RS码的解码算法流程及实现结构RS码是一种基于有限域（如GF，Galoisfield，伽罗华域）的纠错码，其码字由两部分组成：数据码字和纠错码字。其中数据码字包含了有用的信息；纠错码字则是附加在数据码字之后，相当于附加的信息，用于对数据码字可能出现的错误的检测和纠正，码流所包含的总码字数就是数据码字与纠错码字个数之和。RS解码算法包括四个步骤：(1)根据接收码字计算伴随式；(2)求解关键方程[1]；(3)用钱搜索[1]方法寻找错误位置，用Forney方法[1]计算错误值；(4)将错误位置的接收码字与错误值相加，得到纠错后的码字。其总体流程如图1所示。需要说明的是，解码过程中的计算都是基于有限域的，其基本计算单元是有限域的乘法器和加法器[3，4]。1.1伴随式的计算及电路结构实现计算伴随式是译码算法的第一步，需要计算的伴随式个数是码流的可纠错码字数t的2倍。设发送多项式为C(x)，码流在传输过程中产生的错误多项式为E(x)，则接收多项式可表示为：R(x)=C(x)+E(x)=n-1i=0ΣYixi(1)为了确定E(x)，需要得到错误位置xi及错误值Yi。设具有(n，m，t)形式的RS码所在伽罗华域的本原元为α，其2t个伴随式（S1，S2，…，S2t）是通过把αi(i∈2t)代入截短Reed-Solomon码译码器的FPGA实现张玲，张立，何伟(重庆大学通信工程学院，重庆400030)摘要：提出了一种改进的BM算法，并在此基础上提出了一种大量采用并行结构的截短RS码译码器的实现方式。验证表明，该算法能显著提高基于FPGA的RS译码器的速度并简化其电路结构。关键词：RS译码器；关键方程；BM算法；FPGA；并行结构中图分类号：TN919文献标志码：AAnimplementationforshortenedReed-SolomondecoderonFPGAZHANGLing，ZHANGLi，HEWei(DepartmentofCommunicationEngineering，ChongqingUniversity，Chongqing400030，China)Abstract：ThispaperdiscussesanalgorithmforRSdecoder,especiallyanimprovedBM(berlekamp-massey)methodfortheKE(keyequation)solutionisintroduced,whichcansimplifythedecodingprocesstoagreatextent.Basedonthisalgorithm,thepaperpresentsanarchitectureforitsimplementationonFPGA,inwhichparallelstructuresarelargelyusedinordertoachievethespeedashighaspossible.Keywords：RSdecoder；keyequation；BMmethod；FPGA；parallelstructure65《电子技术应用》2021年第7期《电子技术应用》2021年第7期欢迎网上投稿图3改进BM算法的计算框图子时钟产生模块pclk0pclk1pclk2pclk3pclk4△r△rpclk2△r求逆模块xB(x)δ△r计算模块中间变量dd(x)计算模块∧(x)s(x)sys_clkpclk0dd(x)dd(x)pclk1pclk3B(x)B(x)前次迭代值xB(x)存储及L、δ判别模块B(x)中间变量B(x)计算模块pclk4δxB(x)pclk4xB(x)△r错误位置多项式计算模块∧(x)∧(x)01sys_clk∧(x)△r-1图2伴随式计算电路的结构01DSiαirn-1，rn-2，…r0到接收多项式R(x)中计算而得到。在实现时，伴随式S的计算可以用如下公式实现[5]：si=R(αi)n-1j=0ΣRjαij=(…((Rn-1αi+Rn-2)αi+Rn-3)αi+…+R1)αi+R0(2)由式(2)可以看出，该计算式的结构非常规则，其基本单元是Rn-kαi+Rn-k-1，其中Rn-k就是RS码流中的第n-k个码字，以计算第i个伴随式si为例，这种循环迭代的实现结构如图2所示。为了提高速度，本设计采用了8个并行的计算模块，分别计算所需要的8个伴随式，每次计算均在1个时钟周期内完成。这样，经过26个时钟周期后，8个伴随式的值即可并行输出，传递给关键方程求解模块。1.2改进BM算法对关键方程的求解及电路实现结构关键方程是以2t个伴随式为系数构成的一个齐次线性方程组：St+1StSt-1…S1St+2St+1St…S2St+3St+2St+1…S3……………S2tS2t-1S2t-2…S……………………………………………………………………………………t1σ1σ2…σ……………………………………………………………………………………t=000………………………………………………………………………………………(3)记：Σ＝[1σ1σ1…σt]T(4)则对关键方程的求解，就是设法求得由错误位置多项式σ(x)的各项系数构成的向量Σ。笔者提出的改进BM算法相比传统的BM算法而言，其优点是便于采用循环迭代结构实现，硬件实现复杂度减小，而计算效率却得以提高。改进BM算法的流程可以表示为：初始化：∧(0)(x)＝1，B(0)(x)＝1，L0＝0下面的迭代流程用于计算σ(x)：△r=r-1j=0Σ∧j(r-1)Sr-j(5)δr=1，if(△r≠0and2Lr≤r-1)0，other≤s(6)Lr=δr×(r-Lr-1)+(1-δr)×Lr-1(7)∧(r)(x)B(r)(x××)=1△r×xδr×△r-1(1-δr)×××x×∧(r-1)(x)B(r-1)(x××)(8)r=1，2，…2t，经过2t次迭代，可以得到：∧(x)=∧(2t)(x)=1+∧1x+∧2x+…+∧txt(9)其中，∧(x)即为前文所述的错误位置多项式σ(x)，△r、B(x)以及L均为中间变量，△r-1表示△r的倒数，或称为逆元素，∧(r-1)(x)表示上一次迭代中得到的∧(x)的值。有限域上求逆的计算可以通过LUT来实现，用一个片上ROM事先存入所有元素的逆值，根据输入元素的值，在ROM输出端给出对应的逆值。在计算出错误位置多项式σ(x)(即图3中所示∧(x))之后，关键方程求解模块将利用它的值来计算错误值多项式ω(x)的值，ω(x)的系数ωi为：ωi=ij=0ΣSjσi-j(10)在实现关键方程求解电路时，采用了划分时钟的方式，将系统时钟sys_clock依次划分为pclk0、pclk1、…、pclk4，共5个节拍。其中pclk0和pclk1用于驱动△r计算模块；pclk2用于驱动△r求逆模块；pclk3用于判断δr和L的值，并寄存上一次迭代中变量B(x)的值以用于后面的计算；pclk4则用于计算错误位置多项式∧(x)以及中间变量B(x)的值，该模块需要将错误位置多项式的值反馈到输入端以进行迭代计算。1.3钱搜索和Forney算法及电路实现结构求出向量Σ后，由钱搜索方法得出错误个数和错误位置，最后使用Forney算法将错误值与错误码字相加，得到正确的码字。对于一段在GF(2m)域上的RS码流，若其包含码字为2m-1个，则称该码流为非截短RS码，否则称之为截短RS码[4]。以基于GF(28)的RS码为例，在该伽罗华域66上的非截短RS码流应该包含255个码字，这里所讨论的（26，16，4）型码只有26个码字，故为截短码。对于包含j个码字的截短RS码，可以将其理解为包含j个有用码字和αm-1-j个0元素的非截短RS码。设非截短RS码为（n，k），当缩短p个码字时，可表示为（n-p，k-p），则该截短码的接收序列可以表示为：r(x)=rn-p-1xn-p-1+rn-p-2xn-p-2+…+r1x+r0(11)在对截短RS码应用钱搜索方法时，检查该码流中的第l位码字是否出错，实际上就是计算α-(n-p-1)=α(p+1)是否为错误位置多项式σ(x)的根[4]。如果第rn-l位码字有错，则根据Forney算法，其差错值Yn-l按如下公式计算：Yn-l=ω(αp+l)αp+l×σ′(αp+l)=1+ω1αp+l+ω2α2(p+l)+…+ωtαt(p+l)αp+l×(σ1+σ3α2(p+l)+…+σt-1α(t-2)(p+l))=1+ω1αp+l+ω2α2(p+l)+…+ωtαt(p+l)13t-1(12)观察式(12)可以发现，其分子和分母多项式的结构相似，将每一项系数计算出之后，将各个系数相加，便可得出ω(αp+l)和αp+l×σ′(αp+l)这两个结果。以计算ω(αp+l)为例，其电路结构如图4所示。由于有限域上的加法运算是按位异或，不存在进位问题，所以图4所示5个计算单元可以并行计算，最后同时将计算结果送至输出端的加法器。2RS译码器实现结果的验证及分析在FPGA上进行实现之前，将设计所用到的解码算法在matlab6.5上进行了验证。结果表明，对包含4个错误码字的（26，16，4）截短RS码可以进行准确无误的差错和纠错。为了验证在FPGA上实现的结果是否正确，在QuartusⅡ6.0的波形仿真文件中输入了同样的码流，如图5所示，其中用椭圆所圈为错误码字。在QuartusⅡ6.0环境下的时序仿真结果显示，该译码器伴随式计算模块耗时不超过30个时钟周期，而关键方程求解模块消耗的时间最多，在100个时钟周期左右；钱搜索和Forney纠错模块同时进行，其总消耗时间约50个时钟周期。由此也可以看出，关键方程的求解是决定RS译码器速度的最重要步骤。系统时钟频率设为100MHz，经过184个时钟周期（1.84μs）后可得到译码结果，与软件译码方式相比，其耗时非常少。图6中的judge信号显示了输出码字对应于输入码字的错误位置，当该信号为高电平时表示对应位置的输入码字有错，并进行了纠正。该方案已经应用到了基于AlteraCycloneⅡ型FPGA的二维条码识读器中。参考文献[1]张小平.RS码迭代译码算法分析[J].现代电子技术，2021，28(2)：95-98.[2]王进祥，张乃通，来逢昌，等.流水线结构RS(255，233)译码器的VLSI设计[J].计算机研究与发展，2021，37(1)：61-65.[3]刘志伟，邹雪城，刘政林，等.串行迭代结构在RS解码器设计中的应用[J].计算机与数字工程，2021，31(5)：36-40.[4]王伟，徐辉，邹火儿.一种RS码译码器的硬件实现方法[J].无线电通信技术，2021，30(1)：9-10.[5]张国华，王菊花.一种高速Reed-Solomon译码器的实现结构与Simulink建模仿真[J].空间电子技术，2021，1(2)：17-22.(收稿日期：2021-12-16)67《电子技术应用》2021年第7期