RS码是Reed-Solomon码的简称，它是线性分组纠错码中的一种。与同类纠错码比较，在同样编码冗余度下，RS码具有较强的纠错能力，目前主要应用于深空通信、存储系统(如VCR、DVD光盘)、数字广播电视等领域中。RS码的译码相对于编码难度更大，且随着码长的增加，译码电路的复杂性也随之巨增。近年来，由于大规模集成电路技术及EDA技术的发展，使得研究译码器的硬件实现成为国内外信道编码技术的一个热点。
　　RS译码算法根据解关键方程的不同，主要可分为两大类：BM迭代算法和Euclid迭代算法(以下简称欧氏算法)。对这两类迭代算法的RS译码器硬件结构的设计，国外已有不少文献提出了一些好的设计方法[1～3]，其核心都是为了减少硬件结构的复杂性和提高工作效率。本文主要也是围绕这个核心介绍一种新改进的欧几里得算法^[5]，并针对RS(255,239)码给出基于时域译码的流水线结构的FPGA实现。
1 RS时域译码算法介绍
1.1 RS码的时域译码步骤
　　RS码的时域译码步骤一般分为如下三步：
　　(1)由接收到的码组r计算伴随式：

　　由于本文采用的是RS(255,239)码，故码组长n=255字节，信息字节长k=239,校验字节长m=16，纠错数t=8，最大距离d=2t+1=17。
　　该码对应的本原元多项式为：
　　

　　S_j和g(x)两式中都取m0=0。
　　(2)由伴随式计算错误位置多项式和错误值多项式
　　主要是通过解关键方程Ω(x)=Λ(x)S(x) mod x^2t求出错误位置多项式Λ(x)和错误值多项式Ω(x)。对于纠错数较多的RS码，解方程的算法主要有两类：BM迭代算法和欧氏算法。本文将在后面详细介绍欧氏算法。
　　(3)根据第二步的结果计算出错误图样，然后由错误图样和接收码组在GF(2)域上进行加法操作，恢复出正确的码组。
　　此外错误图样的计算需要利用Chien搜索电路、存放逆运算查找表的ROM存储器，以及Forney公式Y_j=Ω(α ⁱ)/Λodd(α ⁱ)^[2]。
　　另外，该算法还要通过C语言进行仿真，以便减少FPGA实现过程中调试、查错的工作量，从而使上述步骤中每一步FPGA实现的正确性都能得到进一步的保证。
1.2 新改进的欧氏算法基本原理
　　欧氏算法的主要原理是通过欧几里德多项式除法多次相除，得到所求错误位置多项式和错误值多项式。其中，除法电路实现非常复杂，要耗费较多的硬件资源，故改进的欧氏算法以减法(在GF(2^m)迦罗华域中减法即加法)替代除法，从而消除除法电路。其具体算法步骤如下： (1)赋初值
　　

　　(3)回到步骤(2)
　　这种新改进欧氏算法的特点是：迭代次数恒定，最高次项系数的位置固定。这些特点将使其硬件结构控制单元更简单，数据处理单元更规则，易于用Verilog HDL实现。
2 译码器的FPGA实现及仿真
2.1流水线式译码器的的整体结构
　　译码器的流水线结构(见图1)由三级流水线构成，在时域上实现前面所述译码算法的三个步骤。其中第一级流水线和第三级流水线各需255个数据处理时钟周期" title="时钟周期">时钟周期和一个寄存器初始化时钟周期，而第二级流水线在不考虑 EL(错误位置多项式)和 EE(错误值多项式)单元复用的情况下，只需16个数据处理时钟周期和一个寄存器初始化时钟周期，这样它会有239个时钟周期处于空闲状态。这里时钟周期是指码组中每个码元的传输时间。

　　采用流水线的优点是：能提高译码器的工作效率，加快其数据处理速度，使之适用于高速通信场合。但缺点是：可能需要耗费额外的流水线寄存器，以保留中间结果。不过，在RS译码器中，由于可以利用其本身特有结构中的寄存器，故不会增加过多的硬件资源。
　　图1译码器中关键方程求解模块是限制整个译码器工作速度的瓶颈，并占用了译码器硬件资源的很大部分，故下面着重介绍该模块的硬件实现及其改进结构(其余模块的硬件实现可参考相关文献)。
2.2 关键方程求解(KES)模块的FPGA实现
　　图2为前面介绍的欧氏迭代算法(即KES模块)的硬件实现电路，它由数据处理单元和控制单元两部分构成。其中数据处理单元中的EE(如图3)和EL(同图3)采用寄存器分组并行方式计算错误值和错误位置多项式，两者的多项式最高次项系数δ，γ都由EE中寄存器R₁₅^(b)，R₁₅^(a)提供，其硬件结构相同，非常规则，分别由2t+1个 完全相同的基本单元PE构成。当KES模块开始工作时，先对EE、EL中的寄存器初始化，即完成欧氏算法步骤(1)。然后在控制单元的控制下，迭代16次就得到结果。迭代中需要多次调用加法器、乘法器来完成迦罗华域的乘、加运算，加法器可由简单的位异或操作实现，而乘法器的实现则较复杂，要占用较多的硬件资源，有多种实现方法。本文根据文献^[4]设计了一种基于对偶基的乘法器，其占用的门电路数较少，且延时也较少。该算法实现的另一特点是：控制单元(见图2(b))很简单，无需普通欧式算法中多项式次数计算等复杂操作。

　　最后，使用QuartusII3.0软件，在ALTERA公司的APEX 20k系列的芯片EP20K1500EFC33-1上实现整个译码器，占用LE (逻辑单元)的总数为4972个，其中EE单元占LE数为1847个，EL单元占LE数为1670个，故关键方程求解模块的数据处理单元占用了3517个LE。
2.3 关键方程求解模块的改进
　　由以上分析可知，因为结构相同的EE和EL都使用了大量的组合逻辑部件：乘法器、加法器、多选器，故可以采用分时复用技术对它们进行复用，以节省硬件资源。分时复用的一种方法具体如下：将EE和EL中对应位置的PE合并为一个基本单元，并通过增加复用器，在不同的时钟节拍，有选择地对不同的寄存器操作，从而达到面积复用的目的。但是，过多的复用器一方面增加了每次迭代的计算延时，降低了工作速度，另一方面也要耗费硬件资源。为了克服这些缺点，本文采用了一种特殊结构对PE单元进行改进。PE单元的硬件结构如图4所示。改进后PE结构与改进前比较，其寄存器分别被替换为一循环移位寄存器和一左移寄存器，这样就避免了加入额外的复用器。同时为了保持与译码器中其它模块的同步，KES模块的时钟信号频率提高为原来的两倍，利用奇数时钟节拍计算错误位置多项式，利用偶数节拍计算错误值多项式。改进后的译码器在QuartusII软件上编译,并经综合、布局布线后，最大工作频率可达71.01MHz，占用LE的总数为3517个，其中KES模块中的数据处理单元仅占用LE数2111个。

2.4 FPGA仿真
　　为了验证译码结果的正确性，可将编码后的数据人为地加入不超过8个的错误字符，将接收后译码得到的码组与编码所得的原始码组相比较，若一致，则说明译码正确。QuartusII编、译码仿真波形如图5所示，data为239字符长的信息符号，code为编码后得到的255字符长码组。这里为便于观察，取data的前236字节为全0，后三字节分别为1、2、3。fout为人为噪声干扰后经过缓冲器延时所接收的码组，err_pattn为错误图样，dout为译码后所得正确编码。

　　本文提出一种RS码时域译码的流水线结构的FPGA实现，它采用分时复用技术对译码器的关键模块——解关键方程模块的结构进行了改进。在ALTERA公司APEX 20k系列芯片EP20K1500EFC33-1上的实现表明，改进后的解方程关键模块占用的逻辑单元数减少了1406个，并经综合、布局布线后，工作频率最大可达71.01MHz。该结构有如下特点：无多项式次数计算，迭代次数恒定，控制单元简单；结构非常规则，易于用Verilog语言实现；复用错误位置和错误值多项式的PE单元后，仍可应用于高速通信场合。
参考文献
1 H.M.SHAO,T.K.troung,L.J.Dentsch.A VLSI Design of a Pipeline Reed-Solomon Decoder[J].IEEE Transactions on Computers.1985;C-34(5):393～403
2 S.Kwon and H.Shin.An Area-efficient VLSI Architechure of a Reed-Solomon Decoder/Encoder for Digital VCR′s[J].IEEE Transaction on Consumer Electron,1997;43(4):1019～1027
3 H.M.Shao, IS.Reed. On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays[J].IEEE Trans-actions on Computers.1988;37(10):1273～1280
4 S.T.J.Fenn，Benaissa,D.Taylor.GF(2m) Multimpilication and Division Over the Dual Basis[J].IEEE Transactions on Com-puters,1996;C-34(3):319～327
5 Y.W.Chang，T.K.Troung，J.H.Jeng.VLSI Architechure of Modified Euclidean Algorithm for Reed-Solomon Code[DB]. http://elsevier.lib.tsinghua.edu.cn/pdflinks/04052214422103738.pdf,2003