RS的BM迭代译码算法

2024年2月15日发(作者：爱情的诗)

BM迭代译码算法的基本原理

时域上的RS译码的关键在于求解错误位置多项式,1966年伯利坎普（Berlekamp）提出了可以由伴随式计算错误位置多项式的迭代译码算法，这极大地加快了求解错误位置多项式的速度，该方法简单且易于实现，从而从工程上解决了RS译码的问题；1969年梅西（Masy）指出了该算法与序列的最短线形移位寄存器综合之间的关系，并进行了简化，因此，此译码算法就称为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实现及调试

实现电路

该算法的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仿真的结果完全一致。