卷积码的译码算法研究

西安电子科技大学硕士学位论文卷积码的译码算法研究姓名：李校娟申请学位级别：硕士专业：通信与信息系统指导教师：陈彦辉20100101摘要自P.Elias首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力，如以卷积码为基础发展起来的Turbo码和分组卷积码等。未来的无线通信系统需要宽带、高速的系统性能来满足诸如数据、声音、图像之类的高质量多媒体传输业务，这必将导致更多高性能信道编码技术的出现。本文主要对卷积码的译码算法进行基础性研究。首先介绍了数字通信的基本结构，强调了信道编码在通信系统中的重要地位，指出卷积码是一种经典码。其次，详细介绍了卷积码的基本原理，主要是BCJR译码算法，并对Max-log-MAP、MAP等译码算法进行误码性能仿真。另外重点对卷积码(1，15/13)的Max-log-MAP译码器的FPGA实现进行设计。文中引入了滑动窗（预热窗和运算窗），预热窗为运算窗提供相对可靠的后向递推初始值，这样的做法在减小译码延时的同时也提高了译码的正确性。另外，分支转移概率和前向递推值在存储时采用了四个RAM轮流读写、分时复用的方法，有效地节约了硬件资源。最后，本文初步探索了和积算法（SPA）在卷积码中的应用，给出了迭代SPA译码和递推SPA译码模型，并分别对具有二个或更多个移位寄存器的若干卷积码进行仿真分析。关键词：卷积码BCJRMax-log-MAP和积算法AbstractConvolutionalcodehasshownitsgreatadvantagessinceitwasproposedbyP.Elias.BlockconvolutionalcodesandTurbocodesaretwotypicaltypesonthebasisofconvolutionalcodes.Inthefuture,thewirelesscommunicationsystemwillneedbetterperformancetomeetthedevelopmentofcommunicationbusiness,whichwillleadmorecodeswithbettererrorperformancetoappear.Thedecodingalgorithmsofconvolutionalcodesaremainlyresearchedinthisthesis.Firstly,thebasicarchitectureofdigitalcommunicationisintroduced,andchannelcodingismainlyintroducedasanimportantpartofthebasicarchitecture.Convolutionalcodeisaclassictypeofcodeandhasbeenusedinerrorcontrolfieldswidely.Secondly,theprincipleofconvolutionalcodesandthedetailedderivationofdecodingalgorithmofBCJRarestated,andtheerrorperformancearesimulatedandanalyzedunderdifferentdecodingalgorithmssuchasMax-log-MAP,MAP.Thirdly,theMax-log-MAPdecoderforconvolutionalcode(1,15/13)isdesignedundertheplatformoftheFPGA,inwhichtheconceptofSliding-Window(includingPre-warmingWindowandComputingWindow)isintroducedandtimedivisionmultiplexingofstorageareadoptedinordertoshortendecodingdelayandsavehardwareresourceseffectively.Finally,preliminaryexplorationoftheapplicationofSPAinconvolutionalcodesismadeinthisthesis.IterateSPAdecodingmodelandnon-iterateSPAdecodingmodelareproposed.Furthermore,severalconvolutionalcodeswithtwoormoreshiftregistersaresimulatedrespectively.Keywords：ConvolutionalCodesBCJRMax-log-MAPSum-ProductAlgorithm西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：日期西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。（保密的论文在解密后遵守此规定）本学位论文属于保密，在年解密后适用本授权书。本人签名：日期导师签名：日期第一章绪论1第一章绪论1.1选题背景和研究意义信道编码是数字通信系统的重要组成部分，随着通信技术的不断发展，信道编码技术也在不断地发展。在通信系统中，信道传输特性不理想以及噪声的存在，会导致接收端出现接收信号的错误，因此用于信道纠错的信道编码是数字通信系统中极为重要的一个环节。二十世纪40年代香农定理的出现为人们指出了纠错码的研究方向。根据香农的有噪信道编码定理[1]，可以推导出一个码率为R的编码通信系统达到无误码传输状态所必须的最小信噪比的理论极限。这个理论极限通常称为香农限，它说明对一个码率为R的编码通信系统，只有当SNR超过这个极限值时才能获得无误码传输。只要SNR高于这个极限值，香农的编码定理保证了能够获得无误码传输的（可能相当复杂）编码通信系统的存在性。另外，香农证明了在采用无限长的随机编码时，数据可以以接近信道容量的速率几乎无误码的传输，从而为信道编码的研究奠定了基础。P.Elias[2]在1955年提出了卷积码，卷积码是一种高效的纠错编码方式，广泛应用于卫星通信系统、遥测外测系统、移动通信系统和各种数字电视等。卫星通信系统中使用(2，1，7)和(3，l，7)卷积码作为标准编码方式。第二代移动通信GSM系统和IS.95CDMA系统分别采用(2，1，5)和(2，l，9)卷积码。第三代移动通信WCDMA系统中上下行链路中分别采用(3，1，9)和(2，l，9)卷积码完成纠错编码。卷积码有序列译码、门限译码、Viterbi译码、BCJR译码等几种译码方法。序列译码算法[3]是最早提出的卷积码译码算法，是一种以最大似然译码原理为基础的准最佳概率译码，R.M.Fano引入了一种新的序列译码的变型。门限译码算法[4]曾经是卷积码的第一种实用的译码方法。该算法虽然误码性能稍差但易于实现，使卷积码在有线和无线信道的数据传输中得到了一些实际应用。Viterbi算法[5]也是以最大似然译码原理为基础，是一种基于码的网格图的最佳概率译码算法。BCJR[6]算法是一种软输入软输出译码算法，更多地应用于Turbo码等的译码中。在通信系统中，为了提高传输的可靠性，各种纠错编码技术被广泛地采用。其中卷积码是一种应用非常广泛的性能优良的编码方式，在信道编码技术不断发展的今天发挥着重要作用，如以卷积码为基础发展起来的Turbo码[15]，由于其类随机特性以及采用迭代译码的思想几乎达到了接近香农限的误码性能[16]，因此研究卷积码的编译码具有重要的意义。本章主要介绍论文的相关背景，信道编码技术及其发展状况，最后说明本文的结构和主要的研究工作。2卷积码的译码算法研究1.2信道编码的发展1948年，信息论的奠基人Shannon在他的开创性论文“通信的数学理论”[7]中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，指出了实现最佳编码的三个基本条件：(1)采用随机编码方式；(2)编码长度L→∞，即码元序列长度无限；(3)译码采用最大似然译码算法。在满足这三个条件的前提下，香农认为在有噪信道中可以实现无差错传输。自20世纪50年代以来，编码理论研究与技术应用是长期围绕数字通信业务的特点和需要而发展的，即以伽罗华域上的代数编码方法为主体，研究适合串行信道中使用的码率尽可能高、检错纠错能力尽可能强的码型及其译码算法。从结构上看，码型可划分为分组码和卷积码两大类；译码算法主要分为基于代数的译码算法和基于概率的译码算法两大类。在分组码研究中，各种好的循环码、能纠正多重差错的BCH码、RS码[23]等码型都从理论推导到计算机模拟、搜索中找到。分组码的译码方法可分为代数和非代数两类。代数方法是以求解一组用以确定差错位置与数值的联立方程为基础的，而非代数方法以更为直接的方式确定差错模式。非代数方法主要有梅吉特（Meggitt）于1961年首先提出的纠突发差错的梅吉特译码器、1963年梅茜（Massey）所给出的门限译码器和1962年由布拉格（Prange）首先介绍的信息组译码法。此外，为了充分利用解调器所能提供的软信息，后来又陆续推出了一系列分组码软判决译码算法，如梅茜的后验概率（APP）译码算法、哈特曼（Hartmann）-鲁道夫（Rudolph）最优逐符号译码算法和威尔顿算法等。在卷积码研究方面，随着Viterbi算法的提出及序列译码算法Fano算法的提出，也出现了以译码算法优化、减少译码复杂度为突破口的一批好的研究成果。为了在译码复杂性不高的同时获得更好的纠错性能，范尼（Forney）于1966年首先提出级联码的概念。20世纪70~80年代，以Goppa为首的学者从理论上构造了一类Goppa码，其中的一个子类的性能达到了香农信道编码定理中提出的“好码”的标准，具有理论上的重大意义。这个时期由于大规模集成电路的迅速发展，为信道编码的大规模使用打下了坚实的基础，如美国在20世纪70年代发射的“旅行者”号宇宙飞船中就成功地运用了信道编码技术，使宇宙飞船能从遥远的太空传回清晰的照片。同时，由于数字信号处理技术的发展，信道编码在通信系统中的应用也得到关注，并广泛用于实际的通信系统中。另外，近几十年来，许多研究学者致力于寻找低编译码复杂度的实用化编码，先后提出了非规则重复累加码（IRA）[25]，以及多维并行级联单奇偶校验码（M-PC-SPC）等结构。在1993年IC国际会议上，法国不列颠通信大学的C．Berrou、A．Glavieux[8]等人，首先提出了一种称之为Turbo码的编译码方案。Turbo码的出现，是首次对第一章绪论3香农提出的非构造性问题的构造性回答，引起了研究人员对随机编码方式和迭代译码[17]的热情关注，完善了香农信道编码理论。LDPC码由Gallager[9]于19世纪60年代初期首次提出，然而不幸的是，他的重大发现被编码研究人员忽视了大约20年；1996年，两位LDPC码的追踪研究者MacKay和Neal[10]重新发现了LDPC码的优越性能。总之，Turbo码和LDPC码的出现，加深了人们对随机编码方式和迭代译码的全面