本科毕业论文---卷积码的viterbi译码设计论文正文.doc

毕业设计（论文）摘要在数字通信系统中，通常采用差错控制编码来提高系统的可靠性。自PElias首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。目前，卷积码已广泛应用在无线通信标准中，如GSM，CDMA2000和IS-95等无线通信标准中。针对N-CDMA数据传输过程中的误码问题,本文论述了旨在提高数据传输质量的维特比译码器的设计。虽然Viterbi译码复杂度较大，实现较为困难，但效率高，速度快。因此本文着重分析和讨论了1/2速率的（2,1,9）卷积码编码和其Viterbi译码算法。深入研究卷积码编码原理和Viterbi算法原理后，提出了（2,1,9）卷积码编码以及Viterbi算法的初始化、加比选和回溯设计方案，运用查表的方法,避免了大量繁琐计算,使得译码简洁迅速,译码器的实时性能良好。并充分利用TMS320C54X系列DSP芯片，用汇编语言完成了（2,1,9）卷积码编码和Viterbi译码的程序。关键词：差错控制编码、卷积码、Viterbi译码、TMS320C54X、DSPAbstractIn 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.In view of the error problem in the process of N-CDMA data transmission, this paper discusses the aims to improve the quality of data transmission of victor design than the decoder. Although Viterbi decoding complexity is bigger, more difficult to achieve, but high efficiency and fast speed. So this article emphatically analyzed and discussed the 1/2 rate (2,1,9) convolution code coding and its Viterbi decoding algorithm. In-depth study on principle of convolution code coding and Viterbi algorithm, proposed the convolution code coding and Viterbi algorithm (2,1,9) initialization, add - than - choose and back design, using look-up table method, to avoid a large amount of tedious calculation, the decoding and quick, good real-time performance of the decoder. Make full use of the series of TMS320C54X DSP chip, using assembly language to complete the（2,1,9）convolution code coding and Viterbi decoding process.Keywords: error control coding, convolutional code, Viterbi decoding, TMS320C54X目录摘要1Abstract2目录31.绪论11.1 移动通信及N-CDMA背景11.2 数字通信概述11.3 卷积编码与译码的发展31.4 主要研究工作32.DSP与CCS简介52.1 DSP概述52.1.1 DSP的主要特点52.1.2 CSSU单元概述72.2 CCS概述82.3 本章小结83.卷积码的理论基础93.1 卷积码的概述93.1.1 卷积码基本原理93.1.2 卷积码的纠错能力93.1.3 卷积码的表示方法103.2 Viterbi译码的概述113.3 本章小结144 卷积编码的实现154.1 (2,1,9)卷积码编码154.1.1 (2,1,9)卷积码编码设计方案154.1.2 (2,1,9)卷积码编码流程图164.1.3 (2,1,9)卷积编码程序实现164.1.4 (2,1,9)的程序仿真174.2 (2,1,9)卷积码状态转换表174.2.1 (2,1,9)卷积码状态转换表的设计算法184.2.2 (2,1,9)卷积码状态转换表的流程图184.2.3 (2,1,9)卷积码状态表194.2.4 (2,1,9)卷积码状态表的蝶形结构214.3 本章小结225. Viterbi译码的实现235.1 Viterbi译码基础235.2 Viterbi译码算法235.3 变量定义情况255.4 初始化265.4.1 初始化流程图275.4.2 初始化程序仿真275.5 加-比-选285.5.1加-比-选流程图305.5.2加-比-选程序仿真315.6 回溯315.6.1 回溯流程图335.6.2 回溯仿真图345.7 Viterbi纠错测试345.8 本章小结35总结36致谢37参考文献38附录1：（2,1,9）卷积编码器原程序39附录2：（2,1,9）Viterbi译码原程序411.绪论1.1 移动通信及N-CDMA背景人们希望在任何时候、在任何地方、与任何人都能及时沟通联系、交流信息。而这就是移动通信所为人们提供的服务。顾名思义，移动通信是指通信双方至少有一方在移动中(或者临时停留在一个非预定的位置上）进行信息传输和交换，这包括移动体（车辆、船舶、飞机或行人）和移动体之间的通信，移动体和固定点（固定无线电台或有线用户）之间的通信。通信系统和网络经过数字化的进程后，目前主要的通信系统和网络都是数字化的系统和网络，移动通信也是如此。通常，人们把模拟移动通信系统（包括模拟蜂窝网、模拟无绳电话与模拟集群调度系统等）称作第一代移动通信（1G），而把数字化的移动通信系统（包括数字蜂窝网、数字无绳电话与移动数据系统以及移动卫星通信系统等）称作第二代移动通信系统（2G）9。第二代移动通信系统主要包括广泛使用的GSM公用移动通信网和窄带数字移动公用网（N-CDMA)。N-CDMA与GSM的根本区别在于采用了不同的多址技术，GSM采用TDMA,而N-CDMA采用CDMA。采用了CDMA技术的移动网有很多的优越性，比如，CDMA网络的抗干扰性能很强，瞬时发射功率比较小；CDMA网络中的用户可以以相同的频率同时通信（分配的码不同），相邻的基站可以使用相同的频率，频率利用率非常高；CDMA移动通信网的容量大，通话质量好，频率规划简单，手机电池寿命长，能够实现多种形式的分集（时间分集、空间分集和频率分集）和软切换17。1.2 数字通信概述观察电的信号波形，我们可以发现如图1-1所示，模拟信号的波形是在自由选取电压的同时连续变化的，而在如图1-2中可见，数字信号从高电压或低电压这两个值中选择其一。如果设高电压为“1”、低电压为“0”，数字信号就可以用“1”、“0”来表示。语言、音乐、图像等的信号是模拟信号，计算机所处理的信号则是数字信号。下面将从保密性和抗干扰能力两方面对模拟信号和数字信号进行比较。（1）保密性模拟通信很容易被窃听。只要收到了模拟信号，就容易得到通信的内容。而在数字通信系统中，信号经过模/数（A/D）转换后可以进行加密处理，再进行传输，在接收端解密后经过数/模（D/A）转换还原出原始信号，其保密性好。（2）抗干扰能力模拟信号沿线路的传输过程中会受到外界和通信系统内部的各种噪声干扰。噪声和信号混合后难以分开，从而使得通信质量下降。但是，对于数字通信，尽管数字信号在传输过程中混入杂音，但可以利用电子电路构成的门限电压（称为阈值）去衡量输入的信号电压，只有达到某一电压幅度，电路才会有输出值，并自动生成整齐的脉冲。较小的杂音电压到达时，由于它低于门限电压而被滤掉，不会引起电路动作。因此再生信号与原始信号完全相同，除非干扰信号大于原始信号才会产生误码15。-+时间电压图1-1模拟信号波形电压高低时间 1 0 1 1 0 1 0 0图1-2 数字信号波形在现代技术的信号处理中，数字信号发挥的作用越来越大，几乎复杂的信号处理都离不开数字信号。从模拟信号转换到数字信号（称为模/数转换）一般要经过抽样、量化和编码三个过程，最终变成一连串由“0”和“1”代表的脉冲数字信号。其中，抽样就是以相等的间隔时间来抽取模拟信号的样值，使连续的信号变成离散的信号。量化是把抽取的样值变换为最接近数字值，表示抽取样值的大小。编码则是量化的数值用一组二进制的数码来表示。所有传输数字信号的数字通信系统都包括信源、信源编码、信道编码、调制、解调、信道译码、信源译码、信宿几个基本部分，可归结于如图1-3所示的模型。信源信源编码信道编码调制信道解调信宿信源解码信道解码噪声图1-3数字通信系统模型1.3 卷积编码与译码的发展本文重点讨论的卷积码是Elias在1955年最早提出的，与分组码一样，编码后的码元序列n位分为一组，其中k位信息码元，r位附加的监督码元，r=n-k。分组码中的监督码元仅与本码组的信息码元有关，而与其他码组的信息码元无关，而卷积码的监督码元不仅与本组信息码元有关，还与前面码组的信息码元有约束关系。在编码器复杂性相同的情况下，卷积码性能优于分组码。针对卷积码的译码方法有三种：Wozencraft在1957年提出了一种有效译码方法，即序列译码；Massey在1963年提出了一种性能稍差，但比较实用的门限译码方法，由于这一实用性进展使卷积码从理论走向实用；Viterbi在1967年提出了最大似然译码法，该方法对存储器级数较小卷积码的译码很容易实现，并具有效率高、速度快、译码器简单等特点，人们后来称其为Viterbi算法或Viterbi译码，广泛应用于现代通信中。Viterbi译码可通过多种平台进行实现，在本是基于DSP汇编语言实现卷积码的Viterbi译码。DSP是数字信号处理的英文缩写，它具有精度高、灵活性大、可靠性高、时分复用、易于大规模集成等优点。在最近的20多年时间里，数字信号处理技术得到了广泛的应用。而在现代通信系统中，它占着非常重要的地位，可以说在通信系统中越来越多的功能部件是采用数字信号处理技术实现的。1.4 主要研究工作本论文所做的工作：首先深入学习N-CDMA移动通信系统的信道结构和信道编码的原理，熟悉卷积码的应用和功能特性。鉴于卷积码译码的最优的特性和高效率确定译码器编码译码方式Viterbi译码。其次，以复杂度较低的（2,1,3）卷积码为例，了解卷积码的基本理论，并初步讲诉了Viterbi译码的基础算法及原理，从而为理解复杂度较高的（2,1,9）Viterbi译码提供基础概念。接着，深入学习数字信号处理器DSP的原理，了解C54x专为Viterbi译码算法设计的CSSU单元,掌握用高效率的汇编语言开发DSP。并学习运用美国德州仪器专为DSP推出的CCS集成开发环境，明白用CCS进行Viterbi译码的编写、编译、调试、仿真。然后,对卷积码译码器的实现算法进行了研究,提出了适于运算的算法,并完成了实现译码器的软件设计。依次通过“初始化”、“加-比-选”、“回溯”完成Viterbi译码。由于（2,1,9）较为复杂，本论文采用“查表法”来节省时间、提高效率，从而避免了大量繁琐计算,使得译码简洁迅速,。最后,用CCS具体实现了适合TMS320C54X DSP运算的Viterbi算法，用CCS仿真结果检验本论文提出的Viterbi译码的正确性，并验证了Viterbi译码器具有纠正随机错误的功能。2.DSP与CCS简介2.1 DSP概述DSP也就是Digital signal processor数字处理器。它是伴随着微电子学、数字信号处理技术、计算机技术等学科的发展而产生的。数字信号处理自20世纪80年代问世以来，以其独特的结构和快速实现各种数字信号处理算法的突出优点，正以前所未有的速度向前发展。数字化是各种信息进行有效获取、存储、处理、交换、综合与应用的基础，而数字信号处理技术及其集成化产品为信号数字化处理提供了广阔的发展和应用空间。随着数字信号处理器性能的不断提高，开发工具的日臻完善，价格迅速下降，使其在语音合成与识别、图像处理、雷达、通信、声呐、多媒体、高速控制、医疗设备、仪器仪表、家用电器等众多领域得到了极为广泛的应用7。TI公司的TMS320C54X系列是应用于通信设备的通用DSP芯片。该芯片采用改善的哈佛结构，拥有优化的CPU、1条数据总线、3条数据总线和4条地址总线，因而在一个周期内可以从程序存储器取1条指令、从数据存储器读2个操作数和向数据存储器写1个操作数。此系列片内的CSSU（比较、选择和存储单元）是为Viterbi译码而专门设计的硬件电路，它与ALU（算术逻辑单元）结合使用，利用专用的指令CMPS使得碟型运算中的相加、比较和选择操作更加高效，这极大的提高了Viterbi译码的性能。2.1.1 DSP的主要特点DSP的主要结构特点可以概括为以下几点：(1) 哈佛结构 总线结构可以分为两种。一种是冯诺依曼结构，另一种是哈佛结构。冯诺依曼结构的特点是程序存储器和数据存储器共用一个存储空间，程序和数据总线共享。统一编址依靠指令计数器提供的地址来区分是指令数据还是地址。由于对数据和程序进行分别读写，取指令和存取操作数必须共享内部总线，因此微处理器在执行指令时只能串行执行，执行速度慢，数据吞吐量低。但是，随着半导体工艺的飞速发展，这一问题基本得到解决。传统的微处理器通常采用冯诺依曼结构，它已经成为计算机发展的一个主要标准。哈佛结构和冯诺依曼结构相比，更适合处理器具有高度实时要求的数字信号。哈佛结构的特点是程序存储器和数据存储器各自具有独立的存储空间，独立的程序总线和数据总线，允许区指令和执行指令重叠执行，允许对数据和程序同时寻址，允许直接在程序和数据之间进行信息传递，减少冲突，大大提高了数据处理能力，从而获得高速的运算能力。很多DSP有两套或者两套以上的内部数据总线，这种总线结构称为修正的哈佛结构。对于乘法或者加法等运算，一条指令要从存储器中取两个操作数，多套数据总线就使得两个操作数可以同时取得。TI公司的DSP采用改进型的哈佛结构，改进之处有三点。第一，数据总线和程序总线之间的局部交叉链接。第二，具有高速缓存器。总线之间的交叉使得程序和数据之间的信息传递更加灵活、方便，运行数据存在程序存储区中，并被算术运算指令直接使用。第三，设置高速缓存器，可以省去从存储器中读取指令的时间，大大提高了运行速度。 (2) 流水线技术所谓流水线操作，就是取指令和执行指令可以同时进行，从而减少指令的执行时间，进一步增强处理器的数据处理能力。流水线技术是提高DSP程序执行效率的一个重要手段。流水线技术使两个或者更多的不同操作可以重叠执行。在处理结构上，每条指令的执行分为取指、解码、执行等若干阶段，每个阶段称为一级流水。流水处理使得若干条指令的不同执行阶段并行执行，而能够提高程序执行速度。流水线的深度为二级以上，不同产品的流水线深度也不同。模拟设备公司的ADSP深度为二级，TI公司的TMS320C54为五级，也就是说可以同时运行5条指令。对于流水线编程还有一个延迟间隙（Delay Slot）的问题，即有些指令的执行时间不是单个周期，指令结果可以使用前一个或者几个周期的等待时间，称为延迟间隙。采用线性汇编语言编程，程序效率可以达到标准汇编程序效率的95%100%。(3) 特殊的指令系统DSP芯片通常都有一套自己的特殊指令，这个指令系统都是专门为数字信号处理而设计的。(4) 采用硬件乘法器一般计算机没有硬件乘法器，它的算术逻辑单元只能完成两个操作数的加、减和逻辑运算，而乘法和除法时由加法和移位来实现，因此在一般的计算机上实现乘法和除法很费时间。但是在信号处理中，又有大量的乘法运算，所以，DSP芯片都有专门的硬件乘法器，TMS320C54x系列DSP就有两个乘法器。另一方面，各种算法也在不断地改进，尽量减少乘法运算。通过硬件乘法器和算法的改进，基本上解决了乘法运算速度的瓶颈问题。硬件乘法器是DSP区别于通用微处理器的一个重要标志。(5) 支持多种寻址方式DSP处理大量的数据，这些数据都存放在片内或者片外存储器上。伴随着频繁的数据访问，数据地址的计算时间也线性增长，有时计算地址的时间比实际的算术操作还长。因此，在地址计算上作特殊考虑。DSP通常都有支持地址计算的算术单元地址产生器。地址产生器与ALU并行工作，因此地址的计算不再额外占用CPU时间。由于有些算法通常需要一次从存储器中取两个操作数，因此DSP内的地址产生器一般也有两个。DSP的地址产生器一般都支持间接寻址。(6) 高速的时钟周期和强大的处理能力DSP芯片的主频和处理能力不断地提高，TMS320C5000系列DSP的主频已经达到200MHz。最初的芯片时钟周期也将达到600MHz800MHz，处理能力将达到（48006400）兆条指令/s。TI宣称到2010年，其DSP的处理能力可以达到310E6兆条指令/s。(7) 设有片内存储器和内存接口由于DSP面向的是数据密集型应用，因此存储器访问速度对处理器的性能影响很大。通用微处理器的特点是程序一般都很大，片内存储器不会给处理器性能带来明显改善。因此现在微处理器片内一般不设ROM（存储程序）和RAM（存储数据），但是集成有高速缓存（Cache）。而DSP算法的特点是需要大量的简单计算，其相应的程序比较短小。将程序指令存放DSP芯片内可以减少指令的传输时间，并有效缓解芯片外部总线接口的压力。除了片内程序存储器外，DSP芯片一般还集成数据RAM，用于存放参数和数据。片内数据存储器不存在外部存储器的总线竞争问题和访问速度不匹配问题，因此访问速度快，可以缓解DSP的数据瓶颈，充分利用DSP强大的处理能力。2.1.2 CSSU单元概述比较、选择和存储单元是TMS320C54X器件专门为Viterbi算法设计的加法、比较、选择（ACS）操作的硬件单元。其功能框图如图2-1所示。compTRNTCmuxMSW/LSWSELECT16EB15-EB0From barrel shifterFrom accumulator AFrom accumulator BCSSU图2-1 CSSU功能框图CSSU支持信道译码器所用的各种Viterbi算法。Viterbi算法的加法、比较、选择操作的来此加法运算由ALU完成。将ST1中的C16位置1，ALU被设为双16位工作模式，这样就可以在一个机器周期内同时完成俩次加法运算。俩次加法运算的结果分别放在了累加器的高16位和低16位。CSSU通过CMPS指令完成比较、选择操作7。完成累加器B的高位字和低位字之间的比较，然后将累加器中的较大的字放在数据存储器中，同时TRN左移1位，将0或1存入TRN的第0位及ST0的TC位。如此可以利用优化的片内硬件促进Viterbi的蝶形运算。2.2 CCS概述CCS 是一个完整的DSP 集成开发环境，包括了编辑、编译、汇编、链接、软件模拟、调试等几乎所有需要的软件，是目前使用最为广泛的DSP 开发软件之一。它有两种工作模式，一是软件仿真器，即脱离DSP 芯片，在PC 上模拟DSP 指令集与工作机制，主要用于前期算法和调试；二是硬件开发板相结合在线编程，即实时运行在DSP 芯片上，可以在线编制和调试应用程序。CCS支持如图2-2所示的开发周期的所有阶段7。分析实时调试、分析统计和跟踪设计前期算法规划编辑和编译创建工程文件、源文件、配置文件调试语法调试、断点调试和日志保存图2-2 ccs开发阶段2.3 本章小结本章着重介绍DSP的特点与集成开发环境CCS。本论文选用的是TMS320C54x系列的DSP芯片，一是因为C54X系列因其片内特殊的单元结构，能够快速完成Viterbi运算，其二是由于数字化时代的到来已经是一个不可逆转的趋势，数字产品必将代替模拟产品，而数字信号处理器(DSP)正是这场数字化革命的核心。3.卷积码的理论基础 3.1 卷积码的概述3.1.1 卷积码基本原理卷积码通常记作( n，k，N)。它将输入信息序列分成长度为k的码段,然后按照既定编码规则,将k 位码元编码成为n比特,构成一个码字。N表示约束长度,代表编码后的n位码元不仅与当前输入码段有关, 而且与前面N-1个输入码段的信息有关。编码效率为k / n。卷积码的纠错能力随着N的增加而增大,而差错率则随着N 的增加呈指数下降17。如果给定一个卷积码的生成多项式，就可以根据这个生成多项式将相应时刻输入的数据相异或（模2加），产生新的编码输出。图3-1就是一个（2,1,9）卷积码编码器的基本结构。DDDDDDDD信息比特（输入）c0 编码输出c1 编码输出图3-1 （2,1,9）编码器结构3.1.2 卷积码的纠错能力卷积码( n，k，N)主要用来纠随机错误，编码复杂度可用编码约束长度N*n来表示。衡量卷积码的纠错能力是用它的距离特性（距离是指两个码字中对应位取值不同的个数）来描述的。由于卷积码的纠错能力与它采用的译码方法有很大关系，因此不同的译码方法就有不同的距离度量。本文采用了的译码方式是概率译码Viterbi译码，衡量概率译码纠错能力是用自由距离df来描述。在卷积码（n，k，N）中，若自由距离为df，则能在N+1连续段内纠正（df-1）/2（向下取整）个随机错误1。3.1.3 卷积码的表示方法卷积编码可以用生成多项式表示，如果我们将参与异或的位设为1，不参与异或的位设为0，那么对应于c0可以得到一个二进制码字111101011，对应于c1可以得到一个二进制码字101110001。这就是卷积码生成的码字，只要生成码字确定了，该卷积码的码型也就选定了。通常，生成码字还可以用时延算子来表示 （3-1） （3-2）式（3-1）和（3-2）中，D代表时延算子，D的幂表示延迟时间单元数，D表示延迟1bit，即上个时刻输入码元，D2表示延迟2bit，即上两个时刻输入码元，以此类推。假设输入码元序列为111101011.，用时延算子表示为（3-3）则输出编码序列也可用时延算子表示为（3-4）（3-5）根据C1(D)，C0(D)的时延算子表达式，即可求出编码输出序列C0,C1。可以证明，式（3-4）和（3-5）与时域运算c1=u*g1和c0=u*g0是等效的，符号*代表卷积运算，编码输出序列c0,c1是输入信息序列u与编码器生成多项式的卷积，这就是卷积码名称的由来。当然，我们也可以用图解法表示，如码树图、状态图和网格图。通过卷积码的几何描述表示，可以非常清楚和直观地观察编码和解码的过程。以约束度为3的卷积码为例，将输入的最近两个时刻的数据作为状态，则寄存器总的状态数有22=4种，其状态标号为a（00），b（01），c（10）和d（11）。按时间展开，对应每个状态值指出去的上支路（实线）表示最新输入数据为0，下支路（虚线）表示最新输入数据为1，则编码过程的网状图如图3-2所示。图3-2 卷积码网格图状态a（00)状态b（01）状态c（10）状态d（11）同样按时间展开，还可以生成（2,1,3）卷积码的树状图，如图3-3所示。01起始状态000010001001110010011100100111图3-3 卷积码树状图3.2 Viterbi译码的概述卷积码的译码方式可以分为两大类：代数译码和概率译码。代数译码时利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑译码，又称门限译码，是卷积码代数译码的最主要的一种方式。大数逻辑译码对于约束长度较短的卷积码最为有效，而且设备较简单。概率译码（又称最大似然译码）则是基于信道的统计特性和卷积码的特点进行计算。首先由沃曾克拉夫特针对无记忆信道提出的序列译码就是概率译码方式之一；另一种概率译码方式是维特比算法。当码的约束长度较短时，它比序列译码算法的效率更高，速度更快，目前得到广泛的应用。维特比译码器是一种最大似然解码器。设信道输出的R是一个二进制(或四进制)序列，而译码器的输出是一个信息序列M的估值序列M。译码器的基本任务就是根据一套译码规则，根据接收序列R给出与发送的信息序列M最接近的估值序列M。由于M与码字C之间存在一一对应关系，所以这等价于译码器根据R产生一个C的估值序列C。显然，当且仅当C=C和M=M时，译码器正确译码。当给定接收序列R时，译码器的条件译码错误概率定义为（3-6）所以译码器的错误译码概率：（3-7）是接收R的概率，与估值序列无关，所以译码错误概率最小的最佳译码规则是使最小，这等价于使最小，亦即使最大。因此，如果译码器对输入的R,能在2k个码字中选择一个使，i =1,2，2k最大的码字作为C的估值序列，则这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验概率译。由贝叶斯公式 （3-8）可知，若发端发送每个码字的概率均相同，且由于P(R)与译码方法无关，所以使最小，即使最大，这等价于使最大。一个译码器的译码规则若能在码字C中选择某一个使上式最大，则这种译码规则称为最大似然译码。而对于无记忆二进制对称信道，最大似然又等价于使汉明距离最小15。Viterbi译码算法并不是在网格上一次比较所有可能的2kL条路径（序列），而是接收一段，计算、比较、选择一段最可能的码段（分支），从而达到整个码序列是一个由最大似然函数的序列。Viterbi译码算法的基本步骤如下：从某一时间单位j=N开始，对进入每一状态的所有长为j段分支的部分路径，计算本分路径度量。对每一状态，挑选并存储一条最小度量的部分路径及其部分度量值，称此路径为幸存路径。j增加1，把此时刻进入每一状态的所有分支度量同这些分支相连的前一时刻的幸存路径的度量相加，得到了此时刻进入每一状态的幸存路径，把存储并删去其他所有路径，这样幸存路径就延长了一个分支。若jL+N，则重复以上步骤，否则停止，译码器得到了有最小路径度量的路径。由时间单位N直至L，网格图中2kN状态中的每一个有一条幸存路径，共有2kN条。但在L时间单位后，网格图上的状态数目减少，幸存路径也相应减少。最后到第L+N单位时间，网格图归到全为0的状态，因此仅剩下一条幸存路径。这条路径就是要找的最大似然函数的路径，也就是译码输出序列。现在仍用（2,1,3）卷积码的例子说明维特比译码的原理,此编码器的基本结构如图3-5所示15。设现在的发送信息位为1101，为了是图2-5中的移存器的信息位全部移出，在信息位后面加入三个“0”，故编码后的发送序列为11 01 01 00 10 11 00并且假设接收序列为11 00 01 00 10 11 00，其中第4个码元为错误。输出序列XMjMj-1Mj-2输入序列M状态x2x1图3-4 （2,1,3）卷积编码基本结构由于这是一个（n，k，N）=（2,1,3）卷积码，发送序列的约束度N=3，所以首先考察n*N=6。第一步考察接收序列的前6位“11 00 01 00”。由此码的网格图3-5知，沿路经每一级有4个状态a、b、c和d。每种状态只有两条路径到达。故4种状态共有8条到达路径。现在比较网格图中的这8条路径和接收序列间的汉明距离。例如，由出发点状态a经过三级路径后到达状态a的两条路径中的上面一条为“00 00 00”，它和接收序列“11 00 01”的汉明距离等于3；下面一条为“11 10 11”，它和接收序列的汉明距离为2。由出发点状态a经过三级路径到达b、c和d的路径分别都有两条，故共有8条路径。在表3-1中列出了这8条路径和其汉明距离15。现在将达到的每个状态的两条路径的汉明距离作比较，将距离最小的一条保留，称为幸存路径。如这两天的汉明距离相同。则可以任意保留一条。这要就剩下4条路径了，即在表中的第2、4、6、8条的路径。表3-1 维特比算法解码第一步运算结果序号路径对应序列距离幸存否序号路径对应序列距离幸存否1aaaa00 00 003否5aabc00 11 106否2abca11 10 112是6abdc11 01 011是3aaab00 00 113否7aabd00 11 014否4abcb11 10 002是8abdd11 01 103是第二步将继续考察接收序列中的后继2位“00”。现在计算4条幸存路径上增减一级后的8条可能路径的汉明距离。计算结果列于图3-7中。表中最小的距离等于1，其路径是abdc+b，相应序列为11 01 01 00。它和发送序列相同，故对应发送信息位1101。按照表3-2中的幸存路径画出的网格图示于图3-6中。图中粗线路径时汉明距离最小（等于1）的路径。表3-2 维特比算法译码第二步计算结果序号路径原幸存路径距离新增路径段新增距离总距离幸存否1abca+a2aa02否2abdc+a1ca23否3abca+b2ab24否4abdc+b1cb01是5abcb+c2bc13否6abdd+c3dc14否7abcb+d2bd13否8abdd+d3dd14否为了使输入的信息位全部通过编码器的移存器，使移存器回到初始状态，在信息位1101后面加了三个“0”。若把这三个“0”仍然看作是信息位，则可以按照上面的算法继续解码。但是，若已知这三个码元是(为结尾而补充的）“0”，则在解码计算时就预先知道在接收这三个码元后，路径必然回到初始状态a。 图3-6 对应信息位“1101”的幸存路径网格图状态a（00）状态b（01)状态d（11）状态c（10）100101000011010110111由卷积码编码的网格图3-6可知，当得到为一条译码路径后，前一级输入信息位就是下一级4个状态a（00）,b（01）,c（10）,d（11）的最后一位。因此当得到幸存路径后，可以计算并保存幸存路径在每一级所在状态的最后一位，得到的序列左移一位就是译码输出序列，这与编码输入序列相同。例如，在图3-8中幸存路径为abdcb。保留a、b、d、c和b对应二进制码元的最后一位得到01101，去除第一位得到1101，与输入序列相同，即还原出原始信息15。Viterbi在卫星和深空通信中有广泛的应用。在解决码间串扰和数据压缩中也可应用。3.3 本章小结本章简要介绍了卷积码的概念、表示方法和译码。表示法包括生成多项式和形象直观的图解法。其中网格图对本文的Viterbi译码起到促进我们理解的作用。本章还对本文讨论的Viterbi译码重点研究、介绍。最后以（2,1,3）卷积码译码为例，详细讨论了Viterbi译码算法中的各个步骤。4 卷积编码的实现4.1 (2,1,9)卷积码编码(2,1,9)卷积码的编码器是由八个移位寄存器和两个模2相加器组成的，如图2-1所示。信息位输入到移位寄存器中，经过抽头的提取，采用模2和的方式产生输出。可以看出，整个编码过程可以看作输入信息序列与由移位寄存器和模2和连接方式所决定的另一个序列的卷积。编码过程中用到的输入位数称为约束长度，它的值等于延迟单元的数目加上1。编码速率则指的是移入编码器的位数与进入信道被传输的位数的比率。常常用延迟算子多项式来描述卷积码。图3-1所示系统的多项式为：（4-1） （4-2）4.1.1 (2,1,9)卷积码编码设计方案由上面的讨论可知，编码的实质就是在已知状态的情况下，由输入0或1计算出输出c0 c1。即先将移存器所存储的状态字左移一位，将输入的0或1放在最低位，然后再计算输出c0 c1。c0和c1的值可以通过公式（4-1）和（4-2）来求得，即c0是数的0，1，2，3，5，7，8位求异或而得到，c1是数的0，2，3，4，8位求异或而得到。然后，再将c0和c1合一个两位数c0 c1，即所要求的输出。业务速率1/2的（2,1,9）卷积码，一帧有96bit信息需要处理，那么输入数据也采取96个0、1序列，即由全0状态开始连续计算96次再回到初始状态。所以要在数据区开一个96字的空间w用来接受输入数据序列，并要开一个192字的空间wa来存储输出。采用一个96次循环语句来实现