RS译码BM算法及IBM算法

1966年，Berlekamp利用迭代算法译BCH码，避免了矩阵的逆计算，从而大大加快了译码速度。1969年，J.L.Massey从序列综合的角度重新推导了该算法，给出了迭代译码算法与序列的最短移位寄存器综合之间的关系。我们称这一算法为Berlekamp-Massey算法(BM算法)。

在介绍RS码的BM算法之前，我们需要介绍一下RS码的伴随式译码算法： 设 发送码字多项式为C(x)?cN?1xN?1?...?c1x?c0，

ll错误个数为t的错误图样多项式为E(x)?etxt?...?e1x1， 其中xi称为错误位置数，该位置的错误值是ei。 接收序列多项式R(x)?C(x)?E(x)?rN?1x则伴随式Sj?R(?m0?j?1N?1l?...?r1x?r0

)?E(?m0?j?1)j?1,2,...,D?1

?et(?t)lm0?j?1?...?e1(?l1)m0?j?1

l伴随式仅取决于传输过程中发生的错误图样，而与编码数据无关。令?i?Xi (i=1,2,..,t) 则Sj?etXtm0?j?1?...?e1X1m0?j?1j?1,2,...,D?1

我们希望从这D-1个方程求出2t(?D?1)个未知数ei、Xi (i?1,2,...,t) 定义错误位置多项式

?(x)??(1?xXi)?1??1x??2x2?...??txt

i?1t则由?(Xi)?0 (i?1,2,...,t)，可以得到

?11??1Xi?1??2Xi?2?...??iXi?t?0

上式两端同乘以eiXim0?j?1?t，我们有

eiXim0?j?1?t??1eiXim0?j?1?t?1??2eiXim0?j?1?t?2?...??teiXim0?j?1?0

上式对i=1,2,...,t求和得到

?e(Xii?1tm0?j?1?ti??1Xim0?j?1?t?1??2Xim0?j?1?t?2?...??iXim0?j?1)?0

即Sj?t??1Sj?t?1??2Sj?t?2?...??tSj?0 由上式可以得到如下递推关系

Sj??(?1Sj?1??2Sj?2?...??tSj?t)j?t?1,...,D?1

此关系式可以用线性反馈移位寄存器表示，如下图2.4

RS码的译码问题变成：已知D ?1个伴随式，设计一个具有最小度数连接多项式

?(x)?1??1x???2x2?...??txt的线性反馈移位寄存器（即最短线性反馈移位寄存器），

产生这个伴随式序列。

Berlekamp和Massey提出的错误位置多项式求解算法如下[1]：

设线性反馈移位寄存器(Lr,?(x))是生成序列S1、S2、...、Sr的一个最短线性反馈移位寄存器，其中Lr是线性反馈移位寄存器的长度。假定已经构造了一系列的最短线性反馈移位寄存器(L1,?(x))、(L2,?(x))、....、(Lr?1,?最短线性反馈移位寄存器(Lr,?(x))。

BM算法：

(r)(1)(2)(r?1)(r)(x)),则可以用BM算法构造新的

...、SD?1，?(x)?1 B初始条件：已知伴随式S1、S2、(0)(0)(x)?1 ?(0)(x)?1 A(0)?0

可以由如下的递推关系经过D-1次迭代求出?L(r?1)(D?1)(x)：

?r?其中

??j?0(r?1)jSr?i (1.2)

?(r)(x)??(r?1)(x)??rxB(r?1)(x), ?(r)(x)??(r?1)(x)??rxA(r?1)(x)

如果?r?0且2Lr?1?r?1，则

Lr?Lr?1,B(r)(x)?xB(r?1)(x),A(r)(x)?xA(r?1)(x)

否则，

1(r?1)1(r?1)Lr?r?Lr?1,B(r)(x)???(x),A(r)(x)???(x) r?r?这样，第r次迭代得到的最短兴县反馈移位寄存器(Lr,?(x))满足：

(r)Lr?max(Lr?1,r?Lr?1),Lr??r/2?，且S(x)?(r)(x)??(r)(x)modxr;

迭代结束时，得到的?(D?1)(x)是满足下面性质的最小度数多项式：

A(D?1)0?1,??(iD?1)Sr?i?0 (r?LD?1?1,...,D-1;LD-1??(D?1)/2?)，且

i?0LD?1S(x)?(D?1)(x)??(D?1)(x) modxD?1。即?(D?1)(x)是我们要求的错误位置多项式，?(D?1)(x)是相应的错误值多项式。

IBM算法[2]

改进的无逆的BM算法(imversionless B M)，其解码的频率较传统的BM算法有大幅度的提高。RS时域解码算法中，关键方程的求解是整个解码过程的关键，其决定了解码器工作的时钟周期。通常的BM算法求解周期过长，解码数据量较低。而IBM算法极大的缩短了关键方程的求解周期，常见的IBM算法分为四个步骤：1.由接收的码字R(x)计算伴随式S(x);2.根据关键方程计算错误值多项式w(a)和错误位置多项式?(x)；3.钱搜索找到错误位置，并计算错误值；4.纠正错误。

IBM算法的具体流程如下：

初始化：?0?b0?1,b?1?0,k(0)?0,r(0)?1

?i(0)?bi(0)?0fori?1,2,...t

r(x)为接收到的码字多项式，?为错误位置多项式系数，b是辅助计算的中间式， k代表迭代计算的次数

输入：si,i?1,2,...,2t?1 ，其中si为伴随式 for r = 0 step 1 until 2t-1 do Begin:

Step iBM.1 ?(r)?sr?0(r)?sr?1?1(r)?...?sr?t?t(r) Step iBM.2?i(r?1)??(r)?i(r)??(r)bi?1(r) Step iBM.3if?(r)!?0andk(r)?0

bi(r?1)??i(r) ?(r?1)?r(r)

k(r?1)?k(r)?1 其中，?(r)为错误位置多项式，?(k)是辅助计算的中间量

for i ?0 ,step 1 until t-1 do

Step iBM.4 ?i(2t)?si?0(2t)?si?1?1(2t)?...?s0?t(2t) 输出：

?i(2t) i?0,1,...,t,

?i(2t) i?0,1,...,t-1; 输出为错误位置，和该位置的错误值。

参考文献：

[1] RS编译码器的设计与FPGA实现 国防科技大学 李宏

[2] 高速并行的RS解码器设计与FPGA实现 中科院上海技术物理研究所 赵明等

[3] 高速Berlekamp．Massey算法结构及电路实现 东南大学 张军，王志功，胡庆生，肖结等

本文来源：https://www.bwwdw.com/article/1cnt.html