Matlab实现turbo编译码毕业论文.doc 31页

'Matlab实现turbo编译码毕业论文目录摘要IABSTRACTII1信道编码11.1信道编码及信道编码的提出11.2信道编码的发展历程11.3信道编码的分类42相关基本概念和常识52.1关于纠错码的基本概念52.2卷积码初步63Turbo码的产生及研究现状73.1Turbo码的产生背景73.2Turbo码的研究现状84Turbo码编码104.1编码器各部分介绍104.2编码原理及算法115Turbo码译码155.1译码器结构155.2Turbo码迭代译码基本原理165.3MAP(maximumaposteriori)算法176Matlab介绍及仿真结果216.1Matlab程序设计语言概述21 6.2程序仿真结果237结束语28致谢29参考文献30 1信道编码1.1信道编码及信道编码的提出所谓信道编码，就是按照一定的规则给待传送的数字序列{d}增加一些多余的码元，称之为监督码元，使不具有规律性的数字序列{d}变换为具有某种规律性的数字序列{c}，又称为码序列。经变换后得到的码序列中，信息序列的诸码元与多余码元之间是相关的，接收端的译码器则根据这种相关性来检测和纠正传输过程中产生的差错。长期以来，人们一直在努力探索着如何安全可靠的进行信息传输的途径。1948年，香农（C.Shannon）在他的开创性论文《通信的数学理论》（Amathematicaltheoryofcommunication）中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的“有扰信道编码定理”，奠定了信道编码（即纠错码）的基石。定理指出：在有噪声的信道环境下，只要信源的信息速率不超过信道容量，就可以找到一种编码方法，使信息的传输速率任意逼近信道容量，而传输的错误概率任意逼近于零，或者传输的失真度能够任意的逼近给定的要求，即实现可靠通信。在这里，香农定理指出了信道编码在实现有效、可靠通信方面的重要地位和作用，并从理论上为信道编码的发展指出来努力的方向。由此，人们还认识到，没有必要建立性能特别好的耗费特别高的信道去保证通信的可靠性，只需应用适当的编码技术便可以达到目的，而且更为经济。自此以后，汉明（Hamming）、斯列宾（Slepian）、普兰奇（Prange）等人在50年代初，根据香农的思想，给出了一系列设计好码和有效译码的方法。1.2信道编码的发展历程迄今为止，信道编码已有50多年的历史，其发展过程可分为以下几个阶段：50年代和60年代里，人们主要致力于寻找能保证差错概率为任意小的码及译码算法。首先得到重视的是分组码。人们利用代数方法逐步认识了Hamming码、BCH码、RS码等分组码，并发现了一些有效的译码算法。后来，人们又着重用概率方法对卷积码的结构进行研究，提出来Viterbi算法之类的译码算法方法。同时，还提出了一些结构特殊或功能特殊的码，如错误定位码、级联码（concatenatedcode ）、收缩码、不等错误保护码等等。G.D.Forney在1966年提出了一种由短码构造长码的方案：串行级联码方案。如下图所示。级联码的性能良好，译码技术简单，具有实用潜力。 图1-1串行级连码编码器框图图1-2串行级连码译码器框图在70年代和80年代，人们不仅对分组码、卷积码分别进行了更深入的研究，而且将代数方法和概率方法结合起来，设计出了几种码字很长、性能较好的码族，使得信道编码理论向着C.Shannon指出的方向进一步推进。这时，人们开始将注意力转向差错控制码在实际通信系统中的应用，设计出来很多适用的差错控制方案。这期间，人们对级联码也进行了初步考察。这些研究为今后信道编码的广泛应用打下了理论基础。80年代以来，信道编码无论在理论上或是在应用方面都得到空前的发展。在理论上，人们不仅从码的未检出错误概率、重量分布、覆盖半径、球半径等各个方面综合进行研究，以期发现性能更好、译码方案更简单的编码方案、而且对级联码之类的特殊码进行深入分析。人们还将差错控制编码与其他抗干扰技术如调制、扩频、保密等结合起来，再用最优化方法进行讨论分析，研究出一些适合于各种通信系统的最优抗干扰方案。集成电路和计算机技术的发展使差错控制编码在通信系统中得到广泛应用，为了适应某些现代通信的要求，如深空通信、流星通信等，人们又设计出了许多新的编码方案。1993年Berrou提出来当前最热门的一种接近香农极限性能的Turbo码（Turbo－codes），这种码又名并行级联反馈系统卷积码。此码的算法简单，却可以很快达到香农限。 1.3信道编码的分类信道编码方法有多种，一般可以按以下方式对其分类：按照信息码元和监督码元之间约束方式的不同，可以分为分组码和卷积码。若本码组的监督码元仅与本码组的信息码元有关，而与其他码组的信息码元无关，则称这列码为分组码；若本码组的监督码元不仅与本码组的信息码元有关而且还和本码组相邻的前若干个码组的信息码元有关，则这列码成为卷积码。按照信息码元与监督码元之间的检验关系又可以分为线性码和非线性码。若编码规则可以用线性方程组来表示，则称之为线性码，反之，若两者不存在线性关系，则称为非线性码。按照编码后每个码字的结构可分为系统码和非系统码。在系统码中，编码后的信息码元保持原样不变，而非系统码中信息码元则改变了原有的信号形式。按照纠正错误的类型的不同，可分为纠正随机错误和纠正突发错误的码。前者主要用于发生零星独立错误的信道，而后者则用于对付以突发错误为主的信道。 2相关基本概念和常识上一章，简单介绍了信道编码相关的一些情况，在本章中，将介绍有关编码的一些相关概念以及卷积码的编码方法。2.1关于纠错码的基本概念本节中，介绍了一些与信道编码有关的重要的概念知识，这些概念在编、译码理论中非常重要。1、错误图样设发送的是n个码元长的序列C：（）通过信道传输到达接收端（纠错码译码器的输入端）的序列为R：。由于信道中存在干扰，R序列中某些码元可能与C序列中对应的码元的值不同。而在二进制序列中的错误只有0错成1或者1错成0，因此把信道中的干扰也用二进制序列E：来表示，则相应有错误的位取值为“1”，无错的位取值为“0”，而R就是C与E序列模2加的结果，即：。我们称E为信道的错误图样或干扰矢量。2、码字和码率分组码是对每段k位长的信息组，以一定的规则增加个校验元，组成长为n的序列：（），这个序列就称为码字（码组或码矢）。码率是指在一个码字中信息位所占地比重，用R表示，R=k/n。R体现了传输信息的有效性。3、汉明距离和汉明重量汉明距离指两个码字之间对应位取不同值得个数；汉明重量是指一个码字中非零码元的个数；最小汉明距离指的是在各种有用码组中汉明距离的最小值。4、码的抗干扰能力与最小汉明距离之间的关系①若码集中码字间的最小距离满足，则该码集中的码字具有检测e个错误的能力；②若码集中码字间的最小距离满足，则该码集中码字具有纠正t个错误的能力；③若码集中码字间最小距离满足（e>t ），则该码集中的码字具有纠t个错误同时检出e个错误的能力。2.2卷积码初步在当今数字通信系统中大都使用信道编码来提高系统性能。最常用的信道编码是卷积码。一个Turbo码可以看成是二维或多维的卷积码。因此在这里将对卷积码作简单的介绍。卷积码的特点如下：当n和k均较小，且要求纠错能力较强，可使用卷积码。1、卷积码中一个码字（n位）的校验元不仅取决于本码字信息元（k位），而且取决于前m组的信息元。表示为。称为编码记忆，N=m＋1（N为约束长度）；2、译码也需要考虑若干码组的影响方能译出一个码组信息元；3、由于各码组间及码组内相关性较分组码强，卷积码的n、k可用较小的数而获得多位分组码同样的性能。 3Turbo码的产生及研究现状Turbo码是一类新型的信道编码。Turbo码在编码领域里有三大特点，(1)使用递归系统卷积码作为编码器的编码单元；(2)使用随机交织器；(3)在译码器中使用内部信息和外部信息。3.1Turbo码的产生背景1948年香农在《通信的数学理论》中提出了香农第二定理（也称信道编码定理），具体表述为：设信道容量为,对于任何的信息传输速率，都存在长为的分组码可使错误译码概率满足下式：（3-1）式中的指数项是一个在下的的正函数，并且该项只与信道的特性有关。上式说明，对于任何低于的传输速率，可在码率不变的前提下增加分组码的长度，使差错概率为任意小。对卷积码也有类似的界限式，其中由码的约束长度代替。在极限情况下趋向无穷，要求带宽趋向无穷。由信息论的基本知识可知，信道容量（3-2）由于（3-3）由上式可知，当信噪比大于－1.6dB，信道容量C大于信息速率R，此时就可实现高斯白噪声信道下的无误传输。这就是带宽无限高斯白噪声信道的极限传输能力，称为香农限。香农在导出上式时，是以随机编码论证为基础的。该界限是对随机选取编码总体上的差错概率取平均得到的。由于总体中肯定存在一些超过平均性能的码，因此这个定理保证存在一些能达到上式界限的码。 但是需要考虑的实际问题是一、编码定理并未给出构造有效码的方法；二、当要求的差错率很低时，将迫使采用非常长的码，这导致译码算法非常复杂。因此在过去的几十年内，编码领域中的研究工作主要围绕两个关键问题，即寻求不同长度下具有良好性能的码类，以及复杂程度能够接受下的能实现码的固有性能的译码算法。香农理论已经指出，增加分组码的长度或卷积码的约束长度可以提高码的纠错性能。但是由于最大似然译码的复杂度随增加而增加，以至于物理不可实现，这样人们就试图构造出具有大的等效分组长度，性能强大，同时译码算法又不至于过于复杂的码。如乘积码、级联码、大约束长度的卷积码等都是这方面尝试，因此传统的级联码等及其译码与信道的极限之间还有着很大差距。1993年，法国的C.Berrou等提出了一种新的纠错码------Turbo码。Turbo码一经提出，就以其优异的性能被编码界专家认为是近几年来最令人兴奋和最具有潜力的重大发展。Turbo码与以往所有的码的不同之处在于它通过一个交织器的作用，达到接近随机编码的目的，并且使等效分组长度很大。香农指出“随机码”是一种好码，因此Turbo码也必然是一种好码。此外它所采用的迭代译码策略，使得译码复杂性大大降低。它采用两个子译码器通过交换称为边信息（或外部信息）的辅助信息，相互支持，从而提高译码性能。边信息的交换是在迭代译码的过程中实现的，前一次迭代产生的边信息经交换后将作为下一次迭代的先验信息。3.2Turbo码的研究现状自从Turbo码提出以来，Turbo码很快就成为纠错编码界研究的热点。它的研究目前主要集中在以下几个方面：1编码器的研究目前编码器的研究着重于：①子码的选择；②非二元Turbo码，即子码用元码代替二元码；③编码器结构的研究，如提出采用多子编码器结构；④为适应语音、图象等的传输，提出不等能力纠错的Turbo编码，即对信息比特和校验比特的功率分配进行优化。2迭代译码算法的研究目前的一些译码算法存在以下几个主要问题。①虽然由于Turbo码采用了迭代译码的思想，每个迭代单元的译码并不是非常复杂，但是要使误码率达到一定要求，迭代次数必须较多，从而使译码时延增大。如果要将Turbo 码用于语音传输，时延将不可忍受；②译码复杂性随卷积码的约束长度或分组码的码字长度增加而呈指数增加。因此迭代译码算法的研究主要是在保证一定算法性能的前提下，寻找译码复杂性与约束长度无关的算法，并且简化算法，使其便于用硬件实现。同时减少时延，以能用于实时语音通信中。目前的改进集中在以下几方面：(1)通过减少非线性运算减少算法计算量，如提出对数域的MAP算法，使得性能优异的MAP算法便于硬件实现；(2)改进SOVA算法，尤其是减少SOVA算法在短交织长度下和MAP算法的性能差距，使得短交织长度下SOVA算法能以可接受的性能取代MAP算法；(3)采用对偶码的概念译码，避免译码复杂性与约束长度或分组码码字长度成指数关系。(4)改进迭代过程中信息传递的方式，提出了并发（concurrent）算法、双向Viterbi译码方法等，从而加速译码过程;(5)寻找判决迭代收敛的规则，及时结束译码迭代；(6)将神经网络计算器用于Turbo码译码。 4Turbo码编码由于编码方式的不同将直接影响译码的方式、方法，所以，在本章里，将详细介绍有关Turbo码编码器的结构及具体编码方法的算法。Turbo码的基本思想是利用短码构造等效长度意义上的长码。一个典型的Turbo码编码器如图4-1所示。图4-1Turbo码编码器基本结构编码是通过两个相同的编码器和一个交织器组成。第一个编码器直接对信源信息序列进行编码，第二个编码器则对经过交织器后的信息序列进行编码，交织器对输入的原信息序列进行随机交织后输出。在编码时，为使编码器初始状态置于全零状态，需要在信息序列之后加m个比特尾信息（tailbits），而要使两个编码器同步归零，必须设计合适的交织器。（实际上，在本文中后边对SOVA具体实现时，使得第一个编码器最终的状态归零了，而第二个未归零，但仍可以用类似的方法译码）。4.1编码器各部分介绍1成员编码器（componentencoder）成员编码器（componentencoder）也叫子编码器。一般一个Turbo码编码器由两个(可以多个)子编码器和通过交织器的作用并行级联组成.子编码器的结构可以不同,但一般取相同结构,以简化译码.子码可以是卷积码或者是分组码。2交织器（interleaver）Turbo码中交织器的主要作用是减少校验比特间的相关性,进而在迭代译码过程中降低误比特。其基本的原则是:通过增加交织器的长度,可使译码性能得到提高交织器应该使输入序列尽能地随机化,从而避免编码生成码字的信息序列交织后, 编码仍旧生成低重码字,导致Turbo码的自由距离减少。交织器一般有这样几种：分块交织、伪随机交织以及两者结合的交织方式。分块交织分为两种：Ⅰ型，采用行顺序写入、列顺序读出方式；Ⅱ型写入顺序与Ⅰ型交织器的写入顺序一致，但读出顺序是以列的倒序来完成的。即从最后一列向第一列读出，而每一列则是从最后一行向第一行的顺序来读出。伪随机交织器。本文中实现的算法就是采用的这种方式，所以在这里详细的介绍一下。伪随机交织器反映的实际上是一种映射关系。其工作过程是：对于长为n的信息序列，首先标记每个比特的位置，然后生成n个[0,1]之间的随机数，按产生的顺序排列成序列X，每个随机数都对应于信息序列中的信息比特。然后把X中元素按一定的规则重新排列得到新的序列Y，并按Y中元素的顺序读出相应的信息比特，这样就完成了交织。比如伪随机序列[0.76210.45650.01850.82140.4447],它对应信息序列X为[]。将随机序列按升序排列得到[0.01850.44470.45650.76210.8214]，则现在对应的信息序列Y为[]。这样，就完成了交织。4.2编码原理及算法1编码原理如果一个码率为的卷积码的生成矩阵为：(4-1)则其对应的递归系统卷积码的生成矩阵为：(4-2)如以生成矩阵为（也可以表示为g＝[1101；1111]）的递归系统卷积码作为子码，它对应的Turbo码结构如图4-2所示。 图4-2[15,17]递归卷积码编码结构图输入编码器的信息序列为，它一方面直接输入到进行编码,生成系统序列和校验序列，另一方面,U经过交织器后,输入到中进行编码,产生另一个校验序列，这三个序列经复用单元复用后完成编码，得到发送序列。复用单元的作用是调整编码速率,并将并行数据变换为串行数据流。通常系统序列全部传送，校验序列按照收缩矩阵收缩。图示Turbo码编码器可以采用收缩矩阵将编码速率调整到1/2，矩阵的每行对应一个子编码器，第一列和第二列分别对应子编码器输出的第偶数个码元和第奇数个码元。1表示该码元需要传送，0表示不需传送。如果称对原始信息序列编码为水平方向的编码，称对经过交织器后的信息序列编码为垂直方向的编码。在每个方向上，个信息比特经过编码器输出为(4-3)其中，或表示信息比特，表示与该信息比特对应的校验比特，校验比特数取决于系统卷积码的生成多项式。显然(4-4)传输前经过收缩，有一部分校验比特将不予传送，在接收端未被传送的比特位用零填充。从上面的介绍我们可以看到，Turbo码编码部分级联结构和交织器的共同作用，使 Turbo编码接近随机编码，从而保证了Turbo码必定是一种好码。2编码算法1、首先谈一下对生成多项式g的理解。图4-3递归系统码对照递归系统卷积码的一般的编码结构图4-3。如前所述，其中[1,m+1]（其中m是寄存器的数目）。是矩阵g的第一行，可以看成是对应的图5中的反馈环支路；是矩阵g的第二行，可以看成对应的是输出的支路。和分别对应两点的信息。无论还是中的后m个信息位的每一位都分别对应一个寄存器。它们可以看成是标志着一种状态。第一行中的后m位表示产生反馈信息所用到的寄存器，比如说第j＋1位，它对应于第j个寄存器，该位为1表示用到了该寄存器内的信息，即该寄存器有反馈到输出信息的那个加法器，为零则表示没有反馈回去。同理，中的后m位表示产生信息所用到的寄存器。2、编码算法（1）对于encoder1：d＝input；L_info=length(d)；L_total=L_info+m；goto(3)；Y（1，：）＝X；Y(2，：)＝Y；（2）对于encoder2：d＝Y（1，：）（alpha）；％alpha为伪随机交织图样％（是L_total列行向量） L_total＝length（d）；L_info＝L_total；goto(3)；Y(3，：)＝Y；Goto（4）。（3）①state为一m列行向量。初始化为零②ifL_info，＝；elseifL_info