基于BM迭代的高速BCH译码方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于BM迭代的高速BCH译码方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：该文以bch(67，53)为例，提出了一种改进的，适合在FPGA上实现的BCH译码算法，并用Xilinx公司Virtext2pro器件实现了BCH(67，53)码的译码。该算法基于bm迭代，与传统的BCH译码算法相比，具有硬件实现简单，运算速度快，消耗资源少等优势。经仿真验证，对于码组中任意小于等于两比特的随机错误都可以给予纠正，且运行可靠。目前，该BCH译码器已成功地应用在DVB-T（数字地面电视）系统中。

关键词：BCH码；BM迭代；现场可编程逻辑阵列；电子设计辅助技术；查表法

中图分类号：TP301.6 文献标识码：A文章编号：1009-3044(2007)04-11019-02

1 引言

BCH码（博斯・乔赫里-霍克文黑姆码）是一种重要的，能够纠正多个随机错误的循环码。是迄今为止所发现的一类很好的线性纠错码。它的纠错能力很强，尤其在短和中等码长下，其性能很接近于理论值，并且构造方便，编码简单。因此非常适用于数据通讯领域。它能够很好的纠正信道传输中的随机突发错误。同时，随着EDA技术的发展，在各种硬件描述语言和EDA工具的帮助下，在软件环境中就能完成硬件电路的设计、仿真、验证、综合，使得硬件设计变得更为简单与直观。这也为BCH译码的硬件实现提供了良好的环境。

该文基于现场可编程逻辑阵列（FPGA）平台，对BCH（67，53）码进行了译码，采用了二进制无逆的BM迭代算法，并且对算法进行了改进。传统的BCH译码一般会采用迭代或者查表两种方法。迭代法的优势在于其使用的硬件资源较少，且当码字较长时，仍有较好的表现。但是其设计的复杂程度较高，而且因为需要迭代，所以运算速度不快。而传统的查表法具有速度快的优势，可是其一般只用于码字短误码少的情况，当码字长误码多的时候，用于建立错误图样表的RAM资源也相当惊人。

该文提出的改进的迭代算法，不仅秉承了迭代算法消耗资源少的优势，而且与查表法的运算速度相当，实现也更为简单。

2 BCH码的结构

BCH码是循环码的一个子类，因此可以用生成多项式来定义。对于BCH（67，53）码来说，它是BCH(127,113)码的缩短码，可以纠正小于等于2比特的所有错。其生成多项式为

g(x)=x14+x9+x8+x6+x5+x4+x2+x1+x （1）

在编码之前，在67比特信息位之前插入60比特0。编码完成之后，这些0会被删除。

3 译码的原理与常用的方法

BCH码的译码可分为频域和时域译码两类。时域译码方法使用较为广泛。

时域译码方法主要分为以下三个步骤：

（1）根据接收码字计算伴随式S；

（2）根据伴随式S计算错误图样E；

（3）将接受码字R与错误图样E作异或运算，得到纠错后的码字U’。

图1 BCH译码器示意图

而在时域译码中较为常用的有两种方法：迭代法和查表法。其主要区别在于第二步：错误图样E的计算。

3.1 查表法

查表法实际上就是根据伴随式S与错误图样E的对应关系，建立起S与E的查找表。S是一个14比特的二进制数（由保护位的位数决定，BCH（127，113）码的保护位有14比特），E是个67比特的二进制数，当第k比特有错时，E[k]=0，否则E[k]=1，k=0，1，…66。例如，第0比特和第5比特发生错误的错误图样：

S与E的关系式如下：

S=E×HT（2）

HT称之为纠错矩阵，由生成多项式g(x)唯一决定。当错误位数在码的纠错范围内时，S与E是一一对应的。

查表法的优点在于速度快，而且硬件实现比较容易，只要用一块ROM建立错误图样表，S作为ROM的地址，E作为ROM的值。可是当错误位数较多时，其缺点也是很明显的：将消耗大量的硬件资源。BCH(67，53)码可纠小于等于2比特的错误，这就意味着，错误图样的总和应该是C+C=2211个，图样的位宽是67比特，即便不考虑地址的冗余（因为S的值不是连续的， ROM会有多余的地址，这些地址无效，仍然会占用ROM空间），也至少需要67×2211≈148k比特的ROM，这对于ASIC是可以接受的，可是对于一个FPGA系统就显得非常庞大了。

3.2 迭代法：

迭代法的步骤如下：[1]

（1）采用 BM 迭代算法决定错误位置多项式和错误值多项式；

（2）用钱搜索的方法找出错误位置多项式的根，错误位置多项式根的倒数就是错误位置；

（3）采用 Forney 算法计算出错误值；

迭代法的优势在于其使用的硬件资源相对较少，对错误位数不敏感，当错误位数较多时，其使用的硬件资源与少位数错误相差无几。而其劣势在于，运算的速度较慢。速度与纠错位数成线性关系，当错误位数较多时，迭代次数也会相应增多。而且其硬件的设计复杂度也比较高，而硬件的ASIC实现希望硬件结构简单，有规律，所以结构过于复杂的话，对于模块的ASIC实现也是相当不利的。

而以下提出的算法，针对BCH（67，53）码特有的特点，对BM迭代进行了改进，在提高运算速度的同时，也大大降低了结构的复杂度。

4 RS译码的迭代算法

RS译码全都是基于有限域理论，以下所有的运算，包括乘法、乘方、加法运算也全都是有限域运算。关于有限域的运算可参考文献[1]。

4.1 伴随式S的计算

假设接收到的码子多项式为r(x)= r0x0+r1x1+…+rn-1xn-1，ai+1（i=0,1…2t-1）为码字空间的根。在此要特别指出，ai+1的指定不是随意的，他与生成多项式有关，生成多项式由数字地面电视（DVB-T）的协议[6]规定。BCH（67，53）的生成多项式见式（1），码字空间的连续根为[a1，a2，a3，a4]，a0不是根。定义伴随式Si（i=0,1…2t-1）为：

因为ai+1是码字空间的根，所以如果没有错误发生，那么所有Si应该都等于0。当错误发生在第k比特时，rk=ck+σ当错误发生在多个比特时，例如n0，n1，…以此类推，

确定nk和σ 的值，即确定错误多项式和错误值多项式，就是以下要做的工作。

4.2 错误图样E的计算

因为在BCH（67，53）码是二进制的BCH码，所以错误值多项式是不必计算的。此处的错误图样E指的就是错误位置多项式的函数。以下BM迭代的方法就是用来确定错误位置多项式。

4.2.1 BM迭代

1966年，伯利坎普（Berlekamp）提出了迭代译码算法[7]。大大节省了计算量，加快了译码速度，从实际上解决了BCH 码的译码问题。1969年，梅西（Massey） 指出迭代译码算法与序列的最短线性移位寄存器综合之间的关系对该算法进行了简化[8]。 因此一般把这种译码算法称为BM迭代译码算法。

普通的BM迭代需要求逆的运算，关于有限域的求逆运算可见参考文献[2][3]。在硬件中求逆，也就是除法运算，是比较麻烦的，因此应该尽量避免。以下提出的无逆的BM迭代方法[9]就避免了这种运算。

二进制无逆的BM迭代算法：

对于BCH（67，53）而言，t=2，所以只需迭代2次。i=0时，d(0)=s0，当错误总数小于等于2比特而且不等于0时，s0=rn0・(a1)n0+rn1・(a1)n1,(n0≠n1)，不可能等于0，即d(0)不等于0，所以?子(0)(x),?啄(0),D(0)都为定值，所以σ(1)也可以被确定。经计算，错误位置多项式为：

由此，复杂的迭代过程被简化为一个代数表达式，而且不必计算所有si。式中s1=s 是根据s的定义。

4.2.2 用钱搜索的方法求错误位置

错误位置多项式根的倒数就是错误位置。钱搜索其实就是用所有的可能根带入错误位置多项式来试验可能根是否为根。设错误位置多项式为：

4.2.3 用foney方法求错误值

因为BCH（67，53）为二进制码，所以无需求错误值，只要在错误位置取反就可以纠错。

5 算法的实现

5.1 伴随式S的实现

由式（3），Si=rj・(ai+1)j，如果要一拍实现这一等式，每个Si需要66个乘法器和66个加法器，那么2t个Si所需的资源看似是非常庞大的。可是实际上，由式（6），只需计算2个Si，而且因为ri是二进制序列，实际使用的是与门，所以实际使用的资源只是132个与门和132个异或门。而之所以要一拍完成运算的目的，其出发点还是流水线的考虑。影响流水线速度的是运算最慢的模块。

伴随式的实现电路如下：

图3 伴随式实现电路

上图中ri表示接收序列。(ai+1)j为定值。图中的乘法器是与门，加法器是异或门。

5.2 错误图样E

5.2.1 BM 迭代的电路实现

BM迭代式见式（6），实现这一代数式需要1个乘方器，1个乘法器，1个加法器。此处要注意，所有的运算都是有限域运算。

5.2.2 钱搜索的电路实现

钱搜索与伴随式有相似的代数结构，因此也可以用类似图（3）的结构实现。在初始化(reset)时，在寄存器D中写入σ(x)的系数。

6 仿真结果

该文选用Xilinx公司的Virtex2pro作为测试芯片。测试的原理图如图4。首先利用modelsim SE 6.1b进行逻辑功能仿真，穷举所有小于等于2比特的错误图样，把原始数据序列加上不同错误图样送入，由输出的波形可看到已译码正确。然后用synplify pro8.5综合软件进行综合，综合结果显示，该译码器总共147个寄存器和473个逻辑功能单元。本设计可以在118M的时钟下运行。

7 结论

经软件验证和FPGA平台验证，该文的设计方法对DVB-T系统中使用的BCH（67，53）码的译码，取得了令人满意的结果。与一般的迭代法相比，其优势非常明显，不仅硬件结构异常简单，而且运算速度也高于普通迭代法，普通的迭代法需要2t=4拍，而该方法仅需要1拍；而与传统的查表法相比，其资源上的优势更是非常明显，求错误图样时，传统的查表方法需要148k比特的RAM，而本方法只需一个有限域乘法器，一个有限域乘方器，一个有限域加法器就可以实现，这些都是简单的组合逻辑。因此，本设计不仅简单易用，而且使用了较少的硬件资源，达到了较高的运算速度，很好的实现了资源与速度的平衡。

图4 测试原理图

参考文献：

[1]王新梅，肖国镇.纠错码[M].西安电子科技大学出版社，1991.

[2]PAAR C, ROSNER M. ‘Comparison of arithmetic architectures for Reed-Solomon decoders in reconfigurable hardware’[A]. Fifth Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '97)[C]. Napa Valley, California, USA,April, 1997.

[3]H. Brunner, A. Curiger, M. Hofstetter.‘On computing multiplicative inverses in GF(2m)’[J].IEEE Trans. on Comput., 1989.

[4]夏宇闻.verilog数字系统设计教程[M].北京航空航天大学出版社，2003.

[5]樊昌信，张甫翊，徐炳祥，吴成柯.通信原理[M].国防工业出版社，2003.

[6]ETSI EN 300 744，’Digital Video Broadcasting (DVB);Framing structure, channel coding and modulation for digital terrestrial television’[S] , 2004（11）.

[7]BERLEKAMP, E.R.: ‘Algebraic coding theory’ [M] (McGraw-Hill, New york,1968).

[8]JAMES L. MASSEY，’Shift-Register Synthesis and BCH Decoding’[J] .IEEE TRANSACTIONS, January 1969.

[9]I.S. Reed, M.T，Shih,T.K，Truong，’VLSI design of inverse-free Berlekamp-Massey algorithm’[J].IEEEPROCEEDINGS, SEPTEMBER，1991.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。