1、RS 系列编译码器的设计与 FPGA 实现摘 要 本文介绍了 RS(255，223)编译码器的实现，其中 RS 编码器的设计中，利用有限域常数乘法器的特性对编码电路进行优化，将所有的乘法器转化为加法器。RS 译码器采用欧几里德算法，同时考虑到并行结构所需的硬件资源较多，译码器均采用串行结构实现。这些技术的采用大大提高了 RS 编译码器的效率，在保证速度的同时最大限度地减少了资源占用。 关键词 RS 码；卷积码；欧几里德算法；FPGA1 引言RS 码是一种有很强纠错能力的多进制 BCH 码，也是一类典型的代数几何码。它首先由里德(Reed)和索洛蒙(Solomon)应用 MS 多项式于 1960
2、年构造出来的。它不但可以纠正随机差错，而且对突发错误的纠错能力也很强，因此广泛用于差错控制系统中，以提高数据传输的可靠性。如今，RS(255，223)已被美国航天局和欧洲空间站在太空卫星通信的级联码系统中作为标准的外码以采用。2 RS(255，223)编码器设计2.1 RS(255，223)编码原理RS(n，k)码是一种非二进制的 BCH 码，工程上的 RS 纠错编码方式为RS(255，223)，该码的基本特性如下：码类型：系统码，非透明码字长度：每个 RS 码字中包含 n=2J-1=255 个 RS 符号=2558bit；检验位数：n-k=2t纠错能力：可纠任一个 RS 码字中的 t=16
3、个 RS 符号差错；码最小距离：dmin=2t+1码的符号：有限域 GF（2J）中的元素，每个 RS 符号由 J=8bit 构 成，即 GF（2）上的 8 维行向量；码字中信息符号数目：k=n-2t=223 个；码字格式：d1d2d3did223 p1p2pkp32，其中 di 为第 i 个数据符号，pk 为第 k 个校验符号；域生成多项式：有限域 GF(28)在其特征域 GF(2)上的生成多项式为：F（X）=X8+X4+X3+X2+1其中 F（X）为域生成多项式，X 为多项式变量； 码生成多项式：g(x)=(x+a)(x+a2).(x+a32)式中，g(x) 是码生成多项式；ai 是 GF(
4、a8)中一个元素。2.2 RS(255，223)编码的 FPGA 实现应用 Matlab 中的符号乘法，得到 RS（255，223）生成多项式中的32 项乘法系数。结合域生成多项式 生成的监督矩阵表a0，a1，a2a254，通过查表得到 32 项码生成多项式的系数a18，a251，a215a11，即因此，RS（255，223）编码器示意图如图 1 所示。图 1 RS（255，223）编码器示意图由于 GF(28)上的 RS 码是 2m 进制码，GF(28)中的每个元素均可表示成它的自然基底 1， 的线性组合：以乘 a8 为例可以表示为：a8(a0+a1a+a2a2+a3a3+a4a4+a5a5
5、+a6a6+a7a7)=a7(a5+a2+a)+a6(a4+a+1)+a5(a7+a2+a+1)+a4(a7+a6+a3+a2+1)+a3(a7+a6+a5+a3)+a2(a6+a5+a4+a2)+a1(a5+a4+a3+a)+a0(a4+a3+a2+1)=a7(a5+a4+a3)+a6(a4+a3+a2)+a5(a7+a3+a2+a1)+a4(a6+a2+a1+a0)+a3(a4+a3+a1+a0)+a2(a7+a5+a4+a2+a0)+a1(a7+a6+a5+a1)+a0(a6+a5+a4+a0)综上推导，我们可以把所有的乘法器变化为加法器，即模二和的形式。如图 2 所示。用输入数据信息实
6、例进行了仿真。即输入信息为 0，1，2222，时，32 个校验位输出为102，212，116，164，159，61，229，39，17，244，245，67，253，18，156，217，115，73，31，174，27，140，69，159，104，219，254，187，173，169，10，116。图 2 的加法器表示3 RS(255，223)译码器设计译码器的实现主要包括下面四个流程：伴随式计算、关键方程求解、钱搜索计算错误位置、福尼算法计算错误值。原理参考文献1-4。3.1 伴随式计算定义伴随多项式为其系数为其中，n=255，i=132， 为 x8+x4+x3+x2+1=0 所生成的
7、 GF(28)中的本原元。 3.2 关键方程求解定义错误位置多项式为错位值多项式为结合上一步求出的伴随多项式，根据 RS 码的性质，我们有称它为关键方程。上式可写成由 Euclid 算法3可以知道 (x)是 S(x)与 x2t+1 的最大公因子。同时，由简单的证明可知，只要假设 U-1=1，U0=0，V-1=0，V0=1，即可利用每一次求到的 qj(x)，来求出当前时刻的 Uj(x)和 Vj(x)，因此可以得到 Euclid 译码算法流程图如图 3 所示。当求出 (x)和 (x)后，利用它们可以求出错误值，从而利用钱搜索，可找出错误位置，求出错误图样，从而实现译码。3.3 钱搜索计算错误位置在
8、上一步关键方程中求得 (x)后，接下来的问题是从工程观点看，如何简单地求出它的根即错误位置。1964 年钱闻天提出了一个求 (x)根的使用方法，解决了这个问题。解 (x)的根，就是确定 R(x)中哪几位产生了错误。设 R(x)=rn-1xn-1+rn-2xn-2+r1x+r0，为了要检验第 k 位 rn-k 是否错误，相当于译码器要确定 n-k 是否是错误位置数，这等于检验 -(n-k)是否是(x)的根。若 -(n-k)是 (x)的根，则这样依此对每一个 rn-k(k=1，2，n)进行检验，就求得了 (x)的根，这个过程称为钱搜索。图 3 Euclid 译码算法流程3.4 福尼算法计算错误值R
9、S 译码的最后一步就是求错误值 Yi。设实际产生的错误个数t，则由可知：所以由于恒等式左边最高次数为 2，故上式成为求 (x)的导数形式另 x=xi-1，则上式成为所以令 x= xi-1，则上式成为所以错误值注意上式可写成其中 xi 是错误位置对应的本原形式，(x)和 (x)分别是错误位置多项式和错误值多项式，(x)为 (x)的一次导数。其中，1，3为错误位置多项式奇数项系数3.5 RS(255，223)译码的 FPGA 实现3.5.1 伴随式计算的实现伴随式计算电路结构如图 4 所示。图 4 中 R0R254 为译码输入。为了节省硬件资源，同时考虑到每个伴随式系数在计算上相互没有关系，故采用
10、串行计算得到 Si。具体做法为：首先将译码输入 R0R254 写入到一个片内 RAM，每计算一个伴随式，将其从 RAM 中串行读出，并进行迭代运算。图 4 伴随式计算电路3.5.2 关键方程求解的实现在欧几里德(Euclid)算法3中，用到了多项式的除法和乘法运算，为了节省资源，必须利用一个有效的刷新办法对该除法器和乘法器进行实时刷新，使得每进行一次迭代后，除法器和乘法器中的内容及时更新，我们把3中的算法结构上做如下的改进：在做多项式除法和乘法之前，先进行数据的并串转换。这样只要一个多项式除法器和一个乘法器就可完成该算法，在保证运算速度的同时也最大限度地节省了硬件资源。在下面的部分给出这两个模
11、块的实现。1) 多项式除法器假设多项式 A(x)除以 B(x)的商为 q(x)，余数为 r(x)。若某次迭代时 A(x)的阶数为 m，B(x)的阶数为 n，mn。由多项式除法原理可知，q(x)=Bn-1Amxm-n，每次同 m-n 一起输出；而 r(x)=A(x)-B(x)q(x)是一个降次的过程，每降一次都需要将 A(x)用 r(x)刷新，直到它的阶数小于B(x)的阶数时，表明此次除法运算结束，用 B(x)和 r(x)分别对 A(x)和B(x)进行同步刷新，继续进行下一次除法运算。当 r(x)的阶数小于或等于 t 时，算法中的除法迭代运算结束。在实现中有两点需要注意：第一点是我们用两组固定长
12、度的寄存器来存放 A(x)和 B(x)的系数，除了第一次初始化的时候需要给出它们的阶数外，以后每次它们的阶数都是由 r(x)或上一次的 B(x)的阶数直接赋值，而由于每次 r(x)是串行得到的，其阶数能通过判断每次的值是否为零累加得到；第二点是每次在对存放 B(x)系数的寄存器进行更新时，应将 B(x)的最高位和 A(x)的最高位对齐，从而方便 r(x)的求解，同时在用 B(x)对存放 A(x)系数的寄存器进行更新时应注意该操作带来的影响。整个多项式除法器的实现如图 5 所示。2) 多项式乘法器多项式乘法器：将多项式除法运算的结果 q 和 deg(q)实时输入多项式乘法器，A(x)赋初值 1，
13、B(x)赋初值 0，每完成一次除法运算，多项式除法器模块给此模块一个控制信号，A(x)与 B(x)互换。迭代运算时代门关闭，输出无效；当除法迭代结束时，多项式除法器模块的控制信号控制门打开，输出有效。多项式乘法器如图 6 所示。3.5.3 钱搜索计算错误位置的实现在工程上，钱搜索过程可用图 7 所示的电路实现，它的工作过程如下：(1) t 个寄存器寄存 1，2，t，当错误个数 t，则+1=+2=t=0。(2) rn-1 正要从缓冲存储器读出之前，t 个乘法器由移位脉冲控制乘法运算，且 1，22，tt 存在 寄存器中，并送入 A中进行运算和检验。若等于-1，则 A 输出一个信号，控制门打开，把错
14、误值 Yn-1 与缓存器输出的 rn-1 相减，得到 rn-1-Yn-1=cn-1。(3) rn-1 译完后，再进行一次相乘，此时 12，2(2)2，t(t)2 存在 寄存器中，并在 A 中进行相加运算和检验，对rn-2 进行纠错。(4) 其余码元同(2)一样纠错。图 5 多项式除法器流程图图 6 多项式乘法器流程图图 7 Chien 搜索电路(并行)以上的计算是并行计算的，我们在处理中，为了节省硬件资源而采用串行计算，需要把每次迭代的数储存起来，在这里使用了一个片内RAM，实时更新里面的内容，同时 RAM 的数据地址表示移位次数。当116 都移位完成之后，输出 RAM 数据为 0 的数据地址
15、即移位次数表示错误位置。改进的串行计算部分电路图如图 8 所示。图 8 Chien 搜索部分电路3.5.4 福尼算法计算错误值的实现福尼算法计算错误值可以采用与钱搜索类似的电路实现。同样，在计算错误值多项式时，我们也采用串行计算，刷新片内 RAM 并累加得到，整个福尼算法的电路如图 9 所示。图 9 福尼算法电路4 编解码性能测试与仿真（1）选取具有代表性的测试数据序列，把编码结果与 matlab 计算结果比较完全正确。（2）把编码器与译码器级联，确认译码器输出结果完全正确。（3）将编码器一组输出码字的任意 16 位出错作为译码器的输入，经过仿真 16 位均被纠正。（4）实现卷积(4，3，3)
16、与 RS(255，223)级联，确认输出结果正确。如图 10 所示，为卷积(4，3，3)与 RS(255，223)级联的仿真图。图中rsin 为 RS 编码器输入，rsout 为编码器输出，jlianout 为 RS(255，223) +卷积(4，3，3)级联编码输出，corr_code 为 RS(255，223) +卷积(4，3，3)级联译码输出。图 10 RS(255，223) +卷积(4，3，3)级联编码输出时序5 FPGA 资源分析本文 RS(255，223)编译码器的设计通过 Altera 公司的 Quartus软件开发平台上完成了功能仿真、编译综合并优化、布局布线、时序仿真等工作。
17、本文选用 Cyclone系列器件的 EP2C8T144C8，分别将上述译码器实际占用 FPGA 资源情况如表 1 所示。表 1 编译码器片内资源占用情况6 结论本文介绍了 RS(255，223)编译码器的设计以及 FPGA 实现，并通过了Quartus的功能仿真，布局布线和时序仿真。在 30MHz 的时钟频率下编译码器的数据吞吐率为 240Mbps，译出一桢数据 255byte 需 1.2ms，相比与目前的一些文献，占用的硬件资源较少且速度较快。FPGA 的仿真测试表明译码的技术指标均符合要求，该设计不仅可以和别的 FEC 技术结合，提供强大的纠错能力，而且也可以专门用于 ASIC 设计中。参考文献1王新梅，肖国镇.纠错码原理与方法M.西安：西安电子科技大学出版社.19962SHI Junfeng，WANG Yu，SUN Huixian. The implementation and verification of RS(255，223) decoder according to CCSDS specificationJ. Chin.J.Space Sci. 2005.25(4)：309-3143张辅云，葛建华. RS 译码的 Eculid 算法及其 FPGA 实现J.中国有线电视，2003(14)：6-94曹志刚，钱亚生.现代通信原理M.北京：清华大学出版社.1997
