卷积码的Viterbi译码设计设计

《卷积码的Viterbi译码设计设计》由会员分享，可在线阅读，更多相关《卷积码的Viterbi译码设计设计（42页珍藏版）》请在装配图网上搜索。

1、摘要在数字通信系统中，通常采用差错控制编码来提高系统的可靠性。自Plia首次提出卷积码编码以来,这一编码技术至今仍显示出强大的生命力.目前，卷积码已广泛应用在无线通信标准中,如GM,CDMA2000和IS-等无线通信标准中。针对NCDMA数据传输过程中的误码问题，本文论述了旨在提高数据传输质量的维特比译码器的设计。虽然ite译码复杂度较大,实现较为困难，但效率高,速度快。因此本文着重分析和讨论了12速率的(2,1，）卷积码编码和其iterbi译码算法。深入研究卷积码编码原理和Viterbi算法原理后，提出了（2，,9）卷积码编码以及iterb算法的初始化、加比选和回溯设计方案，运用查表的方法,

2、避免了大量繁琐计算，使得译码简洁迅速，译码器的实时性能良好。并充分利用TM32C54X系列DSP芯片,用汇编语言完成了(2，1,9）卷积码编码和Viterbi译码的程序.关键词：差错控制编码、卷积码、iterb译码、TMS20C54X、DSPAbstractIn digial cmmunication sytes， err contro cngs usually used o ioe sytem reiabiit. Since P.Elia ut forard te covolutna ingth iti,th codig is sillshowig strng vitalty，haecome

3、 wdly ued i seli commuiation, wirelessommictons ad mayoter ounio ystsas a kind f channlcdiod uch asGSM， A2000 a hs been awielsscommniain stdardso IS95。In vie of t errr problem n e procss of N-CDA ta trasmission, tis pper iscusss the aimsoiove hequity ofdata anmission of victor sign than th decoder.

4、Augh Viterbidecodig omplxt isigger， mordifficult toacieve， bt high effiiency a fa sped thi rtil mphataly analedand disssed the 1/2at (,1,9) nvluion cocoin ts Vtebi decoding alorithm Indeth stud n princple of cooluo cde on an Vterbi lom， roped te oouio ode codng and iterbi algrthm (，1,） niializaton，

5、add han co andbckdeign， usng lok-up tlmethod,to void reamnto tdius clclati, hdeoing and quck,godrea-time pformane e dee Make fuuse of he srieof TMS320C4P chp, sing assembly anguag to compete e（，1,9）cnuioncodecoind ierb ecdig pocess。Kewords：error contr codig,onvolional code， Verb decoing， TMS0C54X目录摘

6、要1bstract2目录1.绪论111 移动通信及N-CDM背景。数字通信概述11。3 卷积编码与译码的发展14主要研究工作2。与CCS简介52.1DS概述52.11 S的主要特点521。2 SSU单元概述7。 CS概述8。3 本章小结83。卷积码的理论基础31卷积码的概述91 卷积码基本原理931。 卷积码的纠错能力。1.3 卷积码的表示方法。 Vterbi译码的概述113.本章小结144. 卷积编码的实现14。1 (，9）卷积码编码54.1。1 （，9）卷积码编码设计方案154。1。2 （2,1,9)卷积码编码流程图164。13(，1,)卷积编码程序实现164。.4 (2,1,9)的程序仿

7、真74 (2，,9)卷积码状态转换表14.2.1 （2，1，9)卷积码状态转换表的设计算法184。2。2 (2,1，9）卷积码状态转换表的流程图184.2.3 （2，1,)卷积码状态表14.2。4 (2，,9)卷积码状态表的蝶形结构14.3 本章小结225. Vitbi译码的实现235 Viteri译码基础235.2 Vitrbi译码算法35。3变量定义情况554初始化25.4. 初始化流程图2。2 初始化程序仿真275。5 加-比-选85。.加比-选流程图305。加比选程序仿真315.回溯15.6。1回溯流程图35。2 回溯仿真图345。7 Vterb纠错测试35。8 本章小结35总结36致

8、谢7参考文献38附录1：（2，1，9）卷积编码器原程序3附录:(2,1，9）Vitbi译码原程序4138 / 421。绪论1.1 移动通信及NDMA背景人们希望在任何时候、在任何地方、与任何人都能及时沟通联系、交流信息.而这就是移动通信所为人们提供的服务。顾名思义，移动通信是指通信双方至少有一方在移动中(或者临时停留在一个非预定的位置上）进行信息传输和交换,这包括移动体（车辆、船舶、飞机或行人）和移动体之间的通信，移动体和固定点（固定无线电台或有线用户）之间的通信。通信系统和网络经过数字化的进程后，目前主要的通信系统和网络都是数字化的系统和网络,移动通信也是如此。通常,人们把模拟移动通信系统（

9、包括模拟蜂窝网、模拟无绳电话与模拟集群调度系统等）称作第一代移动通信(1)，而把数字化的移动通信系统（包括数字蜂窝网、数字无绳电话与移动数据系统以及移动卫星通信系统等)称作第二代移动通信系统（2G）9。第二代移动通信系统主要包括广泛使用的G公用移动通信网和窄带数字移动公用网(-C）。-CDA与GSM的根本区别在于采用了不同的多址技术，SM采用TDA,而NCDMA采用DA.采用了技术的移动网有很多的优越性，比如,CA网络的抗干扰性能很强，瞬时发射功率比较小;CMA网络中的用户可以以相同的频率同时通信(分配的码不同),相邻的基站可以使用相同的频率，频率利用率非常高；CDA移动通信网的容量大，通话质

10、量好,频率规划简单，手机电池寿命长，能够实现多种形式的分集(时间分集、空间分集和频率分集）和软切换。1. 数字通信概述观察电的信号波形,我们可以发现如图11所示，模拟信号的波形是在自由选取电压的同时连续变化的,而在如图-2中可见,数字信号从高电压或低电压这两个值中选择其一.如果设高电压为“1、低电压为“”，数字信号就可以用“1”、“0来表示。语言、音乐、图像等的信号是模拟信号，计算机所处理的信号则是数字信号。下面将从保密性和抗干扰能力两方面对模拟信号和数字信号进行比较。（1）保密性模拟通信很容易被窃听。只要收到了模拟信号，就容易得到通信的内容。而在数字通信系统中，信号经过模/数（A/D）转换后

11、可以进行加密处理,再进行传输，在接收端解密后经过数模（D/A)转换还原出原始信号,其保密性好。(2）抗干扰能力模拟信号沿线路的传输过程中会受到外界和通信系统内部的各种噪声干扰。噪声和信号混合后难以分开，从而使得通信质量下降。但是，对于数字通信，尽管数字信号在传输过程中混入杂音，但可以利用电子电路构成的门限电压（称为阈值）去衡量输入的信号电压,只有达到某一电压幅度，电路才会有输出值，并自动生成整齐的脉冲。较小的杂音电压到达时,由于它低于门限电压而被滤掉，不会引起电路动作。因此再生信号与原始信号完全相同，除非干扰信号大于原始信号才会产生误码15。-+时间电压图1-1模拟信号波形电压高低时间 1 0

12、 1 1 0 1 0 0图1-2 数字信号波形在现代技术的信号处理中,数字信号发挥的作用越来越大,几乎复杂的信号处理都离不开数字信号。从模拟信号转换到数字信号(称为模/数转换)一般要经过抽样、量化和编码三个过程，最终变成一连串由“0”和“1”代表的脉冲数字信号。其中，抽样就是以相等的间隔时间来抽取模拟信号的样值，使连续的信号变成离散的信号.量化是把抽取的样值变换为最接近数字值,表示抽取样值的大小。编码则是量化的数值用一组二进制的数码来表示。所有传输数字信号的数字通信系统都包括信源、信源编码、信道编码、调制、解调、信道译码、信源译码、信宿几个基本部分,可归结于如图13所示的模型。信源信源编码信道

13、编码调制信道解调信宿信源解码信道解码噪声图1-3数字通信系统模型1. 卷积编码与译码的发展本文重点讨论的卷积码是Elias在955年最早提出的，与分组码一样，编码后的码元序列n位分为一组，其中位信息码元,r位附加的监督码元,r=nk。分组码中的监督码元仅与本码组的信息码元有关,而与其他码组的信息码元无关,而卷积码的监督码元不仅与本组信息码元有关，还与前面码组的信息码元有约束关系。在编码器复杂性相同的情况下，卷积码性能优于分组码.针对卷积码的译码方法有三种：Woencaft在1957年提出了一种有效译码方法，即序列译码；Massey在63年提出了一种性能稍差,但比较实用的门限译码方法，由于这一实

14、用性进展使卷积码从理论走向实用;Viterb在167年提出了最大似然译码法，该方法对存储器级数较小卷积码的译码很容易实现，并具有效率高、速度快、译码器简单等特点,人们后来称其为Veri算法或Viterb译码,广泛应用于现代通信中。ieri译码可通过多种平台进行实现,在本是基于DSP汇编语言实现卷积码的iterbi译码。DSP是数字信号处理的英文缩写，它具有精度高、灵活性大、可靠性高、时分复用、易于大规模集成等优点。在最近的2多年时间里,数字信号处理技术得到了广泛的应用.而在现代通信系统中，它占着非常重要的地位，可以说在通信系统中越来越多的功能部件是采用数字信号处理技术实现的。1。4 主要研究工

15、作本论文所做的工作:首先深入学习NCDMA移动通信系统的信道结构和信道编码的原理，熟悉卷积码的应用和功能特性。鉴于卷积码译码的最优的特性和高效率确定译码器编码译码方式itebi译码。其次，以复杂度较低的(，3）卷积码为例，了解卷积码的基本理论，并初步讲诉了Viter译码的基础算法及原理,从而为理解复杂度较高的（2，1,9)Vierbi译码提供基础概念。接着，深入学习数字信号处理器DS的原理,了解54x专为Vterbi译码算法设计的SSU单元,掌握用高效率的汇编语言开发DSP。并学习运用美国德州仪器专为DP推出的CC集成开发环境，明白用CCS进行Viterbi译码的编写、编译、调试、仿真。然后,

16、对卷积码译码器的实现算法进行了研究,提出了适于运算的算法，并完成了实现译码器的软件设计。依次通过“初始化”、“加比选”、“回溯”完成Viterb译码。由于（2，1，9)较为复杂，本论文采用“查表法”来节省时间、提高效率，从而避免了大量繁琐计算,使得译码简洁迅速，.最后，用CS具体实现了适合TM30C5XS运算的Vitrbi算法,用CS仿真结果检验本论文提出的Vitebi译码的正确性，并验证了Viteri译码器具有纠正随机错误的功能。DSP与C简介。1 DS概述DSP也就是Digitlsinal pocessor数字处理器。它是伴随着微电子学、数字信号处理技术、计算机技术等学科的发展而产生的。数

17、字信号处理自20世纪80年代问世以来,以其独特的结构和快速实现各种数字信号处理算法的突出优点，正以前所未有的速度向前发展。数字化是各种信息进行有效获取、存储、处理、交换、综合与应用的基础，而数字信号处理技术及其集成化产品为信号数字化处理提供了广阔的发展和应用空间。随着数字信号处理器性能的不断提高，开发工具的日臻完善，价格迅速下降，使其在语音合成与识别、图像处理、雷达、通信、声呐、多媒体、高速控制、医疗设备、仪器仪表、家用电器等众多领域得到了极为广泛的应用.TI公司的M30C54系列是应用于通信设备的通用SP芯片。该芯片采用改善的哈佛结构，拥有优化的CU、1条数据总线、3条数据总线和4条地址总线

18、，因而在一个周期内可以从程序存储器取1条指令、从数据存储器读2个操作数和向数据存储器写1个操作数。此系列片内的CS（比较、选择和存储单元)是为Viterbi译码而专门设计的硬件电路，它与LU(算术逻辑单元)结合使用，利用专用的指令CMS使得碟型运算中的相加、比较和选择操作更加高效，这极大的提高了Vieri译码的性能。2。1。DP的主要特点DP的主要结构特点可以概括为以下几点:(1) 哈佛结构总线结构可以分为两种。一种是冯诺依曼结构,另一种是哈佛结构。冯诺依曼结构的特点是程序存储器和数据存储器共用一个存储空间，程序和数据总线共享。统一编址依靠指令计数器提供的地址来区分是指令数据还是地址。由于对数

19、据和程序进行分别读写，取指令和存取操作数必须共享内部总线，因此微处理器在执行指令时只能串行执行，执行速度慢,数据吞吐量低。但是，随着半导体工艺的飞速发展,这一问题基本得到解决。传统的微处理器通常采用冯诺依曼结构,它已经成为计算机发展的一个主要标准。哈佛结构和冯诺依曼结构相比,更适合处理器具有高度实时要求的数字信号。哈佛结构的特点是程序存储器和数据存储器各自具有独立的存储空间,独立的程序总线和数据总线,允许区指令和执行指令重叠执行,允许对数据和程序同时寻址,允许直接在程序和数据之间进行信息传递，减少冲突,大大提高了数据处理能力,从而获得高速的运算能力。很多SP有两套或者两套以上的内部数据总线，这

20、种总线结构称为修正的哈佛结构。对于乘法或者加法等运算，一条指令要从存储器中取两个操作数，多套数据总线就使得两个操作数可以同时取得.TI公司的P采用改进型的哈佛结构，改进之处有三点。第一，数据总线和程序总线之间的局部交叉链接。第二，具有高速缓存器。总线之间的交叉使得程序和数据之间的信息传递更加灵活、方便，运行数据存在程序存储区中，并被算术运算指令直接使用。第三,设置高速缓存器，可以省去从存储器中读取指令的时间,大大提高了运行速度. （) 流水线技术所谓流水线操作，就是取指令和执行指令可以同时进行,从而减少指令的执行时间，进一步增强处理器的数据处理能力。流水线技术是提高DP程序执行效率的一个重要手

21、段。流水线技术使两个或者更多的不同操作可以重叠执行。在处理结构上，每条指令的执行分为取指、解码、执行等若干阶段，每个阶段称为一级流水。流水处理使得若干条指令的不同执行阶段并行执行，而能够提高程序执行速度。流水线的深度为二级以上,不同产品的流水线深度也不同。模拟设备公司的ADSP深度为二级,TI公司的S32054为五级,也就是说可以同时运行5条指令。对于流水线编程还有一个延迟间隙(lySlot）的问题，即有些指令的执行时间不是单个周期,指令结果可以使用前一个或者几个周期的等待时间，称为延迟间隙。采用线性汇编语言编程，程序效率可以达到标准汇编程序效率的9510%。（3) 特殊的指令系统DS芯片通常

22、都有一套自己的特殊指令，这个指令系统都是专门为数字信号处理而设计的。（） 采用硬件乘法器一般计算机没有硬件乘法器，它的算术逻辑单元只能完成两个操作数的加、减和逻辑运算，而乘法和除法时由加法和移位来实现，因此在一般的计算机上实现乘法和除法很费时间。但是在信号处理中，又有大量的乘法运算,所以，DP芯片都有专门的硬件乘法器，TS0C54x系列DSP就有两个乘法器。另一方面，各种算法也在不断地改进，尽量减少乘法运算。通过硬件乘法器和算法的改进，基本上解决了乘法运算速度的瓶颈问题。硬件乘法器是DS区别于通用微处理器的一个重要标志.()支持多种寻址方式DS处理大量的数据，这些数据都存放在片内或者片外存储器

23、上。伴随着频繁的数据访问,数据地址的计算时间也线性增长，有时计算地址的时间比实际的算术操作还长。因此，在地址计算上作特殊考虑。DSP通常都有支持地址计算的算术单元-地址产生器。地址产生器与AU并行工作，因此地址的计算不再额外占用CPU时间.由于有些算法通常需要一次从存储器中取两个操作数，因此DSP内的地址产生器一般也有两个.DSP的地址产生器一般都支持间接寻址。（) 高速的时钟周期和强大的处理能力SP芯片的主频和处理能力不断地提高，TM30C500系列SP的主频已经达到2MHz。最初的芯片时钟周期也将达到0MHz800MHz，处理能力将达到（4806）兆条指令/s。TI宣称到2010年,其D的

24、处理能力可以达到310E6兆条指令/s.（7） 设有片内存储器和内存接口由于P面向的是数据密集型应用，因此存储器访问速度对处理器的性能影响很大。通用微处理器的特点是程序一般都很大,片内存储器不会给处理器性能带来明显改善。因此现在微处理器片内一般不设ROM(存储程序)和RA（存储数据)，但是集成有高速缓存（Cche）.而DP算法的特点是需要大量的简单计算，其相应的程序比较短小。将程序指令存放DSP芯片内可以减少指令的传输时间，并有效缓解芯片外部总线接口的压力。除了片内程序存储器外，SP芯片一般还集成数据R，用于存放参数和数据。片内数据存储器不存在外部存储器的总线竞争问题和访问速度不匹配问题，因此

25、访问速度快，可以缓解SP的数据瓶颈,充分利用DSP强大的处理能力.2。1. SSU单元概述比较、选择和存储单元是TMS20C54X器件专门为Vitebi算法设计的加法、比较、选择（ACS）操作的硬件单元。其功能框图如图所示。compTRNTCmuxMSW/LSWSELECT16EB15-EB0From barrel shifterFrom accumulator AFrom accumulator BCSSU图2-1 CSSU功能框图CSU支持信道译码器所用的各种terbi算法。itr算法的加法、比较、选择操作的来此加法运算由LU完成。将T1中的位置，ALU被设为双位工作模式,这样就可以在一个

26、机器周期内同时完成俩次加法运算。俩次加法运算的结果分别放在了累加器的高16位和低位。CSSU通过CPS指令完成比较、选择操作7。完成累加器的高位字和低位字之间的比较，然后将累加器中的较大的字放在数据存储器中，同时N左移1位，将0或1存入TRN的第0位及ST0的TC位。如此可以利用优化的片内硬件促进iterbi的蝶形运算。 C概述CCS 是一个完整的DSP 集成开发环境，包括了编辑、编译、汇编、链接、软件模拟、调试等几乎所有需要的软件,是目前使用最为广泛的D 开发软件之一。它有两种工作模式,一是软件仿真器，即脱离SP 芯片，在C 上模拟SP 指令集与工作机制,主要用于前期算法和调试；二是硬件开发

27、板相结合在线编程，即实时运行在SP 芯片上，可以在线编制和调试应用程序。CCS支持如图22所示的开发周期的所有阶段7。分析实时调试、分析统计和跟踪设计前期算法规划编辑和编译创建工程文件、源文件、配置文件调试语法调试、断点调试和日志保存图2 ccs开发阶段2。3本章小结本章着重介绍DSP的特点与集成开发环境CC。本论文选用的是T0C4x系列的DSP芯片，一是因为C54X系列因其片内特殊的单元结构，能够快速完成Vierbi运算，其二是由于数字化时代的到来已经是一个不可逆转的趋势,数字产品必将代替模拟产品，而数字信号处理器（DSP）正是这场数字化革命的核心.3卷积码的理论基础 3。1 卷积码的概述3

28、。1.1 卷积码基本原理卷积码通常记作( n,k，N）.它将输入信息序列分成长度为k的码段，然后按照既定编码规则，将k 位码元编码成为n比特,构成一个码字。N表示约束长度，代表编码后的n位码元不仅与当前输入码段有关,而且与前面-1个输入码段的信息有关。编码效率为k/ n。卷积码的纠错能力随着N的增加而增大,而差错率则随着的增加呈指数下降7。如果给定一个卷积码的生成多项式，就可以根据这个生成多项式将相应时刻输入的数据相异或(模2加），产生新的编码输出。图3-就是一个（2，1,9）卷积码编码器的基本结构。DDDDDDDD信息比特（输入）c0 编码输出c1 编码输出图3-1（2，1,）编码器结构3.

29、。卷积码的纠错能力卷积码（ ,k，）主要用来纠随机错误,编码复杂度可用编码约束长度Nn来表示。衡量卷积码的纠错能力是用它的距离特性(距离是指两个码字中对应位取值不同的个数）来描述的。由于卷积码的纠错能力与它采用的译码方法有很大关系，因此不同的译码方法就有不同的距离度量。本文采用了的译码方式是概率译码-Viterbi译码,衡量概率译码纠错能力是用自由距离df来描述.在卷积码（,k,N)中，若自由距离为df，则能在N+1连续段内纠正（df)/2（向下取整)个随机错误。.13 卷积码的表示方法卷积编码可以用生成多项式表示，如果我们将参与异或的位设为1，不参与异或的位设为0，那么对应于c0可以得到一个

30、二进制码字111101，对应于c1可以得到一个二进制码字110001。这就是卷积码生成的码字，只要生成码字确定了，该卷积码的码型也就选定了。通常，生成码字还可以用时延算子来表示 (31） (3-2）式（31)和（3）中，D代表时延算子,D的幂表示延迟时间单元数,D表示延迟1bit,即上个时刻输入码元,D2表示延迟2bit,即上两个时刻输入码元，以此类推。假设输入码元序列为1110111.。.,用时延算子表示为（3)则输出编码序列也可用时延算子表示为(3-4）（5)根据C1(）,0(）的时延算子表达式，即可求出编码输出序列C,C1.可以证明,式（4）和（3-5）与时域运算=u*g1和0=u*是等

31、效的，符号*代表卷积运算，编码输出序列,1是输入信息序列u与编码器生成多项式的卷积，这就是卷积码名称的由来。当然,我们也可以用图解法表示，如码树图、状态图和网格图。通过卷积码的几何描述表示，可以非常清楚和直观地观察编码和解码的过程。以约束度为3的卷积码为例，将输入的最近两个时刻的数据作为状态,则寄存器总的状态数有24种，其状态标号为a（0),（1),（1）和（11)。按时间展开，对应每个状态值指出去的上支路（实线)表示最新输入数据为0,下支路(虚线）表示最新输入数据为1，则编码过程的网状图如图32所示。图3-2 卷积码网格图状态a（00)状态b（01）状态c（10）状态d（11）同样按时间展开

32、，还可以生成（2,1，3）卷积码的树状图，如图33所示.01起始状态000010001001110010011100100111图3-3 卷积码树状图32 Vitbi译码的概述卷积码的译码方式可以分为两大类:代数译码和概率译码。代数译码时利用编码本身的代数结构进行解码,不考虑信道的统计特性。大数逻辑译码,又称门限译码，是卷积码代数译码的最主要的一种方式。大数逻辑译码对于约束长度较短的卷积码最为有效,而且设备较简单.概率译码(又称最大似然译码)则是基于信道的统计特性和卷积码的特点进行计算。首先由沃曾克拉夫特针对无记忆信道提出的序列译码就是概率译码方式之一;另一种概率译码方式是维特比算法。当码的约

33、束长度较短时,它比序列译码算法的效率更高,速度更快,目前得到广泛的应用。维特比译码器是一种最大似然解码器。设信道输出的R是一个二进制（或四进制)序列，而译码器的输出是一个信息序列M的估值序列M。译码器的基本任务就是根据一套译码规则,根据接收序列R给出与发送的信息序列M最接近的估值序列M.由于与码字C之间存在一一对应关系，所以这等价于译码器根据R产生一个C的估值序列C。显然,当且仅当C=C和=M时,译码器正确译码。当给定接收序列时，译码器的条件译码错误概率定义为（36)所以译码器的错误译码概率：(3-7）是接收R的概率，与估值序列无关，所以译码错误概率最小的最佳译码规则是使最小,这等价于使最小,

34、亦即使最大。因此，如果译码器对输入的R，能在2k个码字中选择一个使，=1，2，2最大的码字作为的估值序列，则这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验概率译。由贝叶斯公式 （38）可知，若发端发送每个码字的概率均相同，且由于（R)与译码方法无关,所以使最小,即使最大，这等价于使最大.一个译码器的译码规则若能在码字中选择某一个使上式最大，则这种译码规则称为最大似然译码.而对于无记忆二进制对称信道，最大似然又等价于使汉明距离最小15。Viterbi译码算法并不是在网格上一次比较所有可能的2k条路径（序列),而是接收一段，计算、比较、选择一段最可能的码段（分支)，从而达到整个

35、码序列是一个由最大似然函数的序列。iterbi译码算法的基本步骤如下：从某一时间单位j=N开始，对进入每一状态的所有长为段分支的部分路径，计算本分路径度量。对每一状态,挑选并存储一条最小度量的部分路径及其部分度量值,称此路径为幸存路径。j增加1，把此时刻进入每一状态的所有分支度量同这些分支相连的前一时刻的幸存路径的度量相加，得到了此时刻进入每一状态的幸存路径，把存储并删去其他所有路径，这样幸存路径就延长了一个分支。若jL+N，则重复以上步骤，否则停止,译码器得到了有最小路径度量的路径。由时间单位N直至L，网格图中2N状态中的每一个有一条幸存路径，共有kN条。但在时间单位后，网格图上的状态数目减

36、少，幸存路径也相应减少。最后到第L+N单位时间，网格图归到全为0的状态,因此仅剩下一条幸存路径.这条路径就是要找的最大似然函数的路径,也就是译码输出序列。现在仍用（2，1,3）卷积码的例子说明维特比译码的原理，此编码器的基本结构如图35所示15。设现在的发送信息位为11,为了是图2-5中的移存器的信息位全部移出，在信息位后面加入三个“，故编码后的发送序列为11 01 01 010 1100并且假设接收序列为1100100 10 1 00，其中第个码元为错误。输出序列XMjMj-1Mj-2输入序列M状态x2x1图3-4 （2,1,3）卷积编码基本结构由于这是一个（n，,）=（2,1，）卷积码，发

37、送序列的约束度N=3,所以首先考察*N=。第一步考察接收序列的前6位“11 00 01 00”。由此码的网格图-5知,沿路经每一级有个状态a、b、c和d.每种状态只有两条路径到达。故4种状态共有8条到达路径。现在比较网格图中的这8条路径和接收序列间的汉明距离。例如，由出发点状态经过三级路径后到达状态a的两条路径中的上面一条为“00 0 00”，它和接收序列“1 0 01”的汉明距离等于3；下面一条为“11 0 1”，它和接收序列的汉明距离为2。由出发点状态a经过三级路径到达b、c和d的路径分别都有两条,故共有8条路径。在表3中列出了这条路径和其汉明距离15。现在将达到的每个状态的两条路径的汉明

38、距离作比较,将距离最小的一条保留，称为幸存路径。如这两天的汉明距离相同.则可以任意保留一条。这要就剩下4条路径了，即在表中的第、4、8条的路径。表31 维特比算法解码第一步运算结果序号路径对应序列距离幸存否序号路径对应序列距离幸存否aaa000 003否5aa1 06否2bca111 12是6abdc1 1 1是3aab00 0 11否aabd00 1 01否4acb102是8a111 03是第二步将继续考察接收序列中的后继2位“00。现在计算4条幸存路径上增减一级后的条可能路径的汉明距离。计算结果列于图-7中。表中最小的距离等于1，其路径是bdb,相应序列为11 01 0100。它和发送序列

39、相同,故对应发送信息位101。按照表2中的幸存路径画出的网格图示于图36中.图中粗线路径时汉明距离最小(等于1）的路径。表3-2 维特比算法译码第二步计算结果序号路径原幸存路径距离新增路径段新增距离总距离幸存否1ca+a02否2abdc+a1a23否abca+b2b24否4abc+b1是5abcbc2bc13否6add+314否abcb+d2bd否8abdd3dd1否为了使输入的信息位全部通过编码器的移存器，使移存器回到初始状态，在信息位101后面加了三个“。若把这三个“”仍然看作是信息位,则可以按照上面的算法继续解码。但是，若已知这三个码元是（为结尾而补充的)“0”，则在解码计算时就预先知道

40、在接收这三个码元后，路径必然回到初始状态a. 图3-6 对应信息位“1101”的幸存路径网格图状态a（00）状态b（01)状态d（11）状态c（10）100101000011010110111由卷积码编码的网格图3-可知,当得到为一条译码路径后,前一级输入信息位就是下一级4个状态a(0），（01），c（10）,（11)的最后一位。因此当得到幸存路径后，可以计算并保存幸存路径在每一级所在状态的最后一位，得到的序列左移一位就是译码输出序列，这与编码输入序列相同。例如，在图38中幸存路径为abdc.保留a、b、d、和b对应二进制码元的最后一位得到01101，去除第一位得到111，与输入序列相同，即还

41、原出原始信息15.Vierb在卫星和深空通信中有广泛的应用.在解决码间串扰和数据压缩中也可应用。.3 本章小结本章简要介绍了卷积码的概念、表示方法和译码。表示法包括生成多项式和形象直观的图解法。其中网格图对本文的itei译码起到促进我们理解的作用.本章还对本文讨论的Verb译码重点研究、介绍。最后以（2,1，3）卷积码译码为例，详细讨论了Vieri译码算法中的各个步骤.4 卷积编码的实现。 (2,1，9）卷积码编码(,1，9）卷积码的编码器是由八个移位寄存器和两个模相加器组成的，如图2-1所示.信息位输入到移位寄存器中，经过抽头的提取，采用模和的方式产生输出.可以看出，整个编码过程可以看作输入

42、信息序列与由移位寄存器和模2和连接方式所决定的另一个序列的卷积。编码过程中用到的输入位数称为约束长度，它的值等于延迟单元的数目加上1。编码速率则指的是移入编码器的位数与进入信道被传输的位数的比率。常常用延迟算子多项式来描述卷积码。图3-1所示系统的多项式为:(4-1） （4)。1.1 （2,1，9)卷积码编码设计方案由上面的讨论可知,编码的实质就是在已知状态的情况下，由输入0或计算出输出c0 1.即先将移存器所存储的状态字左移一位，将输入的或1放在最低位，然后再计算输出c0 1。c0和c1的值可以通过公式(41）和（4-2)来求得,即是数的0，2，3，7,8位求异或而得到,c1是数的0，2，4

43、，位求异或而得到。然后，再将c和c1合一个两位数c0 c1，即所要求的输出。业务速率1/2的(2,1，9）卷积码，一帧有6bi信息需要处理,那么输入数据也采取96个0、1序列，即由全0状态开始连续计算96次再回到初始状态.所以要在数据区开一个6字的空间用来接受输入数据序列，并要开一个12字的空间来存储输出.采用一个96次循环语句来实现编码功能是最简单有效。41。2 (，,9）卷积码编码流程图开始B累加器低9位清0后，最低位取输入信息wA取输入信息wA累加器与B累加器的特定位异或产生c0 c1 ，存入wa空间B累加器左移1位，最低位取输入信息w96次？结束是否图-1 编码流程图4。1。 (2,1

44、，9）卷积编码程序实现把B累加器的低9位当做状态移存器，左移一位是输入信息从最低位即第0位进入，第8位状态舍去.c0是累加器的第0，1，2,3，5,7,8位分步求异或而得到，1是累加器B的，2，3，4，8位分步求异或而得到。分步的值分别放在A累加器的第1位和第位，即A累加器的第1位放0，第0位放c,再将A累加器的值存入wa空间。如此循环次,可以得到我们需要的92字卷积码.其中卷积码编码程序的重点就是理解A累加器与B累加器的特点位的异或操作。下面就是求c0程序的一段代码。ldar2，a；的值=b0xorb,， ;=b0r1xrb，-2,a ;a=b0xrbxorb2xor，;a=b0orb1xr

45、b2xorbxor，-5，；a=b0ororxorb3xor5xob，a;a=b0xorb1xr2xor3xorb5orb7xorb，-,a;a=b0xor1xrbxor3obxorbolaad#2,a；1放c04.1.4 (2,，9)的程序仿真图4-2是用CCS卷积码编码器的9bit的输入信息，空间的数据图-2编码输入经过程序正确运行后,我们可以得到92bt的输出数据即a空间的数据图43编码输出Wa空间的数据就是w空间的数据经过(2，1,9）卷积后得到的卷积码。4。2 （2,）卷积码状态转换表第3章提到卷积有3种能直观形象表述卷积的图解法,我们注意到图解法能够清楚地反映各个状态之间的转移关系

46、.而本文所讨论的Vebi译码的关键算法查表法就是依赖状态转换表来提高程序效率。那么下面我们将介绍如何用程序得到(2,1，9)卷积码的状态之间的关系。4. （，1,）卷积码状态转换表的设计算法（2，)卷积码,有2个状态，即从000 00到11111.状态转换图的设计算法与卷积编码的设计算法大同小异，可以理解成输入信息分别是、1时，状态从0000 00 到1111 11 时产生的c0c1。将状态左移1位,最低位依次放入0、1，那么c0就是状态的0，2，3，5，7，8位求异或而得到，c1是状态的，2，3,位求异或而得到.4.。2 (2，,)卷积码状态转换表的流程图开始B累加器低9位清0A取0A累加器

47、与B累加器的特定位异或产生c0 c1 ，存入wa空间B累加器状态位加1256次？结束是否A取1A累加器与B累加器的特定位异或产生c0 c1 ，存入wa空间是图 状态表流程图42.3 （2，1，9）卷积码状态表表4-1 （2,，9）状态转换表分支初始分支到达初始分支到达初始分支到达初始分支到达输入状态输出状态状态输出状态状态输出状态状态输出状态00001212101920112111112900265001191911130113111313030146601321300041941012105101311501301667113411106195013411070135171113504118

48、680161200819601361009103711903705011061113133101017011101100130111139060017010341121911411130111003101410711470142101419111210115114104081172111411620000144017451111145091118701146170120014009104110147101204001481801202021411491000149012251015019110311011230151002311210247521001242041115210121113102

49、501301302677151116001511271155007051401287811151421220601561020101291157113079011814300301058031115113101901610200010144013281160013111113300161000811016214513420901162150163501018011114141600641170001311165019113883011661473821101600391167113901167020148116148402120168110410069041116921114285011714

50、900421307100107111401171221044860017210014211117114511173141732001017411461501711150471017524148176152042160170049101719170215089117853101110510017901511117902052010185411522101811530111003101810154910018215015421918210151113105001802800921184561520041115711800571018502908930081715221116101917090183

51、01609088106022210110110189101189036295111901916223019011060111191030496101910142011211650113005119331066901941611662251194101671910670095341168980962006822601961009101116011970350199111963107070081107100101711190172000016072228100010073111320103707011121174290202107502307103038007102102046611723001111701205710078030026167172111206171207107900070000041