基于FPGA的RS码译码器的设计

摘要：介绍了符合CCSDS标准的RS(255，223)码译码器的硬件实现结构。译码器采用8位并行时域译码算法，主要包括了修正后的无逆BM迭代译码算法，钱搜索算法和Forney算法。采用了三级流水线结构实现，减小了译码器的时延，提高了译码的速率，使用了VHDL语言完成译码器的设计与实现。测试表明，该译码器性能优良，适用于高速通信。
关键词：RS码；FPGA；译码器；有限域；改进的BM算法

    在数字通信中，信号在有噪信道中传输，不可避免的会受到噪声的干扰，引起误码。在已知信噪比的情况下要达到一定的误码率指标，在合理设计基带信号，选择调制解调方式，及时域均衡或频域均衡的基础上，使用差错控制技术可以使误码率进一步的降低。RS码属于分组码，是BCH码的一个子类，是最大距离可分码，它是由Reed和Solomon于1960年构造出来。由于它具有很强的纠正随机错误和突发错误的能力，以及极低的不可探测的差错率，所以RS码已经广泛应用于深空通信、卫星通信、存储介质、数字视频广播和扩频数字通信中。
    在一些特定应用域中，RS码的设计和实现是比较困难的，RS码是在有限域上进行的代数运算，不同于常用的二进制系统，现实相对复杂一些，其复杂度主要决定于有限域的大小、码字的长度，采用的编码算法等。FPGA能够快速和经济的将电路描述转化为硬件实现，而且对设计的修订也比较方便。文中使用VHDL语言设计了RS(255，223)译码器，并经过了PFGA芯片上的验证。整个设计采用流水线结构，提高译码器的数据吞吐量，同时对电路结构进行优化，减少体积和时延，非常有利于微小卫星中应用。

1 RS码译码原理及实现
1．1 RS(255，223)码的参数
    RS(255，223)是在有限域GF(28)中计算得到的，其具体参数为：
    1)每个符号的bit数：m=8；
    2)每个码字包含的符号个数：n=28-1=255；
    3)每个码字包含的信息位的符号个数：k=223；
    4)码字中校验位的符号个数：2t=255-223=32；
    5)一个码字所能纠错的最大符号数：t=16；
    6)GF(28)域的本原多项式：f(x)=x8+x7+x2+x+1；
    7)生成多项式：

1．2 RS码译码原理
    RS译码算法有两类：时域译码和频域译码。在实际工程中，由于RS码符号通常取自有限域GF(28)上，采用时域系统码编码方式，系统码编码方式可较容易缩短，满足工程应用的需求。如图1所示，RS码时域译码器主要分为四个模块：伴随式计算模块、错误位置多项式计算模块、钱搜索模块、错误值计模块。其中错误位置多项式计算采用修正后的无逆BM迭代算法，错误值计算采用Forney算法，还需要一个FIFO来
缓存所接受的码字，使与经过译码后计算出的错误值同步。

    RS码时域译码的一般步骤为：
    1)根据接收的码字计算伴随式，如果计算出来的2t个伴随式都等于0，那么表示接收的码字没有错误，不再进行下面的步骤，否则进行下面的步骤；
    2)利用计算好的伴随式计算错误位置多项式和错误值多项式；
    3)计算错误位置和错误值；
    4)根据计算的错误位置和错误值可得到错误多项式E(x)，将接收的码字R(x)与E(x)相加，即可译码。
1．2．1 域内加法器和乘法器
    有限域GF(2m)中的元素都可以用二元域GF(2)中的元素的m重来表示，域中的任意元素都可以用次数小于m的多项式表示，加法和乘法运算是有限域GF(2m)中最简单的运算。
    有限域上的加法比较简单，只需要对m维并行数据进行异或即可。
    有限域上的乘法通常认为是时延较大，结构复杂的运算操作。有限域的乘法器，即对于域内的任意两个元素，可以用m-1次多项式来表示，这样两个元素的乘积为2m-2次多项式，再把乘积对有限域的本原多项式求余，所得的结果即为两个元素的乘积。文中的乘法器是采用八位并行与门和异或门来实现的，这种有限域乘法器的设计充分利用了特征为2的有限域元素的加减法运算即为异或运算的特征，大大简化了设计，同时也使算法描述更简单，且容易实现。
1．2．2 计算伴随式模块
    BS(255，223)译码的第一步就是计算2t个伴随式Si：

    其实现结构如图2所示，在初始阶段，寄存器被清零，输入第一个码字(接收的码字高位)在与零相加后被送入寄存器，再乘以与第二个输入的码字相加，如此循环，直到255个码字全部进去寄存器经过计算后，寄存器内的值便是我们需要的伴随式Si。

1．2．3 修正后的无逆BM迭代算法模块
    求解关键方程是解码器实现中最复杂和占用资源最多的模块，其目的是为了求出错误位置多项式σ(x)，根是错误位置的t次多项式：
   
    关于求解关键方程的算法的已有很多，例如，Euclid算法，非二进制的BM算法等。文中采用修正后的无逆BM迭代算法实现。传统的BM迭代译码算法，每次迭代都有一个求逆的运算，求逆是比较复杂且对硬件要求高的算法。无逆BM迭代算法避免了进行繁琐耗时的求逆运算，但是迭代过程中只计算了错误位置多项式，最后还需要根据关键方程和得到的错误位置多项式来求的错误值多项式，这样也增加了译码的时延。改进后的无逆BM迭代算法，在计算了错误位置多项式的同时也计算了错误值多项式，减少了时钟的损耗，提高了译码的速率。具体实现流程如图3所示。

    图3中λ(x)是计算错误位置多项式σ(x)的辅助多项式，α(x)是计算错误值多项式ω(x)的辅助多项式，k为迭代的次数，δ为前一次迭代和这次迭代的修正项。
1．2．4 钱搜索和Forney算法模块
    错误位置多项式σ(x)和错误值多项式ω(x)确定后，错误位置可以通过求解错误位置多项式的根求得的，工程上用的最多的是钱搜索算法。译码器通过钱搜索算法检查当x=α0，α1，…，αn时，代入错误位置多项式σ(x)中，若σ(αi)=0，则表示αi为出错的位置。
    利用Forney算法可以求得错误位置上的错误值，在已求得错误位置多项式和错误值多项式前提下：
   

    在实现过程中，钱搜索和Forney算法是在一个模块中实现的。对αi进行钱搜索的同时，也把αi输入Forney算法实现结构中，采用流水线结构，这样可以减少时钟周期，经过t+1个时钟后即可以输出第一个纠错后的结果。结构如图4所示，σ0，σ1，…，σ16分别表示σ(x)的系数，ω0，ω1，…，ω16表示ω(x)的系数，x1，…，x16表示αi，…，α16i，对于求σ’(x)时，中间需要等一个时钟，流水线结构一定要注意同步，错开一个时钟都会产生错误。这部分有一个求逆的运算，本文中的求逆运算是用的查表法实现的，查表法的基本思想是GF(28)域上的元素的逆元先计算出来存储到ROM中，将待求逆元作为读取ROM的地址，读出ROM的存储值，该值便是所求结果，这种方法的计算速度非常快。使用这种结构提高了译码的速率。

1．2．5 纠错模块
    当确定可误码的位置及具体的误码值后，也就确定了错误多项式，将得到的错误多项式与接收多项式相加，即完成误码的纠正。
   
    纠错的硬件实现结构如图5所示，是一个二选一的多项选择器，如果代入错误位置多项式后得到的值为0，那么需要将接收值与计算得到的错误值相加，如果不等以0，则直接输出接收值。接收码字需要经过一个缓存器，这样接收值才能与经过译码算法输出的错误值同步，达到纠错的目的。

2 FPGA实现及测试结果
    运用上文提出的硬件实现结构框架，采用VHDL输入，在FPGA上实现了RS(255，223)码的连续译码，使用了XilinxISE10．1编译，采用了xc4vsx55芯片综合，Slice个数为5 209个，占用芯片总数的21％，最高速率达到了149．836 MHz。通过Modelsim6．2验证，采用了三级流水线结构，译码所需时钟周期为255+2*t+2+t+1，文中译码器的时钟周期为306个时钟。

    仿真采用时钟为100 M，将正确的编码后的码字人为的输入16个连续错误和16个分散错误，启动仿真，由波形中引出计算的所得的错误值和相应的错误位置，16个错误均得到了纠正。由图6可以看到输入信号rs_data_in，人为的将27—42改为30、35、128、60、167、250、75、43、108、89、135、40、79、191、2、9。由图7可以看到输出信号rs_data_out，错误的数据已经得到了纠正，验证了译码器的正确性。

3 结束语
    文中实现了RS码时域译码器结构，根据该结构完成了符号取自有限域GF(256)上的RS(255，223)码译码器。这种RS码译码器硬件实现结构具有功能模块化、结构规则化的特点，采用了流水线结构，最大限度提高译码数据的吞吐量，提高了译码速度，适用于高速通信。并且在此基础上只需进行少量更动就可以较容易实现其它码型的译码器，该方案已应用于多个军事通信设备中。