DSP卷积码的维特比译码的分析与实现

PAGE22PAGE21编号：《DSP技术与应用》课程论文卷积码的维特比译码的分析与实现论文作者姓名：____________作者学号：_________所在学院：所学专业：________导师姓名职称：___论文完成时间：_目录TOC\o"1-4"\u摘要： 10前言 21理论基础 21.1信道理论基础 21.2差错控制技术 31.3纠错编码 41.4线性分组码 52卷积码编码 72.1卷积码概要 72.2卷积码编码器 82.3卷积码的图解表示 82.4卷积码的解析表示 113卷积码的译码 143.1维特比译码 153.2代数译码 173.3门限译码 184维特比译码器实现 184.1TMS320C54系列DSP概述 184.2Viterbi译码器的DSP实现 194.3实现结果 215结论 21参考文献 22卷积码的维特比译码的分析与实现摘要：针对数据传输过程中的误码问题，本文论述了提高数据传输质量的一些编码及译码的实现问题。自P.Elias首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。在与分组码同样的码率R和设备复杂性的条件下，无论从理论上还是从实际上均己证明卷积码的性能至少不比分组码差，且实现最佳和准最佳译码也较分组码容易。目前，卷积码已广泛应用在无线通信标准中，其维特比译码则利用码树的重复性结构，对最大似然译码算法进行了简化。本文所做的主要工作：首先对信道编码技术进行了研究，根据信道中可能出现的噪声等问题对卷积码编码方法进行了主要阐释。其次，对卷积码维特比译码器的实现算法进行了研究，完成了译码器的软件设计。最后，结合实例，采用DSP芯片实现卷积码的维特比译码算法的仿真和运行。关键词：卷积码维特比译码DSPConvolutionalcodesandViterbidecodinganalysisandrealization(SchoolofPhysicsandElectronics,HenanUniversity,HenanKaifeng475004,China)Abstract:Consideringtheerrorbitproblemduringdatatransmission,thisthesisdiscussedsomecodingsanddecoders,aimingatenhancingtransmissionperformance.FromP.Eliasfirstgavetheconceptofconvolutionalcode,ithasshowits’greatadvantage.Underthesameconditionandthesamerateofblockcode,theperformanceofconvolutionalcodeisbetterthanblockcode,andit’seasiertoimplementthebestdecoding.Convolutionalcodeshavebeenwidelyusedinwirelesscommunicationstandards,theViterbidecodingusingtherepetitivestructureofthecodetree,themaximumlikelihooddecodingalgorithmhasbeensimplified.Majorworkdoneinthisarticle:First,thechannelcodingtechniqueshavebeenstudied,themaininterpretationoftheconvolutionalcodeencodingmethodaccordingtothechannelmaybenoiseandotherissues.Secondly,theconvolutionalcodeViterbidecoderalgorithmhasbeenstudied,thesoftwaredesignofthedecoder.Finally,withexamples,simulationandoperationoftheDSPchipconvolutionalcodes,Viterbidecodingalgorithm.Keywords:convolutionalcodeVltebridecoderDSP0前言随着数据处理、计算机通信、卫星通信以及高速数据通信网的飞速发展，用户对数据传输的可靠性提出了越来越高的要求，因此如何在保证数据传输速率的前提下，提高传输数据的可靠性，就成为一个迫切需要解决的问题。数字信号在传输过程中不可避免的要受到干扰的影响，因而信息数据会发生误码。严重时会干扰系统的正常工作。根据干扰对数据传输影响的不同干扰可分为随机干扰和突发干扰。其中，电子热噪声产生的干扰可以看作是随机的高斯白噪声，它对信道主要的影响是产生码元的随机错误。脉冲干扰和同频干扰对信道的影响会产生码元的突发错误，如连续出现多个。或多个I。其他干扰如衰落和多径干扰对信道同时产生随机和突发错误两种影响。要提高系统数据传输的可靠性，可以在分析其来源的基础上，尽可能对各干扰源采取对应措施使之减小干扰，同时可以改善信道性能，增加接收端的信噪比或是采用抗干扰能力强的调制解调方式。在上述条件己确定时，针对某一特定的通信系统，应分析信道干扰产生的主要原因，有针对性的应用纠错或检错编码以及相应的技术如反馈重传等来提高传输数据可靠性的方法，即在数据传输时进行差错控制。目前，信道编码的应用几乎遍及数据通信的各个方面，关于信道编码的理论和应用研究也有了新的发展。1理论基础1.1信道理论基础通信的目的是传输信息。通信系统一般由信源，信道，信宿组成。信道是一种物理媒质，用来将来自发送设备的信号传送到接收端。信道既给信号以通路，也会对信号产生各种干扰和噪声。数字信号在传输的过程中，由于信道传输特性不理想以及加性噪声的影响，导致信号波形失真，接收端会不可避免地产生错误判决。按照加性干扰引起的错码分布规律的不同，信道可以分为三类，即随机信道、突发信道和混合信道。在随机信道中，错码的出现是随机的，而且错码之间是独立统计的。例如，由高斯白噪声引起的错码就具有这种性质。在突发信道中，错码是成串集中出现的，即在一些短促的时间段内会出现大量错码，而在这些短促的时间段之间存在较长的无错码区间。这种成串出现的错码成为突发错码。产生突发错码的主要原因之一是脉冲干扰，例如电火花产生的干扰。信道中的衰落现象也是产生突发错码的另一个主要原因。既存在随机错码又存在突发错码的信道，成为混合信道。1.2差错控制技术针对传输信道的不理想，为提高数字传输可靠性就要考虑到差错控制措施了。它的基本思想是通过对信息序列作某种变换，在信息序列中插入若干由发送信息序列生成，但又不是发送者发出的监督码元，使原来的信息序列产生某种相关性，在接收端就可以利用这种相关性来检查并纠正信息序列在传输中所产生的差错。随着差错控制技术的完善和集成电子技术的发展，这项技术不仅已成功地应用于各种通信系统，而且在计算机，磁记录与存储中的使用也日益广泛。针对不同类型的信道，差错控制技术主要分为以下四种。（1）前向纠错（FEC）发送端对信息码元进行编码处理，使发送的码组具有纠错能力。接收端收到这些码序列之后，通过译码能自动发现并纠正传输中出现的错误。这种方法不需要反向信道，特别适合于只能提供单向信道的场合。由于接收端能自动纠错，不会因为发送端反复重发而延误时间，系统实时性好。这种差错控制方式的主要特点是设备较为复杂。（2）检错重发（ARQ）发送端经编码后发出能够检错的码组，接收端收到后如果检测出错误，则通过反向信道通知发送端重发，直至接收端确认收到正确信息为止。所谓检测出错误，是指发现某个或某些接收码元有错，但不一定知道错码的准确位置。这种方式也需要使用反向信道，而且实时性较差。常见的检错重发系统有三种：停发等候重发、返回重发和选择重发。（3）反馈校验（IRQ）接收端将收到的信息码元原封不动地转发回发送端，并与发送的码元相比较。如果发现错误，发送端再进行重发。这种方法的原理和设备都比较简单，无需检错和纠错编译系统，但要使用反向信道。由于每个信息码元至少要被传送两次，所以传输效率低，实时性差。（4）混合纠错（HEC）混合纠错方式是前向纠错方式和检错重发方式的结合。发送端经过编码后发出的码组不但能够检测错误还具有一定的纠错能力。如果接收端收到的码组错误较少，则自动进行纠错；如果错误太多，超出了码的纠错能力但尚未能检测时，接收端通过反向信道请求发送端重发一遍。1.3纠错编码差错控制编码，有时也称为信道编码或纠错编码。不同的编码方法，有不同的检错或纠错能力。有的编码方法只能检错，不能纠错。一般说来，付出的代价越大，检（纠）错的能力越强。这里所说的代价，通常用冗余度表示。1.3.1纠错编码类型差错控制系统中使用的信道编码种类很多，分类的方式也很多。（1）根据差错控制编码的功能，可以把信道编码分为检错码，纠错码和纠删码。检错码只能检测错误；纠错码可以纠正错误；纠删码兼具纠错和检错能力，在发现不可纠正的错误时，可以发出错误指示或将其删除。（2）根据信息码元与附加监督码元之间的关系，可以分为线性码和非线性码。若信息码元与监督码元之间的关系是线性的，即满足一组线性方程，称为线性码；反之，两者若不满足线性关系，则称为非线性码。（3）根据信息码元与监督码元之间的约束方式，可以分为分组码和卷积码。在分组码中，编码后的码元序列没n位为一组，其中k个是信息码元，r个是附加的监督码元，r=n-k,通常记为（n,k）.分组码的监督码元只与本码组的信息码元有关，它又可分为循环码和非循环码。卷积码则不同，虽然编码后的序列也划分为码组，但监督码元不仅与本码组的信息码元有关，还与前面几个码组有约束关系。（4）根据信息码元在编码前后是否保持原来的形式不变，可以分为系统码和非系统码。在编码后的码组中，信息码元和监督码元通常都有确定的位置，一般信息码元集中在码组的前k位，而监督码元位于后r位。如果编码前后信息码元保持原样不变，则称为系统码；反之称为非系统码。系统码的性能与非系统码大致相同，但是在某些卷积码中非系统码的性能优于系统码。系统码的编码和译码相对比较简单，因此得到了广泛的应用。1.3.2常用纠错编码卷积码和线性分组码是现代数字通信中运用最多、最久、最基本的两种纠错码，从技术的角度看，一个通信系统采用什么样的纠错码，应考虑以下几个方面:纠错能力（编码增益）、编码效率、编译码开销（复杂度或可实现性）、编译码延时（实时性）等。1.4线性分组码所谓线性分组码，是指信息码元和监督码元之间的关系可以用一组线性方程来表示的分组码。线性码的概念建立在代数学群论的基础上，因此又称群码。分组码一般用符号（n,k）表示，其中n是码组的总位数，又称为码组的长度，k是码组中信息码元的数目，n-k=r为码组中的监督码元数目，或称监督位数目。……K个信息位 r个监督位 码长n=k+r图1.4.1在分组码中，吧码组中“1”的个数称为码组的重量，简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。我们把编码中各个码组之间距离的最小值称为最小码距（）。一种编码的最小码距的大小直接关系着这种编码的检错和纠错能力：（1）为检测e个错码，要求最小码距：（2）为了纠正t个错码，要求最小码距：（3）为纠正t个错码，同时检测e个错码，要求最小码距：奇偶监督码就是一种简单的线性分组码，例如在偶校验是，它的信息码元和监督码元满足以下线性关系：（1.4.1）上式表示采用偶校验时的监督关系，称为监督方程式。接收时为了检查传输过程中是否出现错误，需要将所有码元的模2加再计算一遍，即：（1.4.2）式中，s被称为校正子或伴随式。如果s=0表示接收码组正确；如果s=1表示出现误码。由于只有1位监督码元，随意只能表示有错和无错两种情况，而不能指出错码的位置。如果有r个监督位，就有r个监督方程式，这是校正子则有中组合，其中1种表示没有错码，其余种组合可以用来指示1位错码的个可能位置。对于码长为n，信息码元数为k的分组码（n,k）来说，如果希望用r=n-k个监督位构造出r个监督方程来指示1位错码的n种可能位置，从而能纠正错误，则要求或（1.4.3）下面通过一个例子来具体说明如何构造这种线性分组码。设分组码（n,k）中k=4，若要能纠正1位错码，要求监督码元数。现取r=3，则n=k+r=7。我们用表示这7个码元，其中是监督位。设，和分别表示与3个监督方程式对应的校正子，而且构成的校正子码组与误码位置的关系如下表误码位置误码位置001101010110100111011000无误码表1.4.1由上表推出，，和与7个码元的逻辑关系式分别为（1.4.5）编码时使用的监督方程式对应=000的无误码情况，即（1.4.6）利用以上方程，可以得到计算监督码元，和的关系式分别为（1.4.7）信息码元给定之后，直接按上式求出对应的监督码元，可得到（7,4）码的16个准用码组如表信息码元监督码元信息码元监督码元0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111表1.4.2接收端收到每个码组后，计算，和，按照的值确定有无误码以及误码的位置，比予以纠正。例如接收码组为“1101011”时，=001，由表1.4.1可知在位置上出现误码，正确码组应该是“1101010”。可以看出，这种（7,4）码的最小码距，它能纠正1位错误或检测两位错误。错误数再多，则无法检测或出现错纠。2卷积码编码2.1卷积码概要卷积码是1955年由麻省理工学院的伊利亚斯（P.Elias）提出来的，它与前面讨论的分组码不同，属于非分组码。通常，为了达到一定的纠/检错能力和编码效率，分组码的码长较大。由于编译码时必须把整个码组存储起来，因此处理产生的延时随码长的增加而线性增大。而卷积码的信息码元个数k和码长n通常较小，故延时小，特别适合于以串行形式传输信息的场合。与分组码相比，不仅与k个信息码元有关，而且与前面N-1段的信息码元有关。2.2卷积码编码器图2.2.1卷积码编码器的一般形式如图2.2.1所示，它包括:一个由N段组成的输入移位寄存器，每段有k级，共Nk位寄存器；一组n个模2和相加器；一个由n级组成的输出移位寄存器。对应于每段k个比特的输入序列，输出n个比特。由图可知，n个输出比特不但与当前的k个输入比特有关，而且与以前的困一1k)个输入信息比特有关。整个编码过程可以看成是输入信息序列与由移位寄存器和模2和连接方式所决定的另一个序列的卷积，卷积码积由此得名。通常把N称为约束长度。常把卷积码记作n(，k，N)，它的编码效率为R=k/n。2.3卷积码的图解表示下面以图2.3.1所示(2，1，3)卷积编码器为例加以说明。图2.3.12.3.1树状图对于图2.3.1所示的(2，1，3)卷积码编码电路，其树状图如2.3.2所示。这里，分别用abc和d表示寄存器，的4种状态:00，01，10，和11，作为树状图中每条支路的节点。以全零状态a为起点，当地第1位信息时，输出码元，寄存器保持状态a不变，对应图中从起点出发的上支路;当时，输出码元，寄存器则转移到状态b，对应图中的下支路;然后再分别以这两条支路的终节点a和b作为处理下一位输入信息的起点，从而得到4条支路。以此类推，可以得到整个树状图。显然，对于第i个输入信息比特，途中将会出现条支路。单从第4位信息开始，树状图的上半部和下半部完全相同，这意味着此时的输出码元已和第1位信息无关，由此可以看出把卷积码的约束长度定义为N一1的意义。图2.3.22.3.2网格图利用树状图中观察到的重复性，把其中相同状态的节点合并到一起，可以得到一种更为紧凑的图形，即网格图。这种图仍由节点和支路组成，4行节点分别表示.a，b，c，d4种状态;支路则代表了状态之间的转移关系，其中实线支路代表输入信号为“0”，虚线支路代表输入信息为“1”，支路上标注的码元为当前输出。一般情况下，网格图应有种状态，从第N节开始图形同样会出现重复。图2.3.32.3.3状态图取出已经达到稳定状态的一节网络，便得到图3一5()a形式的状态图。如果再把相同的当前状态和下一状态重叠起来，就得到图3一5b()形式的状态转移图。显然，状态图也应该有种可能状态(节点)，每个节点会引出2“条支路，同时也会有条来自其他节点或本节点的支路到达。图2.3.42.4卷积码的解析表示2.4.1生成多项式我们可以用延时算子构成的多项式来表示卷积编码器中各级移存器与模2加之间的连接关系。如果某级寄存器与模2加项链，对应的系数为1；反之则为0.以上述卷积码为例，图2.3.1所示的编码器结构可以用以下两式描述：(2.4.1)其中，变量的幂次等于该级寄存器相对于时间起点的单位延时数。在卷积码中，通常把表示移位寄存器与模2加连接关系的多项式称为生成多项式。有时还可以用二进制或八进制的生成序列来表示生成多项式，即（2.4.2）同理，也可以用延时算子的多项式来表示编码器的输入和输出序列。例如，输入序列“110111”可以表示为(2.4.3)其中，变量的幂次等于该级寄存器相对于时间起点的单位延时数，时间起点则通常选在第一位比特上。卷积编码器的输出序列可以根据生成多项式和输入信息序列的乘积算出。例如，输入序列为“110111”时，可得输出序列的算子多项式为(2.4.4)(2.4.5)由此，输出序列（2.4.6）2.4.2生成矩阵卷积码不是分组码，但是从生成多项式的描述可以看出，它仍属于线性码，同样可由生成矩阵或监督矩阵所完全确定。仍以上述卷积码为例，设编码器的起始状态为全零，则输出序列与输入信息序列之间的关系如下所示：（2.4.7）写成矩阵形式为（2.4.8）所以，该码的生成矩阵就是上式最右边的矩阵（2.4.9）可以看出，生成矩阵是一个半无限矩阵，每一行的结构相同，只是下一行比上一行向右移动了2位，而且前3行就已代表了卷积码的全部特征，故得截短生成矩阵(2.4.10)生成矩阵和生成多项式之间存在确定的关系。式（2.4.2）中已经给出了卷积码的生成序列为（2.4.11）比较式（2.4.9）和（2.4.11），可以发现两者之间的关系为(2.4.12)其中，每个子矩阵由一行两列组成，即推广到一般情况，对于（n,k,N）卷积码，如果其生成序列的一般表达式为（2.4.13）其中，。那么对应的生成矩阵一般形式为(2.4.14)其中，为行列子矩阵，即（2.4.15）卷积码的解析和图解表示方法各有特点。用延时算子和生成序列表示卷积码的生成多项式最为方便；网格图则在分析卷积码的译码算法时非常有用；状态图表明卷积码编码器是一种有限状态的马尔科夫过程，因而可以用信号流图理论来分析卷积码的结构及其性能。3卷积码的译码卷积码的译码方式可以分为两大类：代数译码和概率译码。代数译码时利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑译码，又称门限译码，是卷积码代数译码的最主要的一种方式。大数逻辑译码对于约束长度较短的卷积码最为有效，而且设备较简单。概率译码（又称最大似然译码）则是基于信道的统计特性和卷积码的特点进行计算。首先由沃曾克拉夫特针对无记忆信道提出的序贯译码就是概率译码方式之一；另一种概率译码方式是维特比算法。当妈的约束长度较短时，它比序贯译码算法的效率更高，速度更快，目前得到广泛的应用。3.1维特比译码维特比译码算法是由维特比在1967年提出的，其实质是最大似然译码，但利用了编码网格图的特殊结构，从而降低了计算的复杂性，与完全比较译码相比，它的优点是使得译码器的复杂性不再是码字序列中所含码元数的函数。该算法包括计算网格图上在时刻到达各个状态的路径和接收序列之间的相似度，或者说距离。维特比算法考虑的是，去除不可能成为最大似然选择对象的网格图上的路径，即，如果有两条路径到达同一状态，则具有最佳量度的路径被选中，成为幸存路径。对所有状态都将进行这样的选路操作，译码器不断在网格图上深入，通过去除可能性最小的路径实现判决。较早地抛弃不可能的路径降低了译码器的复杂性。Omura在1969年证明了维特比算法实际上就是最大似然算法。注意，选择最优路径可以表述为选择具有最大似然量度的码字，或者选择具有最小距离的码字。维特比（Viterbi）卷积译码步骤及其特点：接收一段，比较、计算一段，尽早舍弃非最佳路径。（1）丢弃网格图上不可能成为最大似然选择对象的路径；（2）如果有两条路径到达同一状态，则具有最佳度量的路径被选中，称为幸存路径（survivingpath）；（3）最佳度量采用汉明距离。对于（2，1，3）的卷积码来说，设输入码序列M为：其中是k个比特的输入码字，信息序列的周期长度为L×k，0代表k个比特的0，附加在有用的信息码字之后，(K-1)组共有（K-1)×k个0，使译码器归到全零状态。加0的目的：使信息序列能分帧传输，接收序列也能分帧译码。译码器网格图如下图3.1.1译码步骤为：从状态a开始，对于某一时间单位t=，(j=1，2，…)，计算进入每一个状态的部分路径与接收码字Z之间的度量（距离）；j增加1，计算此时刻进入各状态的部分路径度量，并挑选出一条度量值最佳的路径，作为幸存路径；如果j<L+（K-1），重复第上一步；否则停止。如果网格图上有两条路径在某一个状态合并，在寻找最佳路径时，一般总可以舍弃这两条路径中的一条。幸存路径选择如下图：图3.1.2通过路径合并，可以保证路径数不会超过状态数。在每次删减之后，都只有4条路径。随着周期性的加入0比特，可以使路径逐渐减少，最后得到一条译码路径。3.2代数译码代数译码是从码字本身的代数结构出发，不考虑信道统计特性，在每次的计算循环之内，可全部译出一个码的支路。在信道传输中码字产生了错误，如果错误图样是已知的，则一定满足.(R为接收码元序列，C为发送码元序列，E为误码序列)根据码元信息位与监督位的关系，一个接收的码字有没有错误可以用监督矩阵H来检验，，R、C、E之间有如下关系式(3.2.1)因为C是一个码字，所以有，则。令或，称S为伴随式或校验子。当时，则判无错。当时，则判有错。因此可以利用伴随式S的内容对接收序列进行检错和纠错。伴随式与信道所产生的错误图样有关，而与发送的是哪一个码字无关。任何一个错误图样都可由公式(3.2.1)算出相应的伴随式。译码器的任务就是根据伴随式来确定错误图样，得到最可能发送的码字C=R+E。适用于代数译码的卷积码是具有快检特性的系统卷积码。代数译码方法很多，且各有特点和使用场合，常用的有门限译码法。3.3门限译码对分组码适用的门限译码、或大数逻辑译码也可适用于卷积码。因此卷积码的门限译码与分组码的门限译码是完全相同的。门限译码可以用比较简单的设备获得1至3dB的编码增益。卷积码的门限译码基于正交一致校验和的概念。任何伴随比特或伴随比特的和可以表示成一致校验和。若接收序列是一码字，则信道错误序列也是码字，所有伴随比特，因而所有校验比特的和必为0，否则某些校验和将不为零。选择码生成式时将一组J个正交估计进行简单的大数表决，并由此解出判断一个差错符号的一致校验方程式，一个或更多的伴随式符号相加，可以得到估计。门限译码相对于卷积码的概率译码来说其对给定的信息组的最终判决只根据接收组的一个约束长度作出。4维特比译码器实现4.1TMS320C54系列DSP概述C54系列DSP具有很高的操作灵活性和速度。它具有先进的修正哈佛结构（一条程序总线、三条数据总线、和四条地址总线）、专门硬件逻辑的CPU、片内存储器、片内外设和专用的指令集、将C54系列DSP的CPU和片内存储器与外设配置组合在一起的螺旋结构，使它可满足电子市场众多领域的应用要求。C54系列DSP具有以下优点：（1）增强的哈佛结构。具有一条程序总线、三条数据总线和四条地址总线，使系统的性能大大增强。（2）具有高度平行和带有专门硬件逻辑的先进CPU设计。（3）为快速算法而设计的高度专用的指令系统以及优化的高级语言开发系统。（4）模块化结构设计。（5）高性能和低功耗的先进IC工艺技术。（6）新的静电设计结构而获得的低功耗和增强的抗辐射能力。4.2Viterbi译码器的DSP实现DSP上实现Viterbi译码分成三个部分：初始化、度量值更新和回溯跟踪。Viterbi译码的处理过程如图5-6所示。 分支度量蝶形运算简化初始化度量值更新回溯跟踪初始化度量值更新回溯跟踪输入 译码输出程序流程大概如下：对每一帧{初始化度量值对每一个符号{ACS（加比选单元）对每一个状态{根据输入，对每一条可能路径计算分支度量；对一条路径计算路径度量值；选择并保存最小度量值；保存幸存路径的表示；}}回溯{对一帧的每一比特{对每一状态计