下载

0下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 一种适用于R—S不等保护码的编译码算法

一种适用于R—S不等保护码的编译码算法.doc

一种适用于R—S不等保护码的编译码算法

问我留言器
2017-11-11 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《一种适用于R—S不等保护码的编译码算法doc》,可适用于高等教育领域

一种适用于RS不等保护码的编译码算法一种适用于RS不等保护码的编译码算法,()ComputerEngineeringandApplications计算机工程与应用一种适用于RS不等保护码的编译码算法毛倩,曾小清,张树京MAOQian,ZENGXiaoqing,ZHANGShujing上海理工大学光学与电子信息工程学院信息与通信工程研究所上海InstituteofInformationCommunication,CollegeofOpticalElectronicInformationEngineeringUniversityofShanghaiforScienceandTechnology,Shanghai,ChinaEmail:maoqianussteducnMAOQtan,ZENGXiaoqing,ZHANGShujingErrorcorrectingcodingalgorithmforRSUEPcodesComputerEngineeringandApplications,,():Abstract:ThispaperstudiedthecodingalgorithmsfortheRSUEPcodesbasedonthealgebraiccharacteristicsofthecodespaceItformedtheunequaldistancesoftheinformationdigitsbyseparatingtheminimumidealwhencodingAndwhendecoding,ifthequantityoftheelrorsinareceivedcodewordwaslessthanorequaltotheminimumerrorprotectioncapability,thegeneraldecodingalgorithmwasused,otherwisethedecodersupposedtheinformationdigitswhoseerrorprotectioncapabilitieswerehJghandverifiedthehypothesisbythecodespaceswhoseerrorprotectioncapabilitieswerelowBythismeansthoseimportantinformationcouldbefoundSimulationshowedthatthisalgorithmwaseffectivefortheRSUEPcode,anditprovidedmoreerrorprotectioncapabilitiesfortheimportantinformationKeywords:errorcorrectingcodeRSUEPcodedecodingalgorithm摘要:以RS不等保护码为研究对象,在分析码空间特性的基础上,着重研究编译码算法编码时,利用分离最小理想的方法构造出信息元距离的不均匀性译码时,如果接收码字中错误码元的数目小于或等于码空间的最低保护能力,则利用一般译码算法译码:否则对高保护等级信息元的值进行假设,并利用低保护等级的子空间验证该假设,用试探法找到满足验证条件的高保护等级信息元的值仿真显示该编译码算法对RS不等保护码是有效的,它可以在不改变编码效率的前提下为高保护等级的信息元提供更好的误码性能关键词:纠错码RS不等保护码译码算法文章编号:()文献标识码:A中图分类号:rIPll概述里德一索罗蒙(ReedSolomon,RS)码是非二进制循环码,它可以有效地使用在具有较大输入码元集的信道上目前常用的RS码几乎都是等保护能力码,即码空间为各信息元提供相等的检错或纠错能力然而在实际应用中,不同信息位上数据的重要性往往不同,人们希望码空间根据信息元重要性的差异为它们提供不同的检错和纠错能力里德一索罗蒙不等保护(ReedSolomonUnequalErrorProtectionRSUEP)码的码空间具有距离不均匀的特性,因此它可以在不改变编码效率的前提下提高特定信息元的保护能力不等保护(UnequalErrorProtection,UEP)码的概念最早由BurtMasnick和JackWolf在世纪年代率先提出,此后又有许多文献在不等保护码的码长界限,码的构造方法以及纠正突发性误码等方面展开研究口对于二进制循环不等保护(CUEP)码,目前已经利用计算机搜索的方法找到了所有码长在以内的CUEP码一,同时利用分离最小理想的方法,还可以构造出CUEP码但是对于RS码的不均匀保护特性则研究较少一种编码算法能否在实际中应用,在很大程度上取决于该算法是否简单有效目前对于RSUEP码尚缺乏有效的编译码算法本文在近世代数以及循环码编译码算法的基础上,提出了一种新的适用于RSUEP码的编译码算法RSUEP码的码空间特性距离特性通常人们对分组码保护能力的描述是借助于码的最小汉明距离d,码的纠错能力为t=L(d一)J(其中LxJ表示不超过的最大整数)当接收码字中错误码元的数目小于或等于t时,整个码字可以被正确译出现在本文讨论UEP码,所关心的是在何种情况下特定信息元能够被正确译出,这时就需要分别描基金项目:国家高技术研究发展计划()(theNationalHishTechResearchandDevelopmentPlanofChinaunderGrantNoAA)作者简介:毛倩(一),女,博士,讲师,主要研究方向为信道编码及无线通信曾小清,女,博士后,同济大学教授张树京,男,博士生导师,同济大学资深教授毛倩,曾小清,张树京:一种适用于RS不等保护码的编译码算法()述每个信息元和其它信息元的分离度,也就是说必须分别度量每个信息元的距离特性在对UEP码距离特性的描述中,分离矢量S是应用较为广泛的一个参数对它的定义如下嗍:设G是特征为P的有限域(P为素数),m=(m,m,,…,m)为信息矢量,其中m,ml,…,mGF(p),则GF(p)上的码空间cI的分离矢量为S=(so,sl,…,s),其中s(,,…,一)为第i个信息元m的分离距离,它等于sf=rain{(ma)~n=(mo,…,),,…,lGF(p),}()其中(c)表示码字c的汉明重量,G为码的生成矩阵利用公式(),可以定量计算出码空间各信息元的距离特性保护能力UEP码的保护能力用保护能力矢量F=,…一,)定义,对于任一信息元m,其保护能力(epeq错能力为fllJi一()当全部相等时,码是等保护能力码,反之Cn就是一个不等保护码假设在传输过程中,码字中发生e个错误,那么如果e小于或者等于码空间的纠错能力t整个码字就可以被正确译出如果e大于t,则不能保证整个码字正确译出,但所有保护能力『:大于或者等于e的信息元都可以被正确译出显然,f=min(fo,…一,)码空间的代数性质把包含个元素的有限域G扩展为一个包含P”„个元素的有限域,称为G的扩域,记为GF(m是任意非零正整数)RS码是非二进制循环码,其码元是扩域G中的元素,并且其码空间CI是多项式剩余类环GXXn的一个主理想,这个主理想可能由G】,一的数个主理想的直和构成由于理想必定是由其中某一元素的倍数构成的,因此一可分解为q个不可约多项式,称为最小多项式叻()啊()在扩域CF上的根为CF的本原根口的幂次形式(这里t表示所有根的幂次的最小值),rnt()在GF上的所有根的集合称为一个共轭类,记为设RS码,C是多项式剩余类环GFxlx”一中个主理想(),(),…,()的直和(这里不可约多项式()(i=,…,)为这些主理想的生成多项式),所有Z(i=,…,)构成的集合记为,,每个主理想对应的子空间的维数为film=,ldeg(())(deg(())表示瓯()的最高次数)则码Cn的生成多项式g()=岛gIg…nk是g个最小多项式的乘积,即g()=H啊()E()其中表示集合V在集合{,,,…,(q一)一}中的补集另外,定义g()所有根的集合为该RS码的完备定义集,即e,…,le}()其中表示集合的补集(模n)RS码的生成多项式确定后,编码方式(即生成矩阵)可以有多种方案,常用的生成矩阵形式如下:G=()文献i~明对于循环码而言,如果生成矩阵G中的任意两行g和岛属于G”一的同一个主理想,则分离矢量s中s和s的值必然相等反之,如果最和岳属于不同的主理想,则s和s有可能不相等这一定理对RS码同样适用显然,在公式()所表示的生成矩阵中,各行向量均属于同一个主理想,因此在由此生成矩阵所构成的码空间中,各信息元的分离距离相等,该RS码是一个等保护能力码要构造RSUEP码,则应该按照信息元的距离要求设计最佳生成矩阵i:Gd=G』Gt:G,()这里Gt(,…,)表示主理想gI()的生成矩阵此时如果子空间()和()的汉明距离不相等,则它们对应的信息元的分离距离就不相等此时根据公式c=mGoe所生成的码字就具备不等保护的特性RSUEP码的译码算法下面探讨一种二次译码算法,该算法适用于所有具有两个保护能力等级的RSUEP码(假设),当码字中错误码元的个数满足lt空间由,个主理想(),(),…,()的直和构成,它的基底为G=,,,毋,,毋,毋DD,()Gompu~rEngineeringandApplications计算机工程与应用…】,子空间的维数为k,生成的码字为c保护能力为的子空间由Vt)个主理想瓯(),…,()的直和构成,它的基底为G”:【GL…G】,子空间的维数为k:,生成的码字为c,,显然,C=C”二次译码算法的译码过程分为两步在译码的第一步首先求出接收码字r的伴随式分量定义码的伴随式分量为S=e(a)(),当tE时,码字c(a)=o,所以有Si=r(„)I!P如果伴随式S的所有值都为,说明接收码字中没有错误如果s不全为,利用伴随式分量判断码字中错误码元的个数是否小于或等于,如果是,则对接收码字列写如下的关键方程组:s竹ISH…S=(i=t,…)()求解关键方程组后可以得到错误位置多项式:Or()::H()()l该式中根的倒数的幂次就是错误图样多项式e()中错误码元的位置,即el最后求解错误值,由于Si=r(Og)J(口)J!P()因此把错误码元的位置代入式(),即可求出该位置上的错误值由此便可得到估计错误多项式(),则最终的译码结果为c()=r()()如果码字中错误码元的个数大于,=„,则进入译码算法的第二步此时首先假设信息序列中前k个信息元为m=(,…,m,),则这部分信息序列对应的子码为c=InG,由此得到子码c,,:rOc,然后计算c”的伴随式分量S”(E(j)如果这些分量满足并且自洽,则假设成立,得到前k个信息元,而后k,个信息元填写否则改变假设,直到找到使伴随式分量s”满足校验条件的m在这个过程中,由于RS码的每个信息元的取值都有”„种可能,因此对高保护能力信息元的假设最多将进行,次二次译码算法的流程图如图l所示图lRSUEP码的二次译码算法流程图算法仿真下面以一(,,(,,,,,,))RSUEP码为例来说明并仿真编译码过程(这里(,,,,,,)表示码空间的分离矢量)该RSUEP码能纠正位错误码元,而信息元mom则可抗位错误已知该码的完备定义集为(„E丽}=i{OtliE(,,,,,ll,,)}()也就是说,该码由个最小理想的直和构成,其生成多项式分别为)赫xxXIX帆乜帆乜”go(糟xx乜乜乜乜lOIltx”Ix”IxxXIX()())赫xx慨慨”()这个子空间内的汉明距离分别为:ds=,do=,d=维数分别为:dim=,dimo=,dim,N~flzN(,,(,,,,,,))RSUEP码的生成矩阵为=lGlllllllllllllllllllllllllllllllllllllllllllllllllllllllllll()矩阵中空位兀累均补译码时,首先根据接收码字求出伴随式分量S,S,S和,现在纠错的目标是当接收码字中有两个错误码元时信息元mm可以被正确译出,因此设错误图样多项式为e()=“J,错误位置多项式为():l仃ix,,则有如下的关键方程组:orISI=s()OrISorSI=S(S)OrISS=S()OrIsS=s()OrI=()OrISorS=S()解方程组(),()可得()crscrS=ss十S()从方程()和()可以得到以下译码规则:()当S,S:,和均为时,接收码字中无错()当S,S:,S和s不全为时,说明码字中存在错误码元,如果ss=o,说明”等于,码字中仅存在一个错误码元,并且Or=S~S,由此可以求出错误码元的位置,再根据=e(„)I求出错误值,就可得到估计错误多项式(),从而译码结果即为()=r()()()如果S,SS和s不全为,并且sss,说明码毛倩,曾小清,张树京:一种适用于RS不等保护码的编译码算法()a*露匿鸸逛也匿灶:,,Dto仉:一l::一!:::!图()RSUEP码在AWGN信道下采用二次译码算法时的误码率(MPSK)字中存在两个错误码元,则译码器进入译码算法的第二步此时译码器对信息序列的前两个码元mm进行假设,由此得到子码c=(mI),则c”e=cr,子码c由理想g()和g)的直和构成,其伴随式分量S,s,,su和$u可以求出,对c列写关键方程组并求解,可以得到:(ss,s)(s)S”s,s()=嚣茜ntt()(orl”)o”墨()从方程()和()可以解出or和or,再用方程()加以验证,如果和or满足(),说明对信息序列momI的假设是正确的,否则改变假设,直到找到满足验证条件的mml对该(,,(,,,,,,))RSUEP码采用上述编译码算法进行信道编码,并在高斯白噪声信道下仿真其误码性能结果如图所示此时信息传输速率为Kbits,调制环节采用相相移键控MPSK图为该RSUEP码在相同仿真条件下,但译码环节采用一般RS码的译码算法时的误码率从这两幅图中可以看出二次译码算法对RSUEP码具有明显效果,采用二次译码算法后,信息元m和m的误码率明显降低了,而此时到m的误码率则与一般译码算法下七位信息元的误码率相当结论RS码适合于规模较大的信息分组,并且具有良好的抗误码特性本文采用分离最小理性的方法,构造出了具有不等保护特性的RS码的码空间,并且利用二次译码算法实现了码a*露匿鸸坦也匿灶毒i三三!jrnam~一E图()RSUEP码在AWGN信道下采用一般译码算法时的误码率(MPSK)空间对信息元的不均匀保护能力仿真显示,该算法为低保护能力的信息元提供的误码性能与等保护码相当,而为高保护能力的信息元则提供更佳的误码性能,因此该编译码算法对RSUEP码是有效的(收稿日期:年月)参考文献:【l】MaanickB,WolfJOnlinearunequalerrorprotectioncodesJIEEETransactionsonInformationTheory,,IT():】VailGilsWJTwotopicsonlinearunequalerrorprotectioncodes:boundsontheirlengthandcycliccodeclassesJJEEETransactionsonInformationTheoryIT():【】杨劲松线性不等保护能力码理论和方法的研究北京:北方交通大学】NambaK,FujiwaraEUnequalertDrprotectioncodeswithtwolevelburstandbiterrorcorrectingcapabilitiesCProceedingsoftheIEEEInternationalSymposiumonDefectandFaultToleranceinVLSISystems(DFrO),:【】OzbudakF,StichtenothHConstructlnglinearunequalerrorprotectioncodesfromalgebraiccurvesJIEEETransactionsonInformationTheory,,():【】LinMaochao,LinChichang,LinShuComputersearchforbinarycyclicUEPcodesofoddle,cthupto叨IEEETransactionsonInformationTheory,,():【StevensPExtensionoftheBCHdecodingalgorithmtodecodebinarycycliccodesuptotheirmaximumerrorcorrectioncapacitiesJIEEETransactionsonInformationTheory,,():【】DunningLA,RobbinsWEOptimumencodingoflinearblockcodesforunequalerrorprotectionjInformContr,,:『】王新梅,肖国镇纠错码原理与方法【M】修订版西安:西安电子科技大学出版社,(上接页)Caseb:Qr,要求当前状态满足Wr=Sr,则WrASr,Stl,Sr或Sr,Sr,ssml,…,ss一CaseC:Qr,要求当前状态满足Wr=l,则Wr=Sr,Srl,…,KSr,SrSS,ssml,…,ss一其中SSi=,ss一=一,()Vegas流丢包恢复后进入(Wr,Sr,Wv,Sv,incr,q,VQ,,QlJ),要求当前状态满足=o,设转移前的状态为(r,,,Sv,incr,q,Qr,QlJ),转移速率均为(Rvq缸),分为两种情况:Casea:”一,贝qWv=rWv,,QlJ=l,,…,WvCaseb:一,要求当前状态满足Wv=,则=Sv或Svl,V=Wv,Wv一l或Wv

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/16

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利