MATLAB实现卷积码编译码-说课材料.doc

MATLAB实现卷积码编译码-精品文档 本科生毕业论文（设计）题 目：MATLAB实现卷积码编译码 专业代码： 作者姓名： 学 号： 单 位： 指导教师： 年 月 日收集于网络，如有侵权请联系管理员删除 目 录前言11. 纠错码基本理论21.1纠错码基本理论21.1.1纠错码概念21.1.2基本原理和性能参数21.2几种常用的纠错码62. 卷积码的基本理论82.1卷积码介绍82.1.1 卷积码的差错控制原理82.2卷积码编码原理102.2.1 卷积码解析表示法102.2.2 卷积码图形表示法112.3 卷积码译码原理152.3.1 卷积码三种译码方式152.3.2 Viterbi译码原理163. 卷积码编译码及MATLAB仿真183.1 Matlab概述183.1.1 Matlab的特点193.1.2 Matlab工具箱和内容193.2卷积码编码及仿真203.2.1编码程序203.3 信道传输过程仿真213.4维特比译码程序及仿真223.4.1 维特比译码算法解析233.4.2 Viterbi译码程序253.4.3 viterbi译码matlab仿真283.4.4信噪比对卷积码译码性能的影响283.4.5码率对卷积码译码性能的影响303.4.6 约束长度对卷积码误码性能的影响313.4.7回溯长度对卷积码误码性能的影响323.4.8 判决方式对卷积码误码性能的影响324. 结论及展望344.1 结论344.2展望355. 结束语36参考文献37致谢38附录39摘要在数字通信系统中，通常采用差错控制编码来提高系统的可靠性。自PElias首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。目前，卷积码已广泛应用在无线通信标准中，如GSM，CDMA2000和IS-95等无线通信标准中。本文简单介绍了纠错码的基本原理，论述了卷积码编译码原理和算法，并通过matlab仿真对卷积码性能进行研究，重点比较分析了不同码率、不同约束长度、不同回溯长度以及不同译码判决方式对Viterbi译码性能的影响，并得出相关结论。关键词：卷积码，Viterbi，Matlab，误码率，数字通信系统AbstractIn digital communication systems, error control coding is usually used to improve system reliability. Since P.Elias put forward the convolutional coding the first time, the coding is still showing strong vitality.,has become widely used in satellite communications, wireless communications and many other communication systemsas a kind of channel coding method. such as GSM, CDMA2000 and has been a wireless communication standards of IS-95.This article introduces the basic principles of error-correcting codes, mainly reasearch the principle of the convolutional code encoding and decoding and the algorithms.Through the matlab simulation, we study the performance of convolutional code, especilly the performance of the viterbi decoding with different bit rates, different Constraint length ,different traceback depthe and different decision types,compare and make conclusions.Keywords: convolutional codes, Viterbi, Matlab, bit error rate, the digital communication system MATLAB实现卷积码编译码前言信道编码是数字通信系统的重要组成部分，随着通信技术的不断发展，信道编码技术也在不断地发展。在通信系统中，信道传输特性不理想以及噪声的存在，会导致接收端出现接收信号的错误，因此用于信道纠错的信道编码是数字通信系统中极为重要的一个环节。二十世纪40年代香农定理的出现为人们指出了纠错码的研究方向。根据香农的有噪信道编码定理，可以推导出一个码率为R 的编码通信系统达到无误码传输状态所必须的最小信噪比的理论极限。这个理论极限通常称为香农限，它说明对一个码率为R的编码通信系统，只有当SNR超过这个极限值时才能获得无误码传输。只要SNR高于这个极限值，香农的编码定理保证了能够获得无误码传输的（可能相当复杂）编码通信系统的存在性。另外，香农证明了在采用无限长的随机编码时，数据可以以接近信道容量的速率几乎无误码的传输，从而为信道编码的研究奠定了基础。 本文主要介绍了信道编码的基本理论，着重研究了卷积码的编码方法和viterbi译码，介绍了MATLAB的使用方法，并编写卷积码的编码和解码程序，通过MATLAB仿真软件对卷积码编解码进行仿真。重点对viterbi译码进行了研究，该算法就是利用卷积码编码器的格图来计算路径度量，选择从起始时刻到终止时刻的惟一幸存路径作为最大似然路径，沿着最大似然路径回溯到开始时刻，所走过的路径对应的编码输出就是最大似然译码输出序列。它是一种最大似然译码方法，当编码约束长度不大、或者误码率要求不是很高的情况下，Viterbi译码器设备比较简单，计算速度快，因而Viterbi译码器被广泛应用于各种领域。1. 纠错码基本理论1.1纠错码基本理论1.1.1纠错码概念纠错码(error correcting code)，在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。为使一种码具有检错或纠错能力，须对原码字增加多余的码元，以扩大码字之间的差别 ，即把原码字按某种规则变成有一定剩余度（见信源编码）的码字，并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收端后，可以根据编码规则是否满足以判定有无错误。当不能满足时，按一定规则确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。检错码与其他手段结合使用，可以纠错。1.1.2基本原理和性能参数纠错码编码的基本思想是在被传输的信息码元中附加一些监督码元，并且使它们之间确定某一种关系，根据传输过程中这种关系是否被破坏来发现或纠正错误。可见这种差错控制能力是用增加信息量的冗余度来换取的。设编码后的码组长度、码组中所含信息码元以及监督码元的个数分别为n、k和r，三者间满足n= k + r，定义编码效率为R = k/n = 1 - r/n。可见码组长度一定时，所加入的监督码元个数越多，编码效率越低。香农的信道编码定理指出：对于一个给定的有扰信道，若信道容量为C，只要发送端以低于C的速率R发送信息，其中R为编码器的输入二进制码元速率，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。可以表示为 (1-1)其中 E(R)称为误差指数，它与R和C的关系如图1-1所示。图1-1 误差指数曲线由定理有如下结论：(1). 在码长及发送信息速率一定的情况下，为减小P可以增大信道容量。由图2-1可知，E(R)随信道容量的增加而增大。由式(1-1)可知，错误概率随E(R)的增大而指数下降。(2). 在信道容量及发送信息速率一定的条件下，增加码长，可以使错误概率指数下降。对于实际应用来说，此时的设备复杂性和译码延时也随之增加。香农的信道编码定理为信道编码奠定了理论基础，虽然定理本身并没有给出具体的差错控制编码方法和纠错码的结构，但它从理论上为信道编码的发展指出了努力方向。我们用3位二进制码组来说明检错纠错的基本原理。3位二进制码元共有8种可能的组合:000、001、010、011、100、101、110、111。如果这8种码组都可传递消息，若在传输过程中发生一个误码，则一种码组会错误地变成另一种码组。由于每一种码组都可能出现，没有多余的信息量，因此接收端不可能发现错误，认为发送的就是另一种码组。如果选其中000、011、101、110 来传送消息，这相当于只传递00、01、10、11四种信息，而第3位是附加的。这位附加的监督码元与前面两位码元一起，保证码组中“1”码的个数为偶数。这4种码组称为许用码组。另外 4种码组不满足这种校验关系，称为禁用码组，它们在编码后的发送码元中不会出现。接收时一旦发现有禁用码组，就表明传输过程中发生了错误。用这种简单的校验关系可以发现1个或3个错误，但不能纠正错误。因为当接收到的码组为禁用码组时，比如为010，无法判断发送的是哪个码组。虽然原发送码组为101的可能性很小(因为3个误码的概率一般很小)，但不能绝对排除，即使传输过程中只发生一个误码，也有三种可能的发送码组即000、011和110。 假如我们进一步将许用码组限制为二种即000和111，显然这样可以发现所有2位以下的误码，若用来纠错，可以用最大似然准则纠正1位错误。可以用一个三维立方体来表示上述3位二进制码组的例子，如图1-2所示。图中立方体各顶点分别表示8位码组，3位码元依次表示x、y、z轴的坐标。zyx(0,0,1)(0,1,1)(0,0,0)(1,1,1)(0,1,0)(1,1,0)(1,0,0)(1,0,1)图1-2 码距的几何解释这里定义码组中非零码元的数目为码组的重量，简称码重。比如100码组的码重为1，101码组的码重为2。定义两个码组中对应码位上具有不同二进制码元的位数为两码组的距离，称为汉明(Hamming)距，简称码距。在前面3位二进制码组的例子中，当8种码组均为许用码组时，两码组间的最小距离为1，称这种编码的最小码距为1，一般记为dmin= l；当选4种码组为许用码组时，最小码距dmin = 2；当用2种码组作为许用码组时，dmin = 3。从图1-2所示的立方体可以看出，码距就是从一个顶点沿立方体各边移到另一个顶点所经过的最少边数。图中粗线表示000与111之间的一条最短路径。很容易得出前例中各种情况下的码距。根据以上分析可知，编码的最小码距直接关系到这种码的检错和纠错能力，所以最小码距是差错控制编码的一个重要参数。对于分组码一般有以下结论： (1)在一个码组内检测e个误码，要求最小码距 (1-2)(2)在一个码组内纠正t个误码，要求最小码距 (1-3)(3)在一个码组内纠正t个误码，同时检测e(et)个误码，要求最小码距 (1-4)这些结论可以用图1-3所示的几何图形简单的给予证明。图1-3 码距与检错和纠错能力的关系图1-3(a)中C表示某码组，当误码不超过e个时，该码组的位置移动将不超出以它为圆心以e为半径的圆。只要其它任何许用码组都不落入此圆内，则C发生e个误码时就不可能与其它许用码组混淆。这意味着其它许用码组必须位于以C为圆心，以e + 1为半径的圆上或圆外。因此该码的最小码距dmin为e + 1。 图1-3(b)中C1、C2分别表示任意两个许用码组，当各自误码不超过 t个时，发生误码后两码组的位置移动将各自不超出以C1、C2为圆心，t为半径的圆。只要这两个圆不相交，当误码小于t个时，根据它们落在哪个圆内可以正确地判断为C1或C2，就是说可以纠正错误。以C1、C2为圆心的两圆不相交的最近圆心距离为2t + l，即为纠正t个误码的最小码距。式(1-1)所述情形中纠正t个误码同时检测e个误码，是指当误码不超过t个时，能自动纠正误码，而当误码超过t个时，则不可能纠正错误但仍可检测e个误码。图1-3(c)中C1、C2分别为两个许用码组，在最坏情况下C1发生e个误码而C2发生 t个误码，为了保证此时两码组仍不发生混淆，则要求以C1为圆心e为半径的圆必须与以C2为圆心t为半径的圆不发生交叠，即要求最小码距 dmin =t+e+1。 可见dmin体现了码组的纠、检错能力。码组间最小距离越大，说明码字间最小差别越大，抗干扰能力就越强。由于编码系统具有纠错能力，因此在达到同样误码率要求时，编码系统会使所要求的输入信噪比低于非编码系统，为此引入了编码增益的概念。其定义为，在给定误码率下，非编码系统与编码系统之间所需信噪比Eb/N0之差(用dB表示)。 采用不同的编码会得到不同的编码增益，但编码增益的提高要以增加系统带宽或复杂度来换取。(2.1.3)纠错码实现纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长n越大,则误码率越小。但n越大，编译码设备也越复杂,且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加；译码的计算量则与码长 n基本无关。可惜，已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展，既使应用比较复杂的但性能良好的码，成本也并不太高。因此，纠错码的应用越来越广泛。 纠错码传输的都是数字信号。这既可用硬件实现，也可用软件实现。前者主要用各种数字电路，主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。硬件实现的速度较高，比软件可快几个数量级。 在传信率一定的情况下，如果采用纠错码提高可靠性，要求信道的传输率增加，带宽加大。因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和半导体存储器等。 在分组码的研究中，谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等，也得到较多的研究.1.2几种常用的纠错码(1) RS编码RS码即里德-所罗门码，它是能够纠正多个错误的纠错码，RS码为（204，188，t=8），其中t是可抗长度字节数，对应的188符号，监督段为16字节(开销字节段）。实际中实施（255，239，t=8）的RS编码，即在204字节（包括同步字节）前添加51个全“0”字节，产生RS码后丢弃前面51个空字节，形成截短的（204，188）RS码。RS的编码效率是：188/204。 (2)卷积码卷积码非常适用于纠正随机错误，但是，解码算法本身的特性却是：如果在解码过程中发生错误，解码器可能会导致突发性错误。为此在卷积码的上部采用RS码块， RS码适用于检测和校正那些由解码器产生的突发性错误。所以卷积码和RS码结合在一起可以起到相互补偿的作用。卷积码分为两种： 基本卷积码: 基本卷积码编码效率为，1/2, 编码效率较低,优点是纠错能力强。 收缩卷积码: 如果传输信道质量较好，为提高编码效率，可以采样收缩截短卷积码。有编码效率为：1/2、2/3、3/4、5/6、7/8这几种编码效率的收缩卷积码。编码效率高，一定带宽内可传输的有效比特率增大,但纠错能力越减弱。 (3)Turbo码1993 年诞生的Turbo 码，单片Turbo 码的编码/解码器，运行速率达40Mb/s。该芯片集成了一个3232 交织器，其性能和传统的RS 外码和卷积内码的级联一样好。所以Turbo码是一种先进的信道编码技术，由于其不需要进行两次编码，所以其编码效率比传统的RS+卷积码要好。 (4)交织在实际应用中，比特差错经常成串发生，这是由于持续时间较长的衰落谷点会影响到几个连续的比特，而信道编码仅在检测和校正单个差错和不太长的差错串时才最有效（如RS只能纠正8个字节的错误）。为了纠正这些成串发生的比特差错及一些突发错误，可以运用交织技术来分散这些误差，使长串的比特差错变成短串差错，从而可以用前向码对其纠错，例如：在DVB-C系统中，RS(204,188)的纠错能力是8个字节，交织深度为12，那么纠可抗长度为81296个字节的突发错误。实现交织和解交织一般使用卷积方式。 交织技术对已编码的信号按一定规则重新排列，解交织后突发性错误在时间上被分散，使其类似于独立发生的随机错误，从而前向纠错编码可以有效的进行纠错，前向纠错码加交积的作用可以理解为扩展了前向纠错的可抗长度字节。纠错能力强的编码一般要求的交织深度相对较低。纠错能力弱的则要求更深的交织深度。 一般来说，对数据进行传输时，在发端先对数据进行FEC编码，然后再进行交积处理。在收端次序和发端相反，先做去交积处理完成误差分散，再FEC解码实现数据纠错。交积不会增加信道的数据码元。 (5)伪随机序列扰码进行基带信号传输的缺点是其频谱会因数据出现连“1”和连“0”而包含大的低频成分，不适应信道的传输特性,也不利于从中提取出时钟信息。解决办法之一是采用扰码技术,使信号受到随机化处理，变为伪随机序列，又称为“数据随机化”和“能量扩散”处理。扰码不但能改善位定时的恢复质量，还可以使信号频谱平滑，使帧同步和自适应同步和自适应时域均衡等系统的性能得到改善。 扰码虽然“扰乱”了原有数据的本来规律，但因为是人为的“扰乱”，在接收端很容易去加扰，恢复成原数据流。 实现加扰和解码，需要产生伪随机二进制序列（PRBS）再与输入数据逐个比特作运算。PRBS也称为m序列，这种m序列与TS的数据码流进行模2加运算后，数据流中的“1”和“0”的连续游程都很短，且出现的概率基本相同。 利用伪随机序列进行扰码也是实现数字信号高保密性传输的重要手段之一。一般将信源产生的二进制数字信息和一个周期很长的伪随即序列模2相加，就可将原信息变成不可理解的另一序列。这种信号在信道中传输自然具有高度保密性。在接收端将接收信号再加上（模2和）同样的伪随机序列，就恢复为原来发送的信息。2. 卷积码的基本理论2.1卷积码介绍卷积码最早于1955年由Elias提出，稍后，1957年Wozencraft提出了一种有效地译码方法即序列译码。1963年Massey提出了一种性能稍差但是比较实用的门限译码方法，使得卷积码开始走向实用化。而后1967年Viterbi提出了最大似然译码算法，它对存储级数较小的卷积码很容易实现，被称作Viterbi译码算法，广泛的应用于现代通信中。2.1.1 卷积码的差错控制原理卷积码是一种性能优越的信道编码，它的编码器和解码器都比较易于实现，同时还具有较强的纠错能力，这使得它的使用越来越广泛。我们在一些资料上可以找到关于分组码的一些介绍，分组码的实现是将编码信息分组单独进行编码，因此无论是在编码还是译码的过程中不同码组之间的码元无关。卷积码和分组码的根本区别在于，它不是把信息序列分组后再进行单独编码，而是由连续输入的信息序列得到连续输出的已编码序列。即进行分组编码时，其本组中的n-k个校验元仅与本组的k个信息元有关，而与其它各组信息无关；但在卷积码中，其编码器将k个信息码元编为n个码元时，这n个码元不仅与当前段的k个信息有关，而且与前面的（N1）段信息有关（N为编码的约束长度）。 同样，在卷积码译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息。而且卷积码的纠错能力随约束长度的增加而增强，差错率则随着约束长度增加而呈指数下降 。卷积码(n,k,N) 主要用来纠随机错误，它的码元与前后码元有一定的约束关系，编码复杂度可用编码约束长度N*n来表示。一般地，最小距离d表明了卷积码在连续N段以内的距离特性，该码可以在N个连续码流内纠正(d-1)/2个错误。卷积码的纠错能力不仅与约束长度有关，还与采用的译码方式有关。总之，由于n，k较小，且利用了各组之间的相关性，在同样的码率和设备的复杂性条件下，无论理论上还是实践上都证明：卷积码的性能至少不比分组码差。以二元码为例，输入信息序列为u(u0，u1，)，其多项式表示为u(x)u0+u1xulxl。编码器的连接可用多项式表示为g(1,1)(x)1+x+x2和g(1,2)(x)1+x2，称为码的子生成多项式。它们的系数矢量g(1,1)=(111)和g(1,2)=(101)称作码的子生成元。以子生成多项式为阵元构成的多项式矩阵G(x)g(1,1)(x),g(1,2)(x)，称为码的生成多项式矩阵。由生成元构成的半无限矩阵 称为码的生成矩阵。其中(11,10,11)是由g(1,1)和g(1,2)交叉连接构成。编码器输出序列为cuG，称为码序列，其多项式表示为c(x)，它可看作是两个子码序列c(1)(x)和c(2)(x)经过合路开关S合成的，其中c(1)(x)u(x)g(1,1)(x)和c(2)(x)u(x)g(1,2)(x),它们分别是信息序列和相应子生成元的卷积，卷积码由此得名。 在一般情况下，输入信息序列经过一个时分开关被分成k0个子序列,分别以u(x)表示,其中i=1，2,k0，即u(x)u(x),u(x)。编码器的结构由k0n0阶生成多项式矩阵给定。输出码序列由n0个子序列组成，即c(x)c(x),c(x)，c(x)，且c(x)=u(x)G(x)。若m是所有子生成多项式g(x)中最高次式的次数，称这种码为(n0，k0，N)卷积码。卷积码中编码后的n个码元不仅与当前段的k个信息有关，而且也与前面（N-1）段的信息有关，编码过程中相互关联的码元为nN个。因此，这N时间内的码元数目nN通常被称为这种码的约束长度。卷积码的纠错能力随着N的增加而增大，在编码器复杂程度相同的情况下，卷段积码的性能优于分组码。卷积码也是分组的, 但它的监督元不仅与本组的信息元有关, 而且还与前若干组的信息元有关。卷积码根据需要, 有不同的结构及相应的纠错能力,但都有类似的编码规律。值得指出的是一种(2,1,N)卷积码, 其码率为1 /2, 它的监督位只有1位, 编码效率较高, 也比较简单。如使用较长的约束长度, 则既可以纠正突发差错, 也可以纠正随机差错。2.2卷积码编码原理卷积码一般表示为(n,k,N)的形式，即将k个信息比特编码为n个比特的码组，N为编码约束长度，说明编码过程中相互约束的码段个数。卷积码编码后的n个码元不仅与当前组的k个信息比特有关，还与前N-1个输入组的信息比特有关。编码过程中相互关联的码元有N*n个。R=k/n是编码效率。编码效率和约束长度是衡量卷积码的两个重要参数。典型的卷积码一般选n,k较小，但N值可取较大(10)，以获得简单而高性能的卷积码。卷积码的编码描述方式有很多种：冲激响应描述法、生成矩阵描述法、多项式乘积描述法、状态图描述，树图描述，网格图描述等。2.2.1 卷积码解析表示法卷积码的解析表示发大致可以分为离散卷积法，生成矩阵法，码多项式法。下面以离散卷积为例进行说明。卷积码的编码器一般比较简单，为一个具有k个输入端，n个输出端，m级移位寄存器的有限状态有记忆系统。下图所示为(2,1,7)卷积码的编码器。图2-1 （2,1,7）卷积码编码器若输入序列为u=(u0u1u2u3),则对应两个码字序列 C1=(ca0ca1ca2ca3)和C2=(cb0cb1cb2cb3)相应的编码方程可写为 P1=uC1，P2=uC2，P=(P1,P2)。“”符号表示卷积运算，P1，P2表示编码器的两个冲激响应，即编码器的输出可以由输入序列和编码器的两个冲击响应卷积而得到，故称为卷积码。这里的冲激响应指：当输入为1 0 0 0 0 序列时，所观察到的两个输出序列值。由于上图N值为7，故冲激响应至多可持续到第7位，可写为P1=1 1 1 1 0 0 1，P2=1 0 1 1 0 1 1然后将两个输出端的码字序列合并为一个码字序列为C=(ca0cb0ca1cb1ca2cb2)。若输入信息序列为1 1 0 1;则P1=1 0 0 1 0 1 0 1 0 1，P2=1 1 1 1 1 0 1 1 1 1,C=1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1。如图3-2所示为(2,1,3)卷积码的编码器，也是本次课程设计所研究的卷积码编码器，由于其生成冲激响应分别为1 1 1和1 0 1，故被称为(7,5) 码。 Z-1Z-1+图2-2 （2,1,3）卷积码编码器2.2.2 卷积码图形表示法除了用解析法描述卷积码的编码外，还可以使用比较形象的图形法来表示卷积码。比较常用的有状态图法，树图法和网格图法。状态图法：由于卷积码编码器在下一时刻的输出取决于编码器的当前状态和下一时刻的输入，而编码器当前状态取决于编码器当前各移位寄存器的存储内容。称编码器当前各移位寄存器存储内容(0或1)为编码器在该时刻的状态(此状态代表记忆以前的输入信息)。随着信息序列的不断输入，编码器不断从一个状态转移到另外一个状态，并且输出相应的编码序列。编码器的总可能状态数为2mk个。对(7,5)码的编码器来说，n=2，k=1，N=3，m=2。共有四个可能状态，其状态图如图2-3所示：0/00001001111/101/011/000/100/010/111/11 图2-3 卷积码状态图图中四个方块表示状态，状态间的连线与箭头表示转移方向，连线上的数字表示是状态发生转移的到来比特，斜杠后的数字由一个状态到另一个状态转移时的输出码字。如当前状态为11，输入信息为0，则转移到01状态并输出01码字，若输入信息为1，则依然为11状态，并输出10码字。树图法描述卷积码的编码过程除了用它的生成矩阵外，还可以用半无限码树图。卷积码的树图表示是一种形象的表示卷积码编码过程的方法。卷积码的各种距离度量与树图有密切关系。以(2,1,3)卷积码为例，它的生成多项式矩阵和生成矩阵分别为： (2-1) (2-2)若输入编码器的信息序列M(D)=(m0,m1,m2.)=(1 1 0 1 1 .),则由编码器输出码序列C为C = M =(11，01，01，00，01，01， )=( C0,Cl,C2, C3,) (2-3)可以把这个编码过程用如图3-4所示的半无限码树图来说明。设编码器的初始状态为0，码树中每个节点的下一级的上面的分支表示输入为0，下面的分支表示输入为l。每个分支上面的数字表示对应次分支的输出。因此输入不同的信息序列，编码器就走不同的路径，输出不同的码序列。按照上面的例子，则编码过程对应码树中粗线表示的一条路径。对该码序列来说，树图上的这条路径就是它的正确路径。对于一般的二进制(n,k,N)编码器来说，每次输入的是k个信息元，有2k个可能的信息组，这对应于从码树每一个节点上分出的分支树有2k条，相应于2k个不同信息组的输入，并且每条都有n个码元，作为与此相应的输出子码。由以上讨论可知，卷积码编码过程的实质，是在输入信息序列的控制下，编码器沿码树通过某一特定路径的过程。显然，译码过程就是根据接收序列和信道干扰的统计特性，译码器在原码树上力图恢复原来编码器所走的路径，即寻找正确路径的过程。其过程如图2-4所示。00 00S01100S010S2011101S000101100110101100S2S2S301S000S011101S2S2110111S100 000 01S3S310图2-4 ( 2,1,3)卷积码的树图网格图法：网格图可以描述卷积码的状态随时间推移而转移的情况。该图纵坐标表示所有状态，横坐标表示时间。网格图在卷积码的概率译码，特别是Viterbi译码中非常重要，它综合了状态图法直观简单和树图法时序关系清晰的特点。如图2-5所示状态 t1 t2 t3 t4 t5 t6 211111111111022020020202111020 1000 01 11图2-5 译码器网格图图中实线表示输入0时所走分支，虚线表示输入1时所走分支，编码时只需从起始状态开始依次选择路线并读出输出即可。假设从a状态开始，输入为1 0 1 1，则可由图中读出输出为11 10 10 01。2.3 卷积码译码原理2.3.1 卷积码三种译码方式(1)代数译码 代数译码是将卷积码的一个编码约束长度的码段看作是n0(m+1)，k0(m+1)线性分组码，每次根据(m+1)分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。如果假设输入的信息序列为(10111)，相应的编码输出序列为 c(11100001100111)。在未超出编码约束长度的情况下，可以通过译码时将接受序列与所有可能的输出编码序列进行比较，通过比较可以得到最小距离，进而可以得到可能的最大概率。按同样方法判决，将每一位进行比较，进行纠错。若此时接收序列R(10100001110111),先根据R的前三个分支（101000）和码树中前三个分支长的所有可能的 8条路径(000000)、(000011)、(001110)、(001101)、(111011)、(111000)、(110101)和(110110)进行比较，可知(111001)与接收序列(101000)的距离最小，于是判定第 0分支的信息数字为 0。然后以R的第 13分支数字(100001)按同样方法判决,依此类推下去,最后得到信息序列的估值为=(10111)，遂实现了纠错。这种译码法，译码时采用的接收数字长度或译码约束长度为(m+1)n0，所以只能纠正不多于(dmin-1)/2个错误(n长上的)。实用中多采用反馈择多逻辑译码法实现。 (2)维特比译码维特比译码是根据接收序列在码的格图上找出一条与接收序列距离（或其他量度）为最小的一种算法。它和运筹学中求最短路径的算法相类似。若接收序列为R=(10100101100111)，译码器从某个状态,例如从状态出发,每次向右延伸一个分支（对于lL,从每个节点出发都有2种可能的延伸,其中L是信息序列段数,对lL，只有一种可能）,并与接收数字相应分支进行比较,计算它们之间的距离，然后将计算所得距离加到被延伸路径的累积距离值中。对到达每个状态的各条路径（有2条）的距离累积值进行比较，保留距离值最小的一条路径，称为幸存路径（当有两条以上取最小值时，可任取其中之一）,译码过程如图。图中标出到达各级节点的幸存路径的距离累积值。对给定 R的估值序列为=(10111)。这种算法所保留的路径与接收序列之间的似然概率为最大，所以又称为最大似然译码。这种译码的译码约束长度常为编码约束长度的数倍，因而可以纠正不多于(df/2)个错误。 维特比译码器的复杂性随m呈指数增大。实用中m不大于10。它在卫星和深空通信中有广泛的应用。在解决码间串扰和数据压缩中也可应用。 （3）序贯译码序贯译码是根据接收序列和编码规则，在整个码树中搜索（既可以前进，也可以后退）出一条与接收序列距离（或其他量度）最小的一种算法。由于它的译码器的复杂性随m值增大而线性增长,在实用中可以选用较大的m值（如2040）以保证更高的可靠性。许多深空和海事通信系统都采用序贯译码。2.3.2 Viterbi译码原理卷积码概率译码的基本思路是:以接收码流为基础，逐个计算它与其他所有可能出现的、连续的网格图路径的距离，选出其中可能性最大的一条作为译码估值输出。概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的正是最大似然的准则。卷积码的最大似然译码与分组码的最大似然译码在原理上是一样的，但实现方法上略有不同。主要区别在于:分组码是孤立地求解单个码组的相似度，而卷积码是求码字序列之间的相似度。基于网格图搜索的译码是实现最大似然判决的重要方法和途径。用格图描述时，由于路径的汇聚消除了树状图中的多余度，译码过程中只需考虑整个路径集合中那些使似然函数最大的路径。如果在某一点上发现某条路径已不可能获得最大对数似然函数，就放弃这条路径，然后在剩下的“幸存”路径中重新选择路径。这样一直进行到最后第L级(L为发送序列的长度)。由于这种方法较早地丢弃了那些不可能的路径，从而减轻了译码的工作量，Viterbi译码正是基于这种想法。 对于(n, k, N)卷积码，其网格图中共2kL种状态。由网格图的前N-1条连续支路构成的路径互不相交，即最初2k_1条路径各不相同，当接收到第N条支路时，每条路径都有2条支路延伸到第N级上，而第N级上的每两条支路又都汇聚在一个节点上。在Viterbi译码算法中，把汇聚在每个节点上的两条路径的对数似然函数累加值进行比较，然后把具有较大对数似然函数累加值的路径保存下来，而丢弃另一条路径