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

1、RS译码的BM迭代算法及其FPGA实现发布日期:2006-04-21作者:张辅云 葛建华 来源：电讯技术TQ2440+3. 5寸寸TFT触摸屏 58。元送USB转串口线摘 要：介绍了运用于RS译码中的BM迭带算法及利用BM迭带进行RS译码的基本原理，同时给 出了该算法的FPGA实现，并通过在高清晰度数字电视接收机中验证了设计的可行性与可靠性。关键词：RS译码；BM迭带算法；FPGA；高清晰度数字电视一、引言RS码是一类具有很强的纠错能力的BCH码，也是一类典型的代数几何码，它首先由里德(Reed) 和索罗蒙(Solomon)应用MS多项式于1960年构造出来。在一般的应用中，RS码可以作为单码

2、单独 使用；而在信道条件极为恶劣的应用中，如移动通信、卫星通信等具有多径衰落特性的信道中，也可 以作为外码提供纠错能力更强的串行级联码，这样在不增加译码复杂度的情况下，可以得到高的编码 增益和与长码相同的纠错能力，最常见的一种结构就是将RS码作为外码，卷积码作内码的级联码。 RS译码主要有时域译码和频域译码，时域译码通常采用BM迭代算法或者欧式算法(EuclidsAlgorithm)。本文主要介绍BM迭代算法原理及以此算法为基础的RS译码器的FPGA实现。RS译码可分为3步：第一步由接收到的码组计算伴随式；第二步由伴随式计算出错误图样；最后 由错误图样和接收码组计算出可能发送的码字。二、BM迭

3、代译码算法的基本原理时域上的RS译码的关键在于求解错误位置多项式,1966年伯利坎普(Berlekamp)提出了可以由 伴随式计算错误位置多项式的迭代译码算法，这极大地加快了求解错误位置多项式的速度，该方法简 单且易于实现，从而从工程上解决了 RS译码的问题；1969年梅西(Massey)指出了该算法与序列的 最短线形移位寄存器综合之间的关系，并进行了简化，因此，此译码算法就称为BM迭代译码算法。如果由接收码组已经求出了伴随式S=耳疽,其中，t为RS码的纠错距离,记S(x)=1+ 命+中错误位置举项式r(x) = I + 0 x+ 电J令*=to(x) ,则经过一系列椎耻可知S(x)(x)和y

4、(x)满足下式：(x) KiJ，f1 )( I)上式即为求解错误位置多项式的关键方程，且它其实说明了 S(x)o (x)的最 高次数不会大于2t。在上式中，S(x)是已知的，因此，可以利用上式进行迭代。先人为设定o (x)和3 (x)的初始值，然后以此初始值表示下一次迭代的结果，并使得下一迭代结果的次数不减，如此反 复迭代求出满足(1)式的方程即可。由于每一次迭代都使得O(X)和3(X)的次数不减，故迭代至第j 步时，应有：钢损/(*) M(2)通常，满足(2)式的每一步迭代都不是唯一的，因此必须对迭代过程加以条件限制。在m进制无记忆离散对称信道中，如果信道转移概率p(x)=(*) *1/ (

5、土)= Z)否则由式和式求出O j+1 (如3 j,1 (X)，然后进行下一次迭代。三、FPGA实现及调试1.FPGA实现电路该算法的FPGA实现电路如图1所示。其中，Syndrome模块主要完成伴随式的计算,Dj和Di模块分别完成dj和dj/di的计算,Iterator 模块则完成迭代的更新及计算，Sj和Oj分别为需要求出的b仲)和3 0。当同步信号SYN到来时, 所有模块完成初始化，di、Sj和Oj初始化为1。Syndrome模块求出伴随式Spoly后串行输出，同时 将此刻的迭代次数Ite_Num输出，而且当迭代达到要求的次数时，输出一个CLR信号，在Dj模块接 收到此信号后，将dj置为0

6、,于是后面的输出不再改变，直到下一同步信号SYN到来；Dj模块用一组 移位寄存器将伴随式的当前状态和之前的t个状态缓存,和当前Sj 一起可以求出dj,当dj不为0时，同时计算输出到J_rank中；为了让下一步的计算更间单，Di模块中计算直接dj/di和rank=j-i的值，di的逆元用一个查找表来完成，同时预设. =0,当该值小于 J_rank时，将此时的存储值作相应的更新，同时输出一个fresh信号以标明这种更新；Iterater模 块在收到fresh信号后进行相应的更新。在设计过程中，可以将(4)式和(5)式中求满足i-最大的过程谷略，不用拖索前面的每一 行.这里因为,幔定匪代到J时，满足

7、i-俨行。最 大的伉为k,则显然.对于任意iwj - 1.k-护/(x) 方-胪寸&).旦&不为。.故时于下一步送代如果 可二0,取任、否则.取i为混足卜喝(。和j- Wh)之间的较大者即叫 这样不仅可以提高电路 的性能村速度，而且也诃以节省存储空间白一个完整的RS译码原理框图如图2所示。其中，伴随式计算电路由输入的码组计算出相应的伴随 式，同时将结果送到下一模块中，该模块即为实现BM迭代算法的电路。伴随式经BM迭代后，计算出 错误位置多项式b (x),同时也计算出3 (x)。Chien搜索电路则由给定的b (x)找出错误位置，然后 控制门打开或者关闭，当该位置有错时，门打开，输出该位置上的错

8、误值，当该位置没有错时，门关 闭，此时错误值为0。利用b (x)和3 (x)可以进行错误值的计算。因为整个译码过程中存在延迟，为 使相应的数据互相对齐而必须加入一个移位存储器。2.电路调试经过软件仿真和硬件电路仿真后，就需要将编译后的程序下载到实际的FPGA芯片中调试，以验 证实际电路的正确性和可靠性，这是电路设计中的一个重要步骤。软件仿真主要是产生正确的数据源 以验证硬件电路仿真的结果，软件仿真主要采用的是Matlab6.1。Matlab是Mathworks公司推出的一 套仿真软件，其数学运算功能非常强大，是工程中一种非常理想的仿真工具，在调试过程中主要是提 供调试数据、结果数据，包括中间结

9、果。硬件电路仿真是用电路设计软件完成电路设计，我们使用的 是ALTERA公司的Quartus2.0软件，再进行编译、仿真，仿真的结果要与上面Matlab的仿真结果一致。当上面的验证完成后，就可将编译后的程序下载到实际的FPGA芯片中调试，然后用逻辑分析仪 随机抓取数据，保存到文件中，并与Matlab仿真的结果进行比较，如果不正确，则对电路中的每一 模块进行查错、修改，直到用逻辑分析仪随机抓取数据完全正确为止，此时可认为电路调试完成。 Quartus2.0电路仿真结果如图3。图3的仿真图给出了在GF(256)内用Quartus2.0进行BM迭代算法的电路仿真结果，为了进行详细 对比，我们将每一次

10、迭代结果都保留下来。经比较，该结果和Matlab仿真的结果完全一致。四、结语本文的FPGA实现是用Verilog硬件描述语言编写，并在Altera公司QuartusII电路仿真环境下 仿真、选用该公司APEX TM EP20K600EBC6521XES系列芯片来完成的，结合别的FEC模块，将其应 用于数字高清晰度电视(HDTV )接收机机顶盒的设计中，经过性能测试，达到了系统指标要求。而且由 于该设计是用Verilog硬件描述语言编写调试的，因此，可移植性较强。在调试通过后，将该模块植 入基于Xilinx的Virtex2系列芯片设计的电路中同样能满足系统要求。因此，该设计不仅可以和别的 FEC技术结合，提供强大的纠错能力，同时，也可以专门应用于ASIC设计中。与此同时，我们也用 FPGA实现了基于欧式算法的RS译码器，但比较而言，BM迭代算法较为简单，易于实现，且比欧式算 法能节省一半左右的资源。参考文献王新梅，肖国镇.纠错码M.西安：西安电子科技大学出