第五章BCH码和RS码-2-2011

15.4.3确定错误位置-钱氏搜索法012211RxRxRxRxRnnnn012211ExExExExEnnnntltllxYxYxYxE2121tttxxxxXxXxXx221211111错误位置多项式xklkX称为错误位置数，它表示在R中的第几项发生了错误。其中：ilk说明第n-i项有错.,1?,11的根是否为就是检查即上是否有错中的第一项译码器要检查xnlxRxRklknn..,,,.,,43222中哪位有错就能判断的根是否为依次检查的根是否为即检查上是否有错中的第二项检查同理RxxxRxRnnn2钱氏错误位置搜索电路t个寄存器分别送入，用时钟脉冲分别激励各乘法器一次，得到乘积；将乘积送回寄存器，再将各寄存器输出求和，R（x）的最高阶正好移到缓冲器末端；仅当和为-1时，求和电路A输出将控制门打开，Rn-1和Yn-1相减进行纠错，下一个时钟脉冲将已纠正的码字送出；对于二元BCH码，门电路可以省略，求和电路输出直接和缓存器输出相加进行纠错。门缓冲器………输入输出t212t1titti1nYA35.4.4计算错误值对于二元码，错误值为1，只要知道错误位置就可确定错误值；对于q元码，错误值是GF（q）中的非0元，在求出错误位置后，还要计算错误值。41.TTHRStjRSjj2,2,1,2.由S求EtkjkktkjlktkljkjjXYYYESkk111klkX称为错误位置数，它表示在R中的第几项发生了错误。其中：kY错误值ilk说明第n-i项有错3.引入中间函数错误位置多项式x所以求E即为由S求的根x1kX第几位有错klkklXXk1ttttttttttXYXYXYSXYXYXYSXYXYXYS2222211222222112221115若实际错误数te11,1001其中eiiieiixxXx定义函数：21xXxxkk0,,11xxXXxkkk的根是时注意当1,1010,1keiikiekiiikxxXx其中31xxXxxXxxkkkkkxXxXxXxXxXxXxekkjk11111111216将(3)式展开:keekkkkkeekkkkkeiikieiikieeXxXxxXxxxXxxxxx12101)1(2210101102211比较系数得到:41~12101112201100eiXiXiXikikkiikkkkkkk510eiiekiS设tkjkkjXYS1ejiejjieXYS17ejjkejjejeiijkiejjeiejiejjkieiiekiXXYXXYXYS111101011061,1010,1keiikiekiiikxxXx其中:,1的性质可知由时当xXxkj0,0,,1xkjxXxkjkkk时时即时7:,61010110eiiekkikeiikkiekkkkekkeiiekiXYXXYXXYSkj即项存在式只有871010110eiiekkikeiikkiekkkkekkeiiekiXYXXYXXYS1011eiiekhieiiekikXSYtltllxYxYxYxE21214.5.xExRxCP118例5.4设上的(7,3)RS码的接收字为求发送码矢。3(2)GF432()Rxaxax91．提高m(x)的次数，即xmxkn2.xrmod运算求xgxmxxrknxrxmxxCkn3.例题5.5系统RS码的编码一般（n,k）RS码的编码电路见图5.2.2105.6.1MS多项式的定义定义:定理:上的多项式为设mGFxa2minnnnGFaaxaxaxaxa2012211minnnnGFbbxbxbxbxb2012211若1,niiab且.多项式的是则称MSxaxbiiiibaabMSxaxb则即多项式的是若,阶元素中的是nGFm25.6非系统RS码的编码和译码11定理:mikkkkmmnmGFmmxmxmxmxmkGFxmnGF2,,12,12,12012211阶多项式上的为的本原元为设.,,,,22码的码多项式生成的根的最低次多项式为是以则多项式的是若RSxgxCMSxmxCt;2;1的倍式是为生成多项式所生成xgxC证明:多项式的是若MSxmxCiniiiiCCmmC,11221100,,knknnCmCmCmCm000111CmCmCmnknkknk为根以所以knxC,,,2即C(x)一定是包含g(x)的因式,所以C(x)是码多项式.5.6非系统RS码的编码12已知m(x),g(x),求C(x).例题编码问题13工作过程：将待编码m(x)的个各系数依次存入k-1个寄存器中，完成第一次运算后输出得到C0，完成第二次运算后输出得到C1，同理，完成第n-1次运算输出得到Cn-1。编码电路012121kk-1输出14012211:RxRxRxRxRnnnn已知(1)求R(x)的MS多项式S(x)012211SxSxSxSxSnnnnnnknknknknRSRSRSRSRS11221xexCxR012211exexexexennnn多项式的为设MSxexE01121111111ExExExEexexexexEnnnnnnnniieE5.6非系统RS码的译码15xexCxR接收多项式02knCCCnnnnnknkknknknknknknknEmeCRSSEmeCRSERSEeCRSEeCRS001111112222211nnknknkknknkESmESmESm022211116(2)即上发生在个错误设有,,,,,21tlllttltllxYxYxYxe2121:多项式的MSxetkkkntkknkkknkntkknkkknkntkkktkkkXYEEXYESXYeESXYeESXYeE10111121222111klkX.,的根其倒数为错误位置多项式x17(3)tttxxxxXxXxXx221211111引入01:221111tktkkkkXXXXX代入:,得到两边同乘以ikkXY02211tikktikkikkikkXYXYXYXYtkjkkjXYStk1,,,,2,1同时考虑求和令011122111tktktikkttkikktkikkikkXYXYXYXY:,2~,1得到令tti0001212222111ttttttttttSSSSSSSSSt~1用迭代法求出18:,~,12得到令ntintntnnttttttttttEEEEEEEEEEEE2111222121221212112000可解出可解出可解出(4)最后求出nnnknknkknknkESmESmESm111111求出m(x)P128例5.619BCH码在信息传输中的应用可视音频编码ITU-TH.261n×384Kb/s：（511，493）本原BCH码，m=9，t=2，dmin=5移动通信例如CCIR建议584所推荐的国际无线寻呼标准码采用（32，21）扩展BCH，它是由本原BCH码（31，21）加一位偶校验得到的。m=5，t=2，dmin=6日本数字蜂窝通信系统PDC采用本原（15，11）BCH码，缩短（12，8）及（14，10）BCH码，m=9，t=2，dmin=320RS码的应用领域：储存器件：磁带，CD，DVD，条形码等无线移动通信卫星通信数字电视或数码视频广播高速调制解调器：ADSL，XDSL等21在删除信道下，当码元做删除处理时，它在接收端的位置是确定的，只是不知道错误值；距离为d=2t+e+1的线性分组码，能纠正t个错误同时纠正e个删除，若全用来纠删则可以纠正d-1个删除；设接收码字中有≤v个差错和≤e个删除，则只要2v+e≤d-1，该码可以纠正v和e的任意组合。5.7BCH码的纠删/纠错译码225.8域元素的计算电路及其应用5.8.1加法运算012211aaaammmmi012211bbbbmmmmj0011222111babababammmmmmji1,,2,1,02,miGFbaii其中，23域上两个元素的加法电路加脉冲与0a0b0与1a1b1与2a2b2与3a3b3寄存器A寄存器B42GF245.8.2乘法运算普通基：在上基底为的自然基。普通基比特串行乘法电路有以下四种：（1）域上任意元素乘以固定元素和除以固定元素的电路；（2）域上任意两元素相乘的第一种乘法电路；（3）域上任意两元素相乘的第二种乘法电路；（4）域上任一元素与固定元素的乘法器电路。2mGF(,,,,)mm12125（1）域上任意元素乘以固定元素固定元素的电路；2mGFP0=1P1=1P4=1a0a1a2a3图5.8.2任意元素A乘的电路是由低位向高位移位并按本原多项式反馈连接的移存器。26（2）域上任意两元素相乘的第一种乘法电路P0=1P1=1P4=1SR0SR1a0a1SR2a2SR3a3b2b1b0b3移存器B寄存器A移存器C（乘α累加器）3210CABbAbAbAbA323210Aaaaa323210Bbbbb27（3）域上任意两元素