Turbo码编译码系统设计及其FPGA实现

-.z硕士学位论文题目Turbo码编/译码系统设计及其FPGA实现〔英文〕TheDesignofTurboCoding/DecodingSystemanditsImplementwithFPGA-.z摘要Turbo码的出现是纠错编码史上的一个重大突破，它具有在低信噪比下接近Shannon理论极限的优异译码性能，在许多通信系统中都有很大的应用前景。本文主要研究的是Turbo码的编码和译码算法及其FPGA硬件实现。首先，介绍了课题的研究背景和Turbo译码的国外研究现状；其次在介绍Turbo编译码原理的根底上对目前常用的各类译码算法进展介绍和性能分析；接着主要研究Turbo码译码器的设计，最后用硬件实现了其电路。本文分别对Turbo码的MAP算法，Ma*-Log-MAP算法，Log-MAP算法、SOVA算法等进展了推导。在深入分析译码算法的根底上，决定采用Log-MAP算法作为本系统的译码算法。在对该系统的硬件实现过程中，为了节约硬件资源和减少延时，对Log-MAP算法进展了一些改进。在系统设计中，根据FPGA技术的优点，采用“自上而下〞和“自下而上〞结合的设计方法，通过适当的模块分割，将Turbo码的译码器分为三大模块:Log-MAP译码单元模块、交织/解交织器模块和控制信号产生模块。本文针对编码器中的延时模块采用一种类似于交织器的方式来实现延时功能，使其精度更高，编码效果更好。并对译码器进展了研究，给出了一种查找表法来实现复杂的E函数，此方法明显的简化了系统的运算复杂度。在硬件实现Log-MAP算法过程中，通过巧妙地改变前向矢量的计算顺序，减少了系统占用的硬件资源。最后利用QuartusII软件对编译码系统做了计算机仿真，结果说明本系统实现的Turbo码译码器的误码性能较好，具有一定的实用价值。关键词:Turbo码，Log-MAP算法，软判决，FPGA-.zABSTRACTTheemergenceofTurbo-Codeisconsideredasthemoste*citingandpotentiallyimportantdevelopmentinthehistoryoferror-correctingcodes.IthasasuperiordecodingperformanceapproachingtheShannonlimitandhasbeenwidelyapplicatedinmanymunicationsystems.ThegoalofthispaperistostudyTurboencoding/decodingalgorithmanditshardwareimplementationwithFPGA.Firstly,itintroducesbackgroundofthesubjectandtheresearchsituationaboutTurbodecoding;Secondly,itintroducesthecurrentvariousdecodingalgorithmandanalyzestheirperformancerespectivelybasedonanalyzingtheencoding/decodingprincipleofTurbo-Code;thenstudiesthedesignoftheTurbodecoderwhichhardwarecircleissuccessfullyimplementedfinally.IncludingtheMAPalgorithm,Ma*-Log-MAPalgorithm,Log-MAPalgorithmandSOVAalgorithminTurbo-Codealgorithmisdeducedrespectivelyinthepaper.Onthebaseofin-depthanalysisofthedecodingalgorithm,theLog-MAPalgorithmasthedecodingalgorithminthesystemisselected.Intherealizationprocessofhardwareinthissystem,Log-MAPalgorithmhasbeenimprovedinordertosavethehardwareresourcesandreducedelay.InthedesignofTurbo-Codesystem,thebiningdesignmethodofboth"fromtoptobottom"and"frombottomtotop"isimplementedaccordingtoadvantageoftheFPGA,andthedecoderisdividedintothreeblocks:Log-MAPdecoder,interleaver/deinterleaverblockandtimingcontrolblock,throughappropriatesegmentationmodule.Inthispaper,asimilarinterleaverisusedbythedelaymoduleoftheencoderasanapproachtoachievedelayfunction,whichmakesitmoreprecise,effectiveandbetter.Meanwhile,inthestudyofthedecoder,alook-uptablemethodisgiventoachieveple*E-function,andthemethodsignificantlysimplifiesoperationple*ityofthesystem.IntheprocessoftheLog-MAPalgorithmimplementationwithhardware,thecalculationofvectorsequenceissubtlychanged,whichcanreducetheshareofthehardwareresources.Finally,encoding/decodingsystemissimulatedbytheQuartusIIsoftware,andtheresultshowsthatTurbo-Codesystemhasabettererrorperformanceandsomepracticalvalue.KeyWords:TurboCodes,Log-MAPAlgorithm,SoftDecision,FieldProgrammableGateArray-.z目录TOC\o"1-4"\h\z\u摘要IABSTRACTII目录III第一章绪论1§1.1Turbo码编/译码方案的提出1§1.2Turbo码的研究现状2§1.3Turbo码的研究展望3§1.4课题背景与本论文的主要工作及奉献4§1.4.1选题背景4§1.4.2论文的构造4第二章Turbo码的根底知识5§2.1Turbo码简介5§2.2Turbo码编码器原理6§2.2.1Turbo码编码构造6§2.2.2RSC分量编码器8§2.3交织器10§2.4Turbo码译码器原理14§2.5Turbo码性能的分析16影响Turbo码性能的因素16§2.5.2Turbo码性能的物理解释17§2.6本章小结18第三章Turbo码译码算法19§3.1最大似然译码原则19§3.2MAP译码算法20§3.3Log-MAP算法和Ma*-Log-MAP算法25§3.4SOVA算法28§3.5几种算法的比拟29§3.6本章小结31第四章Turbo码编译码器的FPGA硬件实现方法32§4.1FPGA技术简介32§4.1.1可编程逻辑器件32§4.1.2硬件描述语言33§4.1.3FPGA硬件设计环境33§4.2Turbo码编译码方案确实定34§4.2.1RSC的生成多项式34§4.2.2交织器构造确实定34§4.2.3编码器构造确实定35§4.2.4Turbo码译码器构造确实定35§4.3Turbo码编码器的FPGA实现36§4.3.1RSC编码器模块的实现36§4.3.2交织器模块的实现36§4.3.3编码器模块的实现38§4.4Turbo码译码器的FPGA实现39接收码字的量化及其运算40§4.4.2E函数的实现方案41§4.4.3Log-MAP译码器的FPGA实现42§分支矢量D模块的实现43§分支矢量A模块的实现44§分支矢量B模块的实现46§对数似然概率的计算48§4.4.4Turbo译码器总体构造的实现50§4.5本章小结51第五章仿真结果分析52§5.1Turbo编译码其系统仿真52§5.2系统仿真构造分析53§5.3本章小结57第六章总结58参考文献60致63硕士在读期间的研究成果64-.z第一章绪论Turbo码的提出对信道编码领域的研究有着重要的意义。由于Turbo码具有接近Shanon理论极限的性能[1]，尤其是低信噪比下的优异性能使Turbo码在许多通信系统中都有非常大的应用潜力。除了在深空通信、卫星通信以及多媒体通信等领域的应用外，Turbo码在无线移动通信系统中的应用是目前的研究热点。本章主要介绍了Turbo码的产生背景、开展现状及本论文的工作安排。§1.1Turbo码编/译码方案的提出随着用户对通信质量和数据传输速率要求的不断提高，通信技术和计算机技术在不断的迅速开展，作为消除或降低信息传输错误有效手段之一的信道编码也在不断开展。在过去的50多年里，有关纠错码技术的研究已经取得了许多骄人的成果。随着信息时代的到来以及微电子技术的飞速开展，今天的纠错码已不再单纯是一个理论上探讨的问题，它已经成为现代通信领域中不可或缺的一项标准技术。现代通信系统的复杂化以及通信业务的多样化，要求通信系统能够对话音、数据、图像等数据量大的信息实现高速实时传输，而且用户对通信质量的要求也在不断提高。另外，移动通信的快速开展以及个人通信的全球化，使得对高速率数字移动通信等领域所采用纠错编码技术的要求越来越高。近年来，依据信道编码定理，人们一直致力于寻找能满足现代通信业务要求，构造简单、性能优越的好码，并在分组码、卷积码等根本编码方法和最大似然译码算法的根底上提出了许多构造好码及简化译码构造复杂性的方法，提出了乘积码、代数几何码、低密度校验码、分组卷积级联码等编码方法和序列译码、逐组最正确译码、软判决译码等译码方法以及编码与调制技术相结合的网格编码调制技术。虽然软判决译码、级联码和编码调制技术都对信道码的设计和开展产生了重大影响，但是其增益与Shannon理论极限始终都存在2－3dB的差距。直到1993年在瑞士日瓦召开的国际通信会议上，C．Berrou，A．Glavieu*和P．Thitimasjshima提出了Turbo码[2]，这是一种可实现的编码系统，而且获得了几乎接近Shannon理论极限的译码性能[3]。Turbo码一出现，就在编码理论界引起了轰动，成为自信息论提出以来最重大的研究进展，Turbo码的提出是信道编码史上的一个重要里程碑。它优异的性能引起了研究人员的极大兴趣，并相继在有关方面进展积极的探索和研究．但由于几位创造者仅给出了一定参数下的计算机仿真结果，而没有严格的理论分析和解释，所以近些年来在编码界掀起了Turbo码的研究热潮。目前Turbo码的研究主要分为设计与性能分析、理论研究以及应用3个方面。Turbo码之所以具有优异的性能，交织器和译码算法起到了很大的作用，对于其应用的研究也有很大的进展。§1.2Turbo码的研究现状Turbo码具有极其广阔的应用前景，是信道编码界的一个突破，被称为二十一世纪的纠错编码。从1995年开场，有关Turbo码的文献大量出现，它已成为通信技术的新热点，目前Turbo码的研究主要集中在以下几个方面[4]:(1)Turbo码的理论分析在介绍Turbo码的首篇论文里，创造者Berrou仅给出了Turbo码的根本组成和迭代译码的原理，而没有严格的理论解释和证明。所以，在研究的Turbo码起步阶段，其理论的研究就显得尤为重要。(2)Turbo码的设计Turbo码由分量码经由交织器级联而成。因此，分量码和交织器设计得好坏就决定Turbo码性能的关键因素。主要包括交织器的设计、码的级联方式、Turbo码的性能分析等等。在性能分析中，主要对码重分布及距离谱进展分析。(3)软输出迭代译码算法Turbo码的编码过程实际上是一个利用强约束短码构成伪随机长码的过程，通过在分量译码器之间交换外部信息来提高性能。其译码算法主要有两大类:一类是基于最大后验概率〔MAP[5],Ma*imumAPosteriori〕的软输出算法。一类是基于Viterbi算法〔VA[6]，ViterbiAlgorithm〕的软输出算法。考虑到Turbo码在未来高速数据传输中的应用，寻找延时小和复杂性低的软判决译码算法始终是Turbo码研究的重要课题。(4)Turbo码的编码调制技术利用Turbo码调制(TurboCodeModulation)技术可以在不增加系统带宽要求的条件下有效地提高编码增益。将Turbo码与TCM相结合来实现高增益高频谱效率地编码调制方案称为Turbo-TCM。在与调制编码技术相结合方面的改进表达在：将栅风格制编码和Turbo码结合可以得到大的编码增益和高的带宽效率，如将Turbo码与OFDM调制、差分检测技术相结合，具有较高的频率利用率，可有效地抑制短波信道中多径时延、频率选择性衰落、人为干扰与噪声等带来的不利影响，而且还有较低的译码复杂度。(5)Turbo码原理及其应用由于Turbo码具有接近Shannon理论极限的性能，尤其是低信噪比下的优异性能使Turbo码在很多通信系统中都有非常大的应用潜力。除了在深空通信、卫星通信以及多媒体通信等领域的应用以外，Turbo码在无线移动通信系统中的应用是目前的研究热点。Turbo码已经成为第三代移动通信系统的标准之一[7-10]，有关其关键技术的标准化已经出现。此外，Turbo码在文本传输和数据存储等方面也有应用。(6)Turbo译码器的实现**大利亚大学SmallWorld通信研究组最先开场开发Turbo码编译码器并推出了Turbo码产品。A.Chass、D.Garrett和K.Koora等人也分别在不同的数字芯片上设计实现了MA*-Log-MAP算法和SOVA算法。在Turbo码编译码器设计过程中，最主要的是考虑数据处理速度和功耗。为降低译码器功耗，一个方法是减少平均的译码迭代次数，根据每一帧数据得迭代次数和信噪比值来动态分配电压，同时在允许的延时围使译码速度放慢。目前，许多科研院所和大公司都在进展Turbo码编/译码芯片的开发，如新加坡OKI公司的EMIK07,Altera公司的Turbo码Ipcore等都宣称开发出了相应的产品，国也有很多高校和研究机构在对Turbo码编译码器的硬件实现进展研究[11-14]。但从公布的技术指标上看，都存在复杂度高、存储量大、译码延时长、功耗大等缺点。§1.3Turbo码的研究展望从1997年开场，Turbo码和相关主题的国际会议每隔三年举行一次。而从2003年以来，对于Turbo码的研究越来越倾向于具体应用。2006年的Turbo码会议在德国慕尼黑与第六届信源信道编码会议一起举行，Tubro码会议的主要议题有：纠错码、Tubro码和LDPC码编码和Turbo编码调制、检测和Turbo检测、均衡和Tubro均衡、同步和Turbo同步、多用户检测界限、性能和收敛性算法和成员码、交织和座标图、Fountani码以及网络编码等。从中看到Turbo码今后的开展方向，除了对编解码器和交织器的新设计和改进之外，更多研究将会投入到Turbo码与其他技术的联合应用中去。Turbo码作为信道编码将与所要保护传输的信源本身特点相结合，会对Tubro码的设计提出不同的要求。例如语音、音频、图象、视频和超文本数据对于传输信道的延迟抖动和可靠性都有着不同的要求，而视频编码技术中的各种分层编码所产生的不同的码流对传输的要求也不尽一样。各种数据对平安性的要求也不一样，因而Turbo码与信源联合编码及不平等保护等技术的结合在实现上还有很多问题有待解决。虽然Turbo码最早提出来的时候是为了深空和卫星通信，但其价值远远超出了这个围，因此Turbo码在各种不同通信环境中的性能一直是研究的一个重点。纵观Turbo码的开展现状和要求，本人认为需要进一步研究的课题有：〔1〕最优分量码与交织器的联合设计。〔2〕低复杂性译码算法。〔3〕译码迭代过程的优化、收敛性以及迭代停顿准则的设计。〔4〕联合信道估计、多用户检测、均衡和译码算法。〔5〕Turbo码与高阶调制技术的结合。〔6〕Turbo码编译器的硬件实现。〔7〕Turbo码在无线通信、移动通信以及多媒体通信中的应用，特别是在移动网络、IMT-2000及加密系统中的应用等。§1.4课题背景与本论文的主要工作及奉献§1.4.1选题背景本论文对所研究的Turbo码编码/译码器，通过系统功能模块分割的设计方法，将整个系统模块化、各模块的分割，考虑到了其功能的完整性和灵活性。整个系统分为:MAP译码器模块、交织器/解交织器模块和时序控制模块。利用Altera公司的QuartusII软件，灵活运用文本编辑器和图形编辑器，对APE*2OK系列器件进展编程[15]，实现Turbo码编码器和译码器的功能。系统仿真结果证明了该编译码器有良好的性能，有相当的实用价值。§论文的构造本课题对Turbo码编译码器的设计及其FPGA实现进展了研究，全文分为六章，除第一章概述外，其余各章安排如下:第二章介绍了Turbo码的根底知识。先介绍了编码器构造及其成员码、交织器，然后介绍了Turbo码译码器原理、分析了影响Turbo码性能的几种因素及其优异性能的物理解释，目的在于为后面Turbo码的硬件设计提供相应的理论根底。第三章详细介绍了Turbo码的译码算法，主要有MAP、Log-MAP、Ma*-Log-MAP、SOVA等。并分别对它们进展了详细的数学公式推导，比拟了各种算法的特点，综合译码性能和实现复杂度考虑，从而根据实际情况选择适合硬件实现的算法。第四章重点研究了Turbo码的FPGA实现。本章首先介绍了FPGA技术的相关知识，然后从前面分析结果的根底上从硬件方面来实现Turbo码编译码器。其中包括对交织器的硬件设计进展了详细介绍，对Turbo码编码器的硬件设计进展了改进。在译码器的设计中，采用了Log-MAP算法，对E函数、量化运算、Log-MAP译码器的三个大模块:分支度量、前向状态矢量和后向状态矢量等各模块的实现进展了详细的介绍。对分块并行Turbo码算法的硬件设计进展了初步的研究。第五章主要介绍了Turbo码硬件仿真过程及其结果的分析。包括信源模型的建立、信道模型的建立，并根据仿真得到的结果进展了分析。FPGA的仿真主要是用数据来表示，本文还用MATLAB仿真证明了前面分析的正确性。如仿真比拟几种算法的译码效果，仿真比拟不同的交织器长度和量化长度时的译码效果。第六章总结了本论文的研究工作，介绍已经做了哪些方面的工作，还有哪些缺乏，并进一步提出了论文中还有待于深入研究的问题及方向。-.z第二章Turbo码的根底知识1993年Turbo码的编码方案的提出，带来了一种迭代译码的全新思想，使通过可译编码逼近信道容量成为可能。实践中显示，Turbo码具有抗衰落、抗干扰性能，尤其适合功率受限的系统，只要时延和复杂度允许，可在多种恶劣条件下提供接近极限的通信能力。本章将详细的介绍Turbo码的根本原理、编译码构造、交织器的作用和分类、及性能分析等，为后面的设计提供了理论依据。§2.1Turbo码简介在现代通信系统中，为了保证各种数据在信道中可靠有效的传输，往往需要利用纠错编码技术。尤其随着无线数字通信的开展和各种高速率、突发性强的业务的出现，对纠错码技术提出了越来越高的要求[16]。Turbo码编译码器实现的就是通信系统道编码到信道译码这一阶段的容，这也是最重要的局部，它的误码率对整个系统起决定性作用，Turbo码所要研究的容就是图2.1所示的信道编译局部。图2.1数字通信系统模型的信道局部纠错码起源于香农1948年提出的香农第二定理〔也称信道编码定理〕。根据香农信道容量公式[1]，实现可靠通信所允许的传输速率的上限为信道容量。在信道带宽无限和功率受限的条件下，高斯白噪声信道容量C表示为：〔2-1〕其中B表示带宽，表示信道输入带限信号的平均功率。如果传输速率为，则有：〔2-2〕经简单变换得：〔2-3〕这就可以得到信道编码定理：每个信道具有确定的信道容量C，对于小于C的码率R，存在有速率为R码长为n的分组码及卷积码，假设用最大似然译码，则随着码长的增加，其译码错误概率P可以任意小，即：和〔2-4〕其中和是大于0的系数，和为正实函数，称为可靠性函数。上式说明在带宽无限信道中，对于任何小于C的传输速率，可在码率不变的前提下通过增加分组码的长度n，使过失率为任意小，当极限情况n趋于无穷，就可以实现高斯白噪声下的无误传输，称为香农限。即当传输速率到达信道容量时，可靠通信所需的最小比特信噪比即香农限为－1.6dB。香农限成为设计信道编码时试图逼近的信噪比的下限，为实现有效可靠的通信奠定了理论根底。1993年，法国学者C.Berrou等人提出了一种称为Turbo码的新型编码方案，由于它很好的应用了Shannon信道编码定理中的随机性编、译码条件，从而获得了几乎接近Shannon理论极限的译码性能，从而引起极大的轰动，也使得Turbo码的研究成为近年纠错码研究的一个热点。传统的Turbo码是一类并行级联的系统卷积码，它由两个经交织器连接的子编码器生成。Turbo码的译码采用了软输入和软输出的译码算法和迭代译码的方法，使子译码器间可以互相传递信息，保证编码信息的充分利用。两个子译码器的输出序列越不相关，在译码端交换的互信息量就越大。根据C.Berrou等人仿真的结果，二元Turbo码在速率R＝1/2和码长较长〔256×256〕的条件下，经18次迭代得到了离理论极限约0.7dB的误码率性能。§2.2Turbo码编码器原理§Turbo码编码构造典型的Turbo码编码如图2.2所示。主要由分量编码器、交织器以及删余矩阵和复接器组成。两个分量编码器由码率为R＝1/2的RSC〔递归系统卷积码〕组成，其构造一般是一样的，且输入一样的长度为N的信息序列，在送入第一个分量编码器进展编码的同时作为系统输出直接送到复接器，同时输入序列经过交织器交织后的交织序列送入第二个分量编码器。其中，为交织映射函数，N为交织长度，即信息序列长度。两个分量编码器输入序列仅仅是码元的输入顺序不同。两个分量码编码器输出的校验序列分别为和。为提高码率和系统频谱效率，可以将两个校验序列经过删余矩阵删余后〔得到〕再与系统信息一起经过复接器构成编码序列。图2.2典型的Turbo码编码器由线性分组码的特性知道，码字的最小距离是估计码字性能的首要参数。对线性分组码而言，码字最小距离就是码字集合中汉明重量最小的非零码字的汉明重量。交织器和分量码的结合可以确保Turbo码编码输出码字具有较高的汉明重量。在Turbo码编码器织器的作用是将信息序列中的比特顺序重置。当信息序列经过第一个分量码编码器后输出的码字重量较低时，交织器可以使交织后的信息序列经过第二个分量编码器后以很大的概率输出高重码字，从而提高码字的汉明重量，同时好的交织器还可以有效的降低校验序列间的相关性。通过交织，编码序列在长为2N或3N〔不经过删余〕比特的围具有无记忆性，从而由简单的短码构造成近似随机长码。因此，交织器设计的好坏在很大程度上影响着Turbo码的性能。常用的交织方式有均匀交织、非均匀交织、伪随机交织等，理论上，随机交织的效果最好。对于数字通信领域日益紧的带宽资源，提高码率就意味着节省带宽和降低通信费用。删余矩阵是目前提高Turbo码码率的主要方法，它可以通过删除压缩合并各成员编码器地输出校验序列来调整Turbo码编码器的编码速率。比方本文删余后得到的是码速为1/2的Turbo码，假设校验码不删余，则得到的是码速为1/3的Turbo码。理论上通过改变删余矩阵可以得到任意码速的Turbo码。删余单元的作用是调整编码效率，为了提高码率。实际中，一般使信息序列全部传送，而校验序列给予适当的删除。在接收端应对接收序列进展插，未被传送的比特位用0填充，以保证序列的完整性。但是，当码率过高时，每个信息码元对应的校验码元数量减少，将导致译码端的纠错性能降低。而码率过低，又使得码元传输效率过低，所以在调整编码率时需做多方考虑，在编码效率和纠错性能间做折衷考虑。复用单元完成编码的并/串转换，使输出适合信道的传输。复用后的输出序列为。根据删余方式，取值或。假设输入信息序列为则编码器使用图2.2所示的递归系统卷积分量码编码后的系统输出和校验输出分别为和假设假设经过交织器交织后的输入信息序列为则下面的递归系统卷积分量码编码后的校验输出为在未删余时得到的码率为1/3的输出码字采用删余矩阵删余后得到的码率为1/2的输出码字为§RSC分量编码器线性分组码是一种常用的纠错编码，包括循环码、BCH码等。它们的共同特点是：一个码字的监视码元仅与本码组的信息码元有关，而与其它码组的码元无关。本节介绍的卷积码是另一类编码，它与分组码的区别在于：本组的码元不仅与当前输入的信息码元有关，而且还与以前的v时刻输入的信息有关。卷积码的纠错能力随着m(m=)的增加而增大，而过失率随着v的增加而指数下降。在编码效率与设备复杂度一样的前提下，卷积码的性能优于分组码，至少不低于分组码。卷积码有三个重要的特性：1.存储长度v,v的值与卷积编码器中延迟单元的个数相对应。2.约束长度N=v+l。3.编码效率。编码效率定义为信息码元个数与经过编码后总的码元个数的比值。传统卷积码的编码器不包含反响，因此可以等效为一个有限冲激响应(FIR)滤波器，而递归系统卷积码RSC(RecursiveSystematicConvolutionalEncoder)是一种特殊的卷积码[17-18]，由于存在反响，因此可以等效为一个无限冲击响应(IIR)滤波器。本文使用的分量编码器如图2.3所示，其生成多项式为(7,5)的递归系统卷积码的编码器，编码速率为1/2。其输出的码元不仅与当前时刻的信息元有关，而且还与前v(本文使用v=2)个时刻的信息元有关。因此，在编码过程中，每N个(N=v+1=3)相邻的子码之间有约束关系。图2.3(7,5)的递归系统卷积码的编码框图从图可以知道输入的编码关系〔2-5〕〔2-6〕〔2-7〕即延时因子为〔2-8〕〔2-9〕由此得到生产多项式g1＝,g2＝.卷积码可以用多种方法表示，一般有矩阵法、码树法、状态图法和栅格图法等，可根据译码方法的不同而采取不同的表示方法。在Turbo码中，用状态图和栅格图来描述译码过程较为方便。由图2.3递归系统卷积码的编码框图可以看出，递归系统卷积码编码器是一个有限状态机，因此可以分别用图2.4和图2.5表示它的状态转换图和栅格图。图2.4所给出的递归系统卷积编码器对应的状态转移图，其中椭圆是编码器所处的状态，箭头的起点是初始状态，终点是输入数据后的状态，射线上斜杠左边1位是编码器的输入数据，右边2位是编码器的输出数据。因为图2.4中的编码器有两个存储器，〔即v＝2〕所以编码器共有4〔〕个状态，即S0＝00,S1=10,S2=01,S3=11。例如，假设编码器的初始状态为S0，当输入信息为1时，编码器的状态就从S0转移到状态S1,，并输出码元C为11。假设输入信息为0时，则编码器停留在S0状态，输出码元C为00。这样不断输入信息，编码器状态不停转移，并相应输出一个子码，它们就组成了编码器的输出码序列。而图2.5给出了图2.4递归系统卷积编码器所对应的状态转移图这个递归系统卷积码的栅格图构造，图中虚线表示输入信息为0的状态转移，实线表示输入信息为1的状态转移。这个栅格图中的每一个分支给出三种信息：分支的状态(当前状态和下一状态)，编码器的输入的信息比特和输出校验比特。图中实线表示输入信息比特为1,虚线表示输入的信息比特为0。例如，对于图中第一条实线，可知在这个分支上输入的信息比特为1，编码器的状态从S0的00变到S1的10，并且编码器的输出为11(=l,=1)。对于图中第一条实线，可知在这个分支上输入的信息比特为0，编码器的状态从S0的00回到本身，并且输出编码00。一共有四个状态S0-S3，它们之间互相转换，其它细节就不多介绍了，从图中可以看出。对于传统的卷积码来说，通过在数据帧的末尾嵌入v个零比特就可以迫使编码器格图回到全零状态。但是对于递归系统卷积码来说，由于它具有无限冲激响应特性，因此仅靠嵌入v个零比特一般无法使递归系统卷积编码格图回到全零状态，此时可以通过解状态变量方程得到所需的尾比特。例如在图2.3中的构造，根据式〔2-6〕知道，当需要使编码器状态回到零，就是令d1等于零，得到：〔2-10〕这就是使编码器回到零状态所需的尾比特。图2.5v=2的RSC编码器的栅格图§2.3交织器经过研究发现，Turbo码之所以不同于以往的其它编码，表现出了极佳的性能，其中一个重要原因就是采用了交织器。交织器的主要作用就是将原始数据序列打乱，使得交织前后数据序列的相关性减弱，这样做很突出的一个优点便是大大降低了数据突发错误的影响。在现代的高效编码调制技术中，无论是级联编码还是Turbo编码中都要使用交织器。从前面的描述知道，交织器的主要作用是减小突发过失的影响和改善信息序列的码重特性。通常Turbo码的自由距都不是很大，但是由于交织器的作用，使得Turbo码和卷积码相比，其重量近似的码字数目要小的多，从而使得在一定条件下Turbo码的译码过失概率比卷积码的过失概率低。交织器是Turbo码的重要特征，在Turbo码的帧长、码率和约束长度一定的情况下，交织器的构造决定了Turbo码的译码性能，这是由于交织器的构造影响着Turbo码的重量分布。因此如何选择交织器也成为Turbo码系统设计的重要课题。下面给出了在Turbo码织器的设计应该遵循的设计准则[19]：〔1〕最大程度地置乱原数据排列顺序，防止置换前相距较近的数据在置换之后仍相距较近，特别要防止置换前相邻的数据在置换后再次相邻。〔2〕尽可能防止与同一信息位直接相关的两个分量编码器中的校验位均被删除。〔3〕对于不归零的编码器，交织器设计时要防止出现“尾效应〞图案。〔4〕在满足上述要求的交织器中选择一个较好的交织器，使码字之间的最小距离(或自由距离)尽可能大，而使码重为的码字数要尽可能少，以改善Turbo码在高信噪比时的性能。L.C.Perez等人的研究说明Turbo码的渐近性能接近渐进线，在高信噪比时出现错误平台是小的引起的[20]。Turbo码交织器有许多种，如分组交织器、螺旋交织器、奇偶交织器、随机交织器、S－交织器、循环移位交织器、均匀交织器、“smile〞交织器、最优周期交织器等等。这里我们介绍几种典型的交织器。行列交织器行列交织器，即分组交织器，该交织器是将信息序列视为矩阵。通常采取以按行写按列读的方式实现码元交织，交织后的码元距离特性均匀分布，即交织前信息按行写入，但是交织器矩阵交织后信息位按列读出，从而实现行列置换。其特点是交织方式非常简单，同时根据后面仿真结果可以看出，它对短序列译码效果较好，但交织后码元的去相关不彻底。而解交织列顺序写入，行顺序读出。表2.1和表2.2表示交织器的交织与解交织的存储器实现过程。分块交织器的交织函数为：(2-11)表2.1行列交织器的交织过程表2.2行列交织器的解交织过程在纠错编码中，交织矩阵的行数叫做交织深度，交织矩阵的列数叫做交织跨度。分块交织的特点是方式简单、对短序列交织效果较好，但交织后对信息比特的去相关不彻底。伪随机交织器与S随机交织器在随机交织器里，一个N比特的信息序列被输入交织器里，然后被随机读出。理论上，信息序列之间的交织方式是变化的，以便更好地反映随机性。但在实际应用中，接收端必须能够确定每一帧码字序列的交织方式，就增加了传输的负担，因此完全随机化交织并不是最正确的方式，一般使用的是伪随机交织器[21-22]。伪随机交织器通常在输入信息序列较长时可以采用近似随机的交织映射方式，每个长度为N的伪随机交织器共有N！种可能的交织形式。但是对应于N！种可能的交织形式，交织后有些元素之间的距离非常小，这样会导致对*些错误序列相关行的离散度不够。因此利用下面的S-随机交织器可以局部解决这个问题。通常，随机交织器是以*种方式产生一组随机数，决定信息序列在交织器中的排列方式,信息序列之间的交织方式是一样的。随机数可以这样来产生：首先在从1到N之间等概率地随机选择一个整数，作为信息序列中第一个比特在交织后的位置，然后从剩下的N-1个整数中等概率地随机选择一个整数，作为信息序列中第二个比特在交织后的位置，依此类推，直到N个信息比特都进展完。为了防止交织前相距较近的数据在交织后仍相距较近，可以把上述交织方式修改为S随机交织，就是把上述随机交织器加了一个约束。为了进一步减小交织器的相关行的离散度，设计在伪随机交织过程中相邻的S个比特经过交织后它们之间的距离至少为S，从而构成了S-随机交织器。每一个随机产生的整数要和先前个选择的整数比拟，如果当前产生的随机整数与先前个选择的整数之差的绝对值小于的话，当前产生的随机整数就被抛弃，重新选择，即：(2-12)考虑到算法的搜索实际，通常选择.S-随机交织器是一种公认的性能良好的交织器。因为它能够将错误序列中相邻比特在交织后扩散，距离至少为S，从而使错误转化为随机错误，有利于卷积码纠错。信息序列越长，随机数的产生越均匀，交织前后序列的相关性越小。随着S值的增加，Turbo码的性能不断提高。但S值越大，条件越难满足，交织器的设计就越困难。通常比拟好的S-随机交织器的参数要满足(2-13)其中N为交织长度。当S大于这个值时一般难以收敛。3、分组螺旋交织器分组螺旋交织器的工作原理是：首先将数据序列按行的顺序写入矩阵〔其中矩阵的行m与列n互素〕，在交织时从矩阵的左上角开场向右下方向读取数据，每向下一行同时右移一位(即行索引递增的同时列索引也递增，增量步长为1)。在行的方向和列的方向分别对索引取模m和n，即假设令和分别表示第i个比特的行索引和列索引，则分组螺旋交织器的数据读取顺序是以行列顺序依次写入，然后在交织时从矩阵的左上角开场向右下方读取数据，每向下一行同时右移一位。它的表达式如下：(2-14)其中上述递归运算的初值为i＝0，1，2，…N－1.初始值.对于分组螺旋交织器，当交织矩阵的大小为，且交织过程从左上角开场读数据；或者交织矩阵大小为，且交织过程中从左小角开场读数据时，得到的分组螺旋交织器就是对称交织器。本对称交织器的交织器与解交织器完全一样，下面关于对称性的介绍时会有详细说明。下面以长度为4×3螺旋交织器为例，其实也就是对称螺旋交织器，详细说明它的工作过程。如表2.3和2.4所示，把交织器的工作过程通过RAM的写入与读出表示非常清楚。表2.3写入RAM的顺序表2.4读出RAM的顺序相对于行列交织器而言，螺旋奇偶交织器有以下优点:1)对称性交织器对称性是指假设输入序列的第i个比特经过交织后成为输出序列的第j个比特，则输入序列中的第j个比特经过交织后也一定输出序列的第i个比特。这种性能使得交织器的交织序列和解交织序列完全一致，这就使得在硬件实现的时候可以用同一模块来实现交织和解交织功能，从而减小占用的硬件资源。2)保奇偶性所谓保奇偶性是指原来处于奇数位或偶数位的信息比特，在交织后仍然位于新序列中的奇数位或者偶数位，从而实现对所有信息比特的等过失保护来提高译码性能。为了提高编码效率，通常对Turbo码的编码输出进展删余压缩。如果采用不当的交织方式，则有可能出现对信息为保护不均的情况，从而影响码字的纠错性能。螺旋奇偶交织器可以很好的保证交织器的保奇偶性。3)去相关性经螺旋奇偶交织器交织后相邻码元距离很大，比行列交织器去相关更加彻底。这样使交织后的码元的码距扩大、相关性变小，Turbo码的编码输出更近似随机长码。综合交织后的效果和硬件实现的复杂度，本文Turbo码的编译码器中决定选用这种交织器进展交织与解交织。§2.4Turbo码译码器原理Turbo码获得优异性能的根本原因之一是采用了迭代译码，通过分量译码器之间软信息的交换来提高译码性能。对于Turbo码这样的并行级联码，如果分量译码器的输出为硬判决，则不可能实现分量译码器之间软信息的交换。如果分量译码器能够提供一个反映其输出可靠性的软输出，则其它分量译码器也可以采用软判决译码，从而系统的性能可以得到进一步提高。为此，人们提出了软输出译码的概念和方法，即译码器的输入输出均为软信息。软输出译码实现了解调器和分量译码器之间的软信息转移，系统性能可以得到很大改进。在介绍Turbo码译码器之前，首先介绍一下硬判决与软判决的概念。硬判决和软判决是指译码的时候对接收到的比特进展量化的两种形式。对于硬判决译码解调器供给译码器作为译码用的每个码元只取0或1两个值。在调相和相干解调系统中，假设0、1信号的电压为，则相当于匹配滤波器输出端的判决门限取0。假设接收电压的幅度小于0，则解调器输出为0；假设大于或等于0，则输出1。例如，采用调制电压为士5V的BPSK调制，如果码元为0，则调制成－1发送；假设码元为1，则调制成+1。调制后的－1/+1在信道中传输，由于噪声的影响，序列值会发生变换。如果在接收端收到3V和0.3V两个脉冲电压，硬判决方式会将这两个脉冲都判决为二进制信息1，尽管第二个脉冲看起来离二进制1的标准还差很远。硬判决不可防止地会产生一些不恰当的判决，这种判决结果当然会损失掉接收信号中所包含的有用信息。为了充分利用接收信号波形中的信息，使译码器能以更大的正确概率判决所发的码字，就把解调器输出的抽样电压进展分层或量化。因而由解调器输出供给译码器的值就不止两个，而有Q(通常Q=)个。另一方面假设译码器直接利用解调器输出的未量化的模拟电压或其变换进展译码，称为模拟译码。无论译码器利用Q进制序列译码，还是利用模拟量的模拟译码，统称为软判决译码(或简称软译码)。通常，译码器利用附加的软判决信息进展软译码时要比硬译码能得到额外的2～3dB的增益。Turbo码译码器由两个一样的软输入软输出(SISO)译码器、交织器和相应的解交织器组成，常用的Turbo码译码构造如图2.6所示。其中SISO译码器的作用是完成RSC编码器的译码，也是Turbo码译码器中的核心模块，其性能直接影响整个译码器的性能。软输入指的是译码模块的输入信息为经过量化的解调数据，而不是判决后的二进制序列0和1。软输出则指的是译码模块的输出值也不是判决后的二进制，对于接收序列进展译码后得到一个似然概率值，因此最后在输出之前还要经过硬判决。Turbo码译码器中的交织器与编码器中的交织序列是一致的，在编码器中，交织器的作用是使两个RSC编码器趋于相对独立；而在译码器中，交织器和相应的解交织器则是连接两个SISO译码器的桥梁。译码器局部没有包括量化，它是编码器与译码器中间的局部。接收到的信息序列和校验序列、都是经过解调器解调和量化过的序列，而不是二进制的0和1。这里没有多做说明，在第三章的算法局部和第四章的量化局部将有详细介绍。图2.6Turbo码的迭代译码构造Turbo码译码器的完整译码过程为：首先对从信道接收到的序列经串/并转换，别离出信息序列和校验序列、〔对于码速为1/3的Turbo码，两个RSC编码器输出的校验序列被完全发送，因此在接收端不需要改动，而对于其它码速的Turbo码，比方1/2码速的两个校验序列经过删余矩阵后，分别被删除了局部校验位，因此在接收端对应位应填0〕。译码器1输入的是先验概率信息，即是译码器2的外部信息的交织信息〔对于第一次迭代过程，初始值置0〕、接收的未编码信息序列〔以交织器长度为单位帧长输入〕和校验序列，经SISO1译码后输出后验概率〔即外部信息〕。由于外部信息与先验信息及输入响应的系统信息无关，而且译码器1没有利用校验序列，所以译码器1的输出仅在交织后作为译码器的先验信息输入，而不能用作对信息序列的判决。而译码器2的输入包含了经过交织后的信息序列、校验序列的数据和先验信息，是译码器1的外部信息交织后的数据。经过假设干次迭代后，译码器2的软输出〔似然函数比〕L2经过解交织，并作硬判决，就得到输入信息序列Turbo码的译码输出结果。上面介绍的译码过程可以概述如下：1、第一次迭代，首先采用SISO1译码，设先验信息为0，译码输出软信息，同时计算得到外部信息。SISOl输出的外部信息通过交织以后作为先验信息送入SISO2译码，译码输出软信息L2的同时计算得到外部信息。2、第二次迭代，将第一次迭代过程中SISO2计算得到外部信息通过解交织作为先验信息送入SISO1译码，译码输出外部信息再次交织作为SISO2译码输入先验信息，再次译码输出外部信息。3、如此不断的迭代，直到符合迭代停顿准则或者预先设定的迭代次数，则迭代停顿。最后根据SISO2译码输出的软信息L2作硬判决得到译码比特序列，则本次译码过程完毕。Turbo码译码两个分量译码器采用的是软输入软输出(SISO)译码器，SISO译码算法的选择是保证最正确译码的关键所在，也是Turbo译码器中的核心模块。最大后验概率(MAP)算法可以使Turbo译码的误码率最小，因此，MAP算法是Turbo码的最正确译码算法，下一章将介绍这一算法的根本原理。§2.5Turbo码性能的分析§影响Turbo码性能的因素就Turbo码在移动通信系统应用来说，关注的焦点在以下三个方面，评价Turbo码性能的标准也主要取决与以下几个因素：1、迭代次数Turbo码译码器需要屡次迭代才能有效发挥其优越性，到达一定的误码率水平。但是随着迭代次数的增加，BER性能提高幅度不断的减小。在进展一定次数的迭代后，BER趋向重合，出现平板效应(Flooreffect)。对*一固定码率而言，当交织长度N较小时，BER仅在迭代3到5次后变化就很小。然而，随着N的增大，迭代次数的增加就会带来明显的增益，这时让BER重合所需要的迭代次数就会变多。并且随着Turbo码译码算法中迭代次数的增加，这必然会引人了较大的时延，这在传输实时数据业务(如图象、IP、电视会议等)中是一个较严重的问题。通过研究说明，普通译码过程中迭代次数要到20～30次才能饱和，迭代的性能才可以充分发挥，这与实际应用有矛盾。要在不影响译码性能的原则下，尽量减小迭代次数，降低译码时延。2、交织长度在一样信噪比、码率、约束长度和迭代次数下，随着交织长度N的增加，误码率BER下降。在高信噪比时，BER近似与交织长度成反比，因此交织长度对Turbo码性能的影响不可忽略。当交织长度很大时，因为码字的随机性，各种交织器的性能逐渐趋于一致。但在移动通信系统中，因为延时和硬件复杂性关系，交织器长度不可能很大。3、码率R在一样信噪比、交织长度、约束长度和迭代次数下，码率R越小BER越低。当码率由1/2减小到1/3时，在BER为～附近可获得0.5～0.8dB的编码增益。4、生成多项式通常生产多项式对BER的影响不大，但随着BER的下降它的影响将变得明显。总的来说，约束长度N较大的码生成多项式性能较好，但是它是以复杂度的指数增加为代价的。综合硬件实现复杂度及Turbo码性能考虑，一般人们选择的约束长度N都不是很大。§Turbo码性能的物理解释C.Berrou在1993年提出Turbo码时给出的是性能的模拟结果，而不是理论的分析。此后掀起了Turbo码的热潮，陆续有文章在一定程度上对Turbo码的机理进展理论的解释，但直至目前，对Turbo码的理论研究还远远不够。Turbo码的性能是由码构造、最小距离及距离谱等诸多因素决定，在计算误比特率时，还与码字中包含的信息比特数有关。对于Turbo码，虽然理论上的定量分析还远没有弄清，但粗略的物理解释还是有一些研究的。已经知道，一种编码的误码性能取决于其码距，如A和B两个码字距离越远，把B错译为A的概率越小。Turbo码采用并行构造的级联系统码，两个并行编码码分别对交织前后的信息序列进展编码，得到相应的校验序列。显然，影响误码性能的主要是低重量的信息序列编码后的校验码重。对于不同的低重量信息序列，经过一次分量编码(卷积码)后的校验重量是不同的，而单靠卷积码的码重是缺乏以提供接近极限的译码性能的。但假设大局部具有低校验重量的信息序列经交织后再次编码可获得较高的校验重量。从上述物理解释可直接得到一个重要结论：用递归码作为分量码要优于非递归码，在非递归码的低重量信息序列编码中，单错事件(即错误路径从离开到返回正确路径只有一个信息位错)的概率较大，而第一层码中的单错事件经交织后也会在第二层码中以很大的概率产生单错事件。递归码不会发生单错事件，其双错事件的两个错码经交织后会离得很远，从而产生很大的校验位错误，因而从总的码重分布来看更集中在平均码重附近。§2.6本章小结本章详细介绍了Turbo码的根本知识。首先介绍了Turbo码的原理，接着说明了编码器的构造，包括分量编码器、交织器、删余矩阵、复接器等。其中详细介绍了分量编码器的原理及其构成、交织器的作用及各种交织器的特点。然后介绍了译码器的原理及其构造，并通过构造图简单说明了译码的过程。最后，分析了影响Turbo码性能的因素，对其优异性能给了一些物理解释，并得出一些结论。-.z第三章Turbo码译码算法Turbo码的一个重要特点就是在译码时采用了迭代译码的思想，迭代译码的复杂性是随着信息序列的大小增加而呈线性增长。为使Turbo码到达比拟好的译码性能，分量码译码必须采用SISO算法，从而实现迭代译码过程中软信息在分量码之间的交换。Fomey等人已经证明了最优的软输出译码器应该是后验概率(APP,APosterioriProbability)译码器，它是以接收信号为条件的*个特定比特传输概率。Turbo码系统采用多级迭代的译码构造，子译码器间是软输入、软输出的形式。子译码器中的SISO算法是最核心的容，所以本章介绍Turbo码译码中常用的MAP算法及对数域上的简化算法、SOVA译码算法，分析了各种算法的特点，并从不同方面对Turbo码性能进展了改善。§3.1最大似然译码原则香农编码定理中已经指出,除了随机编码外,采用最大似然译码算法也是获得较低误码率的一个重要环节。假设信息序列为U，经过编码器编码后发送的码字序列为C，译码器接收码字序列为R，译码器输出的估值序列为,由于码字M与C之间存在着一一对应的关系，所以这等价于译码器根据R产生一个C的估值序列。显然，当且仅当＝C的时候，＝M，这时译码器正确译码。如果译码器输出的,则译码器产生了错误译码。之所以产生错误译码是由于信道干扰严重，超过了码本身的纠错能力〔这里不考虑设备故障及人为因素〕。当给定接收序列R时，译码器的条件错误概率定义为：〔3-1〕所以译码器的错误概率为：〔3-2〕P(R)是接收R的概率，与译码方法无关，所以译码错误概率最小的最正确译码原则是使P(R)〔3-3〕因此，如果译码器对输入的码元R,能在个码字中选择一个使，最大的码字作为C的估值序列,则这种译码规则一定使译码器输出错误概率最小，称这种规则为最大后验概率译码。由条件概率的贝叶斯公式〔3-4〕可知，假设发端发送每个码字的概率均一样，且由于与译码方法无关，所以〔3-5〕对于离散无记忆信道而言〔3-6〕这里的码字为，一个译码器的译码规则假设能在个码字C中选择一个使〔3-5〕式成为最大，则这种译码规则称为最大似然译码〔MLD〕，称为似然函数，相应的译码器称为最大似然译码器，由于对数函数的单调性，因此〔3-5〕式与〔3-6〕式可以写成，.〔3-7〕称为对数似然函数或似然函数。对于离散无记忆信道，最大似然译码是使译码错误概率最小的一种最正确译码准则或方法，但此时要求发端发送每一码字的概率均相等，否则MLD不是最正确的，一般均认为近似相等。§3.2MAP译码算法MAP算法最初由Bahl,Cocke,Jelinek和Raviv等在1974年提出的，为了纪念它的提出者，该算法也叫BCJR算法[23]。由于MAP算法实现起来比拟复杂，计算量非常大，因此在Turbo码的出现之前并没有得到广泛应用。直到1993年Turbo码的创造者在其最初的Turbo迭代译码方案中采用了修正的MAP算法，人们才重新开场研究该算法，并证明了此算法是实现Turbo迭代译码最好的次最优算法。MAP算法是基于码字格图的软输出译码算法，目的是使比特错误概率最小[24]。以码速为1/2的串行译码器为例，设输入编码其的信息序列为N个互不相关的信息位，编码其输出序列为,其中，，为信息位，即；为编码输出校验位。为加强对噪声的抵抗能力，编码输出序列在送到高斯信道之前，先经过二进制调制，其映射关系为：〔3-8〕这样码元与字符构成一一对应的关系：，则在译码过程中可以通过对数似然比的正负号直接判定信息值。对于BPSK调制，发送符号与码字的关系为〔3-9〕其中为编码输出信号，，，为k时刻的输入信息比特，为k时刻编码输出码字。在通信理论研究中，高斯信道模型是最重要的信道模型之一[25]，因此一般在模拟时都采用该信道模型。接收信号用表示。其中〔3-10〕本文为了计算的方便，令＝1，则〔3-11〕其中和服从均值为0，方差为的独立同分布高斯随机变量，、分别对应于发送端的第k个系统比特和第k个信息校验比特；、分别对应于接收端的第k个接收系统信息序列和第k个接收校验序列。在接收端，接收采样经过匹配滤波器之后得到的接收序列为,经过串/并变换后得到下面3个序列。系统接收信息序列：用于分量译码器1〔与分量编码器1相对应〕的接收校验序列：和用于分量译码器2〔对应于分量译码器2〕的接收校验序列：其中*些校验比特在编码过程过删余矩阵被删除，则在接收校验序列的相应位置以“0〞来填充。MAP算法的译码器采用串行译码。根据最大似然译码原理，如图3.1所示。译码器的主要任务就是计算在接收采样条件下不同发送符号的概率，即，而后将接收采样判决为概率值最大的信息符号，即：〔3-12〕其中R为接收符号，为k时刻的输入信息比特。图3.1软输入软输出译码框图MAP算法的目的时根据接收序列估计栅格图上两个时刻所以转移的概率，并由此可求出每一个信息码元的软输出〔似然概率比〕。对于每个被译比特，其相应的似然概率比为[26]：〔3-13〕根据的值进展判决为：设k时刻编码器的状态为，我们得到：〔3-14〕为了计算，需要定义三个重要的参数：，和。栅格图中的每一个分支对应的，和的值，本文分别把叫做前向状态向量，叫做后向状态向量，叫做分支向量。定义：〔3-15〕〔3-16〕根据贝叶斯公式可得：〔3-17〕〔3-18〕和可以通过迭代的方法求得，下面将详细进展介绍。首先说明怎样计算，分支向量的表达式依赖于传输信道特性，在这里本人只研究对于加性高斯白噪声〔AWGN〕信道。分支向量对应栅格〔如图2.4所示〕中从k时刻到k＋1时刻，编码器初始状态为m，输入信息比特为i的分支。在接收端收到的经过信道后带有噪声的信息为，栅格图中的每一个分支都有与之对应的分支向量，对于AWGN信道有[27]：〔3-19〕式中K表示常数，i表示编码器k时刻的输入＝i，表示k时刻状态为m，编码器输入为i时的编码输出，表示上一个分量译码器k时刻输出的外部信息。叫做前向状态向量，它代表在k时刻，当输入为i时，从状态m转移到下一状态矢量，可通过下式计算：〔3-20〕是在前面定义过的分支矢量，表示编码器当前状态为m且前一次输入为j时编码器的上一状态。只要对进展正确的初始化，所有的都能正确计算出来，一般把作如下初始化处理：,叫做后向状态矢量，它表示在时刻k，当输入为i，从状态m转移到下一状态的状态矢量。它的表达式类似于，但是是通过反向迭代运算得到的，即在时刻N-1初始化，由时刻N-1反向计算到时刻0，的递推公式为：=〔3-21〕为以前定义过的分支向量，表示编码器当前状态为m且输入为i时编码器的下一状态。图3.2表示了和递推过程的栅格图，向量时从前往后依次计算得到的，而向量的计算是从后往前逆向进展的。只要正确初始化，可通过迭代计算所有的值。通常把做以下初始化：对于其它的所有m和i。图3.2和递推示意图从上面的介绍我们知道，MAP算法的运算步骤有：第一步：使用式3-19计算并存储分支向量。第二步：在k＝N-1时刻，初始化。第三步：从k＝N-2时刻开场一直到k＝0时刻，对每一状态使用式3-21计算并存储的值。第四步：在k＝0时刻按照前面的方法初始化。第五步：从k＝1时刻到k＝N－1时刻对于每一状态使用式3-20计算并存储。第六步：有前面计算所的的每一时刻各个分支的，，，可计算从k＝0到k＝N-1时的。第七步：对每一个做硬判决得到。如果使用前文所定义的公式计算，，和,使用MAP算法计算得到一个信息比特所需的计算量如下：一计算需要：(1次加法和2次乘法)一计算需要：(1次加法和2次乘法)一计算需要：n次幂运算和－l次乘法，n是每个信息比特经过编码后产生的总的码字个数，对于本文所用的编码器n=2。―计算需要：1次对数和1次除法运算，2(－1)次加法和2次乘法运算。因此，对于每一个信息码元译码时所需的运算量为：一n+1次幂运算(幂运算和对