RS译码的BM迭代算法及其FPGA实现.doc

RS译码的BM迭代算法及其FPGA实现

发布日期:2006-04-21　作者:张辅云 葛建华 来源:电讯技术

摘 要：介绍了运用于RS译码中的BM迭带算法及利用BM迭带进行RS译码的基本原理，同时给出了该算法的FPGA实现，并通过在高清晰度数字电视接收机中验证了设计的可行性与可靠性。
关键词：RS译码；BM迭带算法；FPGA；高清晰度数字电视
一、 引言
RS码是一类具有很强的纠错能力的BCH码，也是一类典型的代数几何码，它首先由里德（Reed）和索罗蒙（Solomon）应用MS多项式于1960年构造出来。在一般的应用中 ，RS码可以作为单码单独使用；而在信道条件极为恶劣的应用中，如移动通信、卫星通信等具有多径衰落特性的信道中，也可以作为外码提供纠错能力更强的串行级联码，这样在不增加译码复杂度的情况下，可以得到高的编码增益和与长码相同的纠错能力，最常见的一种结构就是将RS码作为外码，卷积码作内码的级联码。RS译码主要有时域译码和频域译码，时域译码通常采用BM迭代算法或者欧式算法(Euclid′s Algorithm)。本文主要介绍BM迭代算法原理及以此算法为基础的RS译码器的FPGA实现。
RS译码可分为3步：第一步由接收到的码组计算伴随式；第二步由伴随式计算出错误图样；最后由错误图样和接收码组计算出可能发送的码字。
二、BM迭代译码算法的基本原理
时域上的RS译码的关键在于求解错误位置多项式,1966年伯利坎普（Berlekamp）提出了可以由伴随式计算错误位置多项式的迭代译码算法，这极大地加快了求解错误位置多项式的速度，该方法简单且易于实现，从而从工程上解决了RS译码的问题；1969年梅西（Massey）指出了该算法与序列的最短线形移位寄存器综合之间的关系，并进行了简化，因此，此译码算法就称为BM迭代译码算法。
如果由接收码组已经求出了伴随式S=［S1,S2,…,S2t］,其中，t为RS码的纠错距离,记S(x)=1+

上式即为求解错误位置多项式的关键方程，且它其实说明了S(x)σ(x)的最高次数不会大于2t。在上式中，S(x)是已知的，因此，可以利用上式进行迭代。先人为设定σ(x)和ω(x)的初始值，然后以此初始值表示下一次迭代的结果，并使得下一迭代结果的次数不减，如此反复迭代求出满足(1)式的方程即可。由于每一次迭代都使得σ(x)和ω(x)的次数不减，故迭代至第j步时，应有：

通常，满足(2)式的每一步迭代都不是唯一的，因此必须对迭代过程加以条件限制。
在m进制无记忆离散对称信道中，如果信道转移概率p<1/m，则信道产生错误个数少的可能性最大，即σ(x)次数越低的可能性越大。故如果每一次迭代都能保证求的σj(x)次数最低，且满足此时的译码结果就是满足译码错误概率最小的最大似然译码，并且此时的解是唯一的。

其中i是j前面的某一行，且满足最大，这样能保证每次迭代总是使σ(x)的次数最小化。因此，令j=-1和0，得到两组初始值，利用(3)式求出dj，再结合(４)式和(５)式即可得到下一步的结果。迭代步骤如下：

否则，由(4)式和(5)式求出σj+1（x)、ωj+1(x)，然后进行下一次迭代。
三、FPGA实现及调试
1.FPGA实现电路
该算法的FPGA实现电路如图1所示。

其中，Syndrome模块主要完成伴随式的计算，Dj和Di模块分别完成dj和dj/di的计算，Iterater模块则完成迭代的更新及计算，Sj和Oj分别为需要求出的σj(x)和ωj(x)。当同步信号SYN到来时，所有模块完成初始化，di、Sj和Oj初始化为1。Syndrome模块求出伴随式Spoly后串行输出，同时将此刻的迭代次数Ite－Num输出，而且当迭代达到要求的次数时，输出一个CLR信号，在Dj模块接收到此信号后，将dj置为0，于是后面的输出不再改变，直到下一同步信号SYN到来；Dj模块用一组移位寄存器将伴随式的当前状态和之前的t个状态缓存,和当前Sj一起可以求出dj,当dj不为0时，同时计算输出到J－rank中；为了让下一步的计算更简单，Di模块中计算直接dj/di和rank=j-i的值，di的逆元用一个查找表来完成，同时预设=0，当该值小于J－rank时，将此时的存储值作相应的更新，同时输出一个fresh信号以标明这种更新；Iterater模块在收到fresh信号后进行相应的更新。
在设计过程中，可以将(4)式和(５)式中求满足i-

一个完整的RS译码原理框图如图2所示。其中，伴随式计算电路由输入的码组计算出相应的伴随式，同时将结果送到下一模块中，该模块即为实现BM迭代算法的电路。伴随式经BM迭代后，计算出错误位置多项式σ(x),同时也计算出ω(x)。Chien搜索电路则由给定的σ(x)找出错误位置，然后控制门打开或者关闭，当该位置有错时，门打开，输出该位置上的错误值，当该位置没有错时，门关闭，此时错误值为0。利用σ(x)和ω(x)可以进行错误值的计算。因为整个译码过程中存在延迟，为使相应的数据互相对齐而必须加入一个移位存储器。

2.电路调试
经过软件仿真和硬件电路仿真后，就需要将编译后的程序下载到实际的FPGA芯片中调试，以验证实际电路的正确性和可靠性，这是电路设计中的一个重要步骤。软件仿真主要是产生正确的数据源以验证硬件电路仿真的结果，软件仿真主要采用的是Matlab6.1。Matlab是Mathworks公司推出的一套仿真软件，其数学运算功能非常强大，是工程中一种非常理想的仿真工具，在调试过程中主要是提供调试数据、结果数据，包括中间结果。硬件电路仿真是用电路设计软件完成电路设计，我们使用的是ALTERA公司的Quartus2.0软件，再进行编译、仿真，仿真的结果要与上面Matlab的仿真结果一致。

当上面的验证完成后，就可将编译后的程序下载到实际的FPGA芯片中调试，然后用逻辑分析仪随机抓取数据，保存到文件中，并与Matlab仿真的结果进行比较，如果不正确，则对电路中的每一模块进行查错、修改，直到用逻辑分析仪随机抓取数据完全正确为止，此时可认为电路调试完成。Quartus2.0电路仿真结果如图3。
图3的仿真图给出了在GF(256)内用Quartus2.0进行BM迭代算法的电路仿真结果，为了进行详细对比，我们将每一次迭代结果都保留下来。经比较，该结果和Matlab仿真的结果完全一致。
四、结语
本文的FPGA实现是用Verilog硬件描述语言编写，并在Altera公司QuartusⅡ电路仿真环境下仿真、选用该公司APEX TM EP20K600EBC652—1XES系列芯片来完成的，结合别的FEC模块，将其应用于数字高清晰度电视(HDTV)接收机机顶盒的设计中，经过性能测试，达到了系统指标要求。而且由于该设计是用Verilog硬件描述语言编写调试的，因此，可移植性较强。在调试通过后，将该模块植入基于Xilinx的Virtex2系列芯片设计的电路中同样能满足系统要求。因此，该设计不仅可以和别的FEC技术结合，提供强大的纠错能力，同时，也可以专门应用于ASIC设计中。与此同时，我们也用FPGA实现了基于欧式算法的RS译码器，但比较而言，BM迭代算法较为简单，易于实现，且比欧式算法能节省一半左右的资源。

参考文献
［１］王新梅，肖国镇.纠错码［Ｍ］.西安：西安电子科技大学出版社，2001.
［２］Donald E Thomas, Philip R Moorby,刘明业，等.硬件描述语言Verilog［Ｍ］.北京：清华大学出版社，2001.
［３］刘宝琴，张芳兰，田立生. Altera 可编程逻辑器件及其应用［Ｍ］.北京：清华大学出版社，1995.
［４］郝东来.COFDM传输系统中编解码技术的研究［Ｄ］. 西安：西安电子科技大学