基于BM算法的BCH码的译码硬件实现

摘要：BCH码是一种理论上比较成熟的代数码型，在电力通信系统，GSM标准的语音和数据业务，以及卫星通信和数字广播通信(DVB-S2)等多个领域均有着广泛的应用。基于幂次运算，在线性反馈移位寄存器(LFSR)下实现了基于Berlekamp—Massey(BM)时域迭代译码算法的整个译码器构架，以及BM简化算法的硬件设计。通过计算机模拟仿真表明，两种算法的译码速率分别可达到32 Mbps，37Mbps。
关键词：BM迭代简化算法；FPGA；译码器构架

O 引言
    BCH码是1959年由Hocquenghem，1960年由Bose和Chandhari分别独立提出的一种能纠正多个随机错误的循环码，该码有严格的代数结构，具有纠错能力可控，在中短码长情况下性能接近理论最佳值等优点，并且构造方便，编码简单，是实际使用最广泛的码型之一。
    1960年Peterson从理论上解决了二进制BCH码的译码算法，奠定了BCH码译玛的理论基础。随后，Gorensten和Zierler把它推广到高阶有限域中。1966年Berlekamp提出了迭代译码算法，Maxsey从线性反馈寄存器的角度对该算法进行描述，不仅使算法硬件实现成为可能，也大大提高了译码速度，从实际上解决了BCH码的译码问题。鉴于FP—GA具有较大块RAM，本文以(15，5)BCH码为例说明如何将BM迭代算法，以及后面的chien搜索都建立在有限域上进行运算，用域元素的幂次运算代替原来的乘和除操作，从而节约了逻辑单元(slice)资源。文献已经给出了普通BM译码算法的流程图，本文根据二元BCH码的特点给出了简化的BM算法流程图。

1 BM算法介绍
1．1 有限域知识介绍
    BCH码是在有限域中进行运算的，详细的有限域知识参考文献。
    以本文设计的BCH码为例，p(x)=x4+x1+1是GF(2)上的本原多项式。令α为本原多项式的根，m=4，则由{l，α，α2，α3}中元素的线性组合可表示GF(24)上的所有非零元素{α0，α1，α2，…，α14}，这些非零元素构成一个循环群如表l所示。最后一行是为了运算的需要，人为加上去的，表示“无”这种状态。

1．2 经典BM算法
    普通的译码算法都可分为如下三步：
    (1)由接收码字R(x)计算伴随式S(x)．(用除法电路)
    (2)由伴随式S(x)求差错图样E(x)．(用各种译码方式)
    (3)由差错图样E(x)求得译出码字C(x)．(用关系式C(x)=R(x)一E(x))
    上面的(1)(3)步是固定关系式的运算，相对容易，最关键的是第(2)步。1966年，Berlekamp针对关键方程式S(x)D(x)≡ω(x)(mod x2t+1)的求解(这里的D(x)为错误位置多项式)，提出一种复杂度随纠错数目线性增加的迭代算法，而Massey对Berlekamp算法作为设计自回归滤波器的过程进行了重新的推导，采用反馈移位寄存器来完成关键方程的计算。自此以后这种译码算法被称为BM迭代译码算法，其算法流程图参考文献。

2 二元域下的简化算法
    经典的BM算法流程适合任何有限域的BCH码，对于GF(2)，我们可以证明当r为偶数时，△r为0[2]，此时迭代可以省略。通过对经典BM算法流程图的改进，得到下图l，即GF(2)上的简化BM算法流程图。

    其中，Sn为伴随式，D(x)为错误位置多项式，B(x)为多项式修正项，△代表差值即下一个伴随式与由当前错误位置多项式表示的移位寄存器所产生的值之间的差值，L为移位寄存器的当前长度。

3 硬件设计与实现
3．1 基于幂次的运算方式
    对表1进行简化，得到表2和表3：

    将运算步骤都建立在域元素幂次运算的基础上，流程图中的“*”，“／”，“+”运算方式都会改变。例如：(1110)*(1111)mod(10011，这个为本原多项式)=1011010mod(10011)=0101，转化成幂次后(1110)*(1111)→a12*a11=α23=α8，原来二进制乘除法电路变为简单幂次的指数加法电路。“+”由原来的模二加运算变成两次查表和一次模二加运算，例如，α12+α11→查表二(1l11)+(1110)=000l→查表三0001对应α0，所以得到α12+αll=α0。在硬件实现中，表2，表3的第二列作为内容存在FPGA的ROM中，第一列作为他们的地址。

3．2 整体译码结构设计
    以上是BCH译码器的整体结构模块图，分四个模块，下面介绍这四个模块的功能：
    (1)S_produce：根据接收码字R(r0 r1 r2…r14)，产生伴随式S(s1，s2，s3，s4，s5，s6)；
    (2)dr：根据伴随式S(s1,s2，s3，s4，s5，s6)，产生位置差错式D(dl，d2，d3)；
    (3)chien：以钱搜索的方式，根据位置差错式D(d1，d2，d3)，产生错误图样E(e0，el，e2…e14)；
    (4)shift_register：同步时钟的功能，满足chien产生e14时，r14恰好输出：c14=r14+e14。
    整个结构中，dr这个模块最为复杂，对应整个BM算法。图3是dr模块图。计算的功能，并将计算得到的△r值和前一状态的D(dl，d2，d3)传给T_updata，和B_updata这两个模块；B_updata完成B(x)更新的功能(B(x)<一xB(x)或B(x)<一△-1nd(x))，将值传给T_updata；T_updata完成T(x)更新的功能(T(x)=d(x)一△rxB(x))，并将计算结果反馈给top_dr，作为当前状态的D(dl，d2，d3)；control模块完成控制整个模块的时钟同步。

4 仿真结果
    我们选用了Xilinx公司的xc4v1x60，仿真环境是xilinxISE6．0，moddsim SE 5．5e，在布线后的时序报告中得到的系统可以在70MHz的时钟上对信号进行实时的处理。在时序仿真中我们选用了50MHz的时钟，连续输入两帧数据(每帧数据15bit)，一帧是正确的码字(100010100110l1)，一帧是错误的码字(10001010001111)，普通算法在延迟23个时钟周期后输出结果，简化算法在延迟20个周期后输出结果。根据译码速度计算公式：译码速率=(帧长*系统频率)僻码一帧所需要的时钟周期数，则两种算法的译码速率分别为32Mbps，37Mbps。

5 结论
    在本文中我们利用FPGA实现了基于BM迭代译码算法的BCH码译码器，并根据FPGA块ROM资源充足的的优势，采用基于幂次的运算方式，合理地对．BM流程算法进行模块划分，同时实现了简化的BM算法，缩短了译码延迟，提高了整个译码器的译码速度。计算机仿真结果表明，本设计所实现的BCH译码性能基本满足传输要求，为后续长BCH码的硬件实现作了较好的铺垫。