资源描述：
《基于vc的bch码迭代译码算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第19卷第5期哈尔滨师范大学自然科学学报NATURALSCIENCESJOURNALOFHARBINNORMALUNIVERSITYVol.19,No.52003基于VC的BCH码迭代译码算法实现王建华郑坤张军(哈尔滨师范大学)【摘要】在现代通信系统中,纠错码技术是实现可靠通信的基本方法1本文首先对纠错码技术做一下简介,然后以(63,39)码为例,着重讨论用VC++610对BCH码迭代译码的进行实现1关键词:BCH码;域为素数幂),则共有qk个码字1n长的数组共有qk组,在二进制的情况下,有2n个数组1显然,qk个n维数组(n重)组成一个GF(q)(
2、表示阶为q的有限域)上的n维线性空间,如果qk个码字集合构成了一个k维线性子空间,则称它是一个(n,k)线性分组码1循环码:它是最重要的一类线性码,我们本文所要讨论的BCH码正是循环码1根据代数理论,一个循环码是模(xn-1)多项式剩余类线性结合代数中的一个理想1反之,一个理想对应一个循环码1从理想的定义可知,在理想中至少可以找到一个次数最低的非零首一多项式g(x),有它的一切倍式能够生成一个理想(循环码)1这个多项式g(x)称为循环码的生成多项式1BCH码是一种很好的线性循环码,在中、长码长中具有很好的纠错能力1其译码方法也有多种,其中迭代算法因其
3、译码速度快而最常用1本文用最流行的开发工具VisualC++,以软件的方法实现迭代译码算法,可供教学、科研、工业生产领域之用1纠错码简介111纠错码的基本概念·线性分组码与循环码在纠错码中最常用的就是线性分组码,它是讨论各种码的基础1分组码:信源输出的信息序列,以k个码元划分为一段,通过编码器把这段k个信息元按一定规则产生r个校验元,输出长为n=k+r的一个码组1因此分组码用(n,k)表示,n表示码长,k表示信息位1如果我们把每一个码字看成是一个n维数组或n维线性空间中的一个矢量,则可以从线性空间的角度,比较深入地谈论线性分组码1线性分组码:一个(n
4、,k)线性分组码,是把信息化成k个码元为一段(称为信息组),通过编码器变成长为n个码元的一组,作为(n,k)线性分组码的一个码字1若每个码元的取值有q种(q1BCH码及其迭代译码算法BCH码是迄今为止所发现的一类很好的线性纠错码,于1959年由Hocquenghem,1960年由Bose和Ray-Chaudhuri分别提出(BCH是三位科学家的名字的缩写)1它的纠错能力很强,而且有严格的代数结构,因此在编码理论中起重要作用.·BCH码的描述BCH码是可以纠正多个随即错误的循环码,可以用生成多项式g(x)的根来描述,根集合中含2收稿日期:2003-09
5、-14有δ个连续根1BCH码的生成多项式为:g(x)=LCM(m0(x),m1(x),m2(x),(x))余式r(x),然后将r(x)“后接”到M(x)的尾部,得到码字C(x).即C(x)=M(x)+r(x).假设输入信息:M(x)=m38x38+m37x37++m1x+m0;生成多项式:,mδ一个码的纠错能力,完全由它的最小汉明距离dm决定,而BCH码的dm则完全由g(x)的根决定1在实际中应用的最多的是码元取自GF(2)中的二进制BCH码1它有如下性质:对任何正整数m和t,一定存在一个二进制BCH码,它以α1,g(x)=g24x24+g23x23
6、++g1x+g0;余式:r(x)=r23x23+r22x22++r1x+r0生成的码字:C(x)=m38x38+m37x37++m1x+m0+r23x23+r22x22++r1x+r0.α3,,α2t-1为根,其码长n=2m-1,能纠正t个因此BCH码的编码问题就是以g(x)为模的随即错误,校验位数目至多mt个1就(63,39)码而言,它的码长为63=26-1,其中dm为9,可纠正4个随机错误,因此它的校验元共24个1而它的生成多项式就是以α1,α3,α5,α7的根最小多项式的乘积1除法问题112译码3相对于编码而言,BCH码译码问题一直是编码理论研
7、究中最感兴趣的问题之一1一个码是否能在实际中应用,往往取决于译码器是否简单、快速、经济和译码错误概率小1BCH码在短和中等(63,39)码的编码和译码实现首先,为了便于计算机快速的计算有限域多项式乘法,在程序中首先建立一张表,来建立GF(26)上所有元素同以模x6+x+1的所有剩余类多项式之间的对应关系1由于GF(26)上的所有非零元素对乘法满足阿贝尔群,所以计算多项式乘法只需要查表找到对应多项式的元素,然后根据元素的乘积找到对应的多项式,即完成乘法计算1在GF(26)上有非零元素26-1个,同x6-1的所有剩余类多项式一一对应1比如当要计算两个多项
8、式x3+x同x5+x3+x的乘积时,我们只需要查表得到其对应的元素分别为α13和α53,其乘积为元素α66=
