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

毕业设计（论文）摘要 在数字通信系统中，通常采用差错控制编码来提高系统的可靠性。自 P Elias首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。目前，卷积码已广泛应用在无线通信标准中，如 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、DSP 毕业设计（论文）Abstract In 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 毕业设计（论文）目录目录 摘要.1 Abstract.2 目录目录.3 1.绪论.1 1.1 移动通信及 N-CDMA 背景.1 1.2 数字通信概述.1 1.3 卷积编码与译码的发展.3 1.4 主要研究工作.3 2.DSP 与 CCS 简介.5 2.1 DSP 概述.5 2.1.1 DSP 的主要特点.5 2.1.2 CSSU 单元概述.7 2.2 CCS 概述.8 2.3 本章小结.8 3.卷积码的理论基础.9 3.1 卷积码的概述.9 3.1.1 卷积码基本原理.9 3.1.2 卷积码的纠错能力.9 3.1.3 卷积码的表示方法.10 3.2 Viterbi 译码的概述.11 3.3 本章小结.14 4 卷积编码的实现.15 4.1 (2,1,9)卷积码编码.15 4.1.1 (2,1,9)卷积码编码设计方案.15 4.1.2 (2,1,9)卷积码编码流程图.16 4.1.3 (2,1,9)卷积编码程序实现.16 4.1.4 (2,1,9)的程序仿真.17 4.2 (2,1,9)卷积码状态转换表.17 4.2.1 (2,1,9)卷积码状态转换表的设计算法.18 4.2.2 (2,1,9)卷积码状态转换表的流程图.18 4.2.3 (2,1,9)卷积码状态表.19 4.2.4 (2,1,9)卷积码状态表的蝶形结构.21 4.3 本章小结.22 5.Viterbi 译码的实现.23 5.1 Viterbi 译码基础.23 5.2 Viterbi 译码算法.23 5.3 变量定义情况.25 毕业设计（论文）5.4 初始化.26 5.4.1 初始化流程图.27 5.4.2 初始化程序仿真.27 5.5 加-比-选.28 5.5.1 加-比-选流程图.30 5.5.2 加-比-选程序仿真.31 5.6 回溯.31 5.6.1 回溯流程图.33 5.6.2 回溯仿真图.34 5.7 Viterbi 纠错测试.34 5.8 本章小结.35 总结.36 致谢.错误错误!未定义书签。未定义书签。参考文献.37 附录 1：（2,1,9）卷积编码器原程序.38 附录 2：（2,1,9）Viterbi 译码原程序.40 毕业设计（论文）第 1 页 共 52 页 1.绪论 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）抗干扰能力 模拟信号沿线路的传输过程中会受到外界和通信系统内部的各种噪声干扰。毕业设计（论文）第 2 页 共 52 页 噪声和信号混合后难以分开，从而使得通信质量下降。但是，对于数字通信，尽管数字信号在传输过程中混入杂音，但可以利用电子电路构成的门限电压（称为阈值）去衡量输入的信号电压，只有达到某一电压幅度，电路才会有输出值，并自动生成整齐的脉冲。较小的杂音电压到达时，由于它低于门限电压而被滤掉，不会引起电路动作。因此再生信号与原始信号完全相同，除非干扰信号大于原始信号才会产生误码15。在现代技术的信号处理中，数字信号发挥的作用越来越大，几乎复杂的信号处理都离不开数字信号。从模拟信号转换到数字信号（称为模/数转换）一般要经过抽样、量化和编码三个过程，最终变成一连串由“0”和“1”代表的脉冲数字信号。其中，抽样就是以相等的间隔时间来抽取模拟信号的样值，使连续的信号变成离散的信号。量化是把抽取的样值变换为最接近数字值，表示抽取样值的大小。编码则是量化的数值用一组二进制的数码来表示。所有传输数字信号的数字通信系统都包括信源、信源编码、信道编码、调制、解调、信道译码、信源译码、信宿几个基本部分，可归结于如图 1-3 所示的模型。时间 电压 图 1-1 模拟信号波形 电压 低时间 1 0 1 1 0 1 图 1-2 数字信号波形 毕业设计（论文）第 3 页 共 52 页 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 译码算信源 信源编码 信道编码 调制 信道 解调 信宿 信源解码 信道解码 噪声 图 1-3 数字通信系统模型 毕业设计（论文）第 4 页 共 52 页 法设计的 CSSU 单元,掌握用高效率的汇编语言开发 DSP。并学习运用美国德州仪器专为 DSP 推出的 CCS 集成开发环境，明白用 CCS 进行 Viterbi 译码的编写、编译、调试、仿真。然后,对卷积码译码器的实现算法进行了研究,提出了适于运算的算法,并完成了实现译码器的软件设计。依次通过“初始化”、“加-比-选”、“回溯”完成 Viterbi译码。由于（2,1,9）较为复杂，本论文采用“查表法”来节省时间、提高效率，从而避免了大量繁琐计算,使得译码简洁迅速,。最后,用 CCS 具体实现了适合 TMS320C54X DSP 运算的 Viterbi 算法，用 CCS仿真结果检验本论文提出的 Viterbi 译码的正确性，并验证了 Viterbi 译码器具有纠正随机错误的功能。毕业设计（论文）第 5 页 共 52 页 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 有两套或者两套以上的内部数据总线，这种总线结构称为修正的哈佛结构。对于乘法或者加法等运算，一条指令 毕业设计（论文）第 6 页 共 52 页 要从存储器中取两个操作数，多套数据总线就使得两个操作数可以同时取得。TI公司的 DSP 采用改进型的哈佛结构，改进之处有三点。第一，数据总线和程序总线之间的局部交叉链接。第二，具有高速缓存器。总线之间的交叉使得程序和数据之间的信息传递更加灵活、方便，运行数据存在程序存储区中，并被算术运算指令直接使用。第三，设置高速缓存器，可以省去从存储器中读取指令的时间，大大提高了运行速度。(2)流水线技术 所谓流水线操作，就是取指令和执行指令可以同时进行，从而减少指令的执行时间，进一步增强处理器的数据处理能力。流水线技术是提高 DSP 程序执行效率的一个重要手段。流水线技术使两个或者更多的不同操作可以重叠执行。在处理结构上，每条指令的执行分为取指、解码、执行等若干阶段，每个阶段称为一级流水。流水处理使得若干条指令的不同执行阶段并行执行，而能够提高程序执行速度。流水线的深度为二级以上，不同产品的流水线深度也不同。模拟设备公司的 ADSP 深度为二级，TI 公司的 TMS320C54 为五级，也就是说可以同时运行 5条指令。对于流水线编程还有一个延迟间隙（Delay Slot）的问题，即有些指令的执行时间不是单个周期，指令结果可以使用前一个或者几个周期的等待时间，称为延迟间隙。采用线性汇编语言编程，程序效率可以达到标准汇编程序效率的 95%100%。(3)特殊的指令系统 DSP 芯片通常都有一套自己的特殊指令，这个指令系统都是专门为数字信号处理而设计的。(4)采用硬件乘法器 一般计算机没有硬件乘法器，它的算术逻辑单元只能完成两个操作数的加、减和逻辑运算，而乘法和除法时由加法和移位来实现，因此在一般的计算机上实现乘法和除法很费时间。但是在信号处理中，又有大量的乘法运算，所以，DSP芯片都有专门的硬件乘法器，TMS320C54x 系列 DSP 就有两个乘法器。另一方面，各种算法也在不断地改进，尽量减少乘法运算。通过硬件乘法器和算法的改进，基本上解决了乘法运算速度的瓶颈问题。硬件乘法器是 DSP 区别于通用微处理器的一个重要标志。(5)支持多种寻址方式 DSP 处理大量的数据，这些数据都存放在片内或者片外存储器上。伴随着频繁的数据访问，数据地址的计算时间也线性增长，有时计算地址的时间比实际的算术操作还长。因此，在地址计算上作特殊考虑。DSP 通常都有支持地址计算的算术单元地址产生器。地址产生器与 ALU 并行工作，因此地址的计算不再额外占用 CPU 时间。由于有些算法通常需要一次从存储器中取两个操作数，因 毕业设计（论文）第 7 页 共 52 页 此 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 所示。CSSU 支持信道译码器所用的各种 Viterbi 算法。Viterbi 算法的加法、比较、comp TRN TC mux MSW/LSW 1EB15-EB0 From barrel shifter From accumulator A From accumulator B CSSU 图 2-1 CSSU 功能框图 毕业设计（论文）第 8 页 共 52 页 选择操作的来此加法运算由 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)正是这场数字化革命的核心。设计设计 前 期 算 法规划 编辑和编译编辑和编译 创建工程文件、源文件、配置文件 调试调试 语法调试、断点调试和日志保存 分析分析 实时调试、分析统计和跟踪 毕业设计（论文）第 9 页 共 52 页 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）卷积码编码器的基本结构。图 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。信息比特（输入）c0 编码输出 c1 编码输出 毕业设计（论文）第 10 页 共 52 页 3.1.3 卷积码的表示方法 卷积编码可以用生成多项式表示，如果我们将参与异或的位设为 1，不参与异或的位设为 0，那么对应于c0可以得到一个二进制码字 111101011，对应于 c1可以得到一个二进制码字 101110001。这就是卷积码生成的码字，只要生成码字确定了，该卷积码的码型也就选定了。通常，生成码字还可以用时延算子来表示 84321)(1DDDDDG （3-1）875321)(0DDDDDDDG （3-2）式（3-1）和（3-2）中，D 代表时延算子，D 的幂表示延迟时间单元数，D表示延迟 1bit，即上个时刻输入码元，D2表示延迟 2bit，即上两个时刻输入码元，以此类推。假设输入码元序列为 111101011.，用时延算子表示为.1)(7532DDDDDDU （3-3）则输出编码序列也可用时延算子表示为)(1)()(1DGDUDC （3-4）)(0)()(0DGDUDC （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 所示。同样按时间展开，还可以生成（2,1,3）卷积码的树状图，如图 3-3 所示。图 3-2 卷积码网格图 状态 a（00)状态 b（01）状态 c（10）状态 d（11）毕业设计（论文）第 11 页 共 52 页 3.2 Viterbi 译码的概述 卷积码的译码方式可以分为两大类：代数译码和概率译码。代数译码时利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑译码，又称门限译码，是卷积码代数译码的最主要的一种方式。大数逻辑译码对于约束长度较短的卷积码最为有效，而且设备较简单。概率译码（又称最大似然译码）则是基于信道的统计特性和卷积码的特点进行计算。首先由沃曾克拉夫特针对无记忆信道提出的序列译码就是概率译码方式之一；另一种概率译码方式是维特比算法。当码的约束长度较短时，它比序列译码算法的效率更高，速度更快，目前得到广泛的应用。维特比译码器是一种最大似然解码器。设信道输出的 R 是一个二进制(或四进制)序列，而译码器的输出是一个信息序列 M 的估值序列 M。译码器的基本任务就是根据一套译码规则，根据接收序列 R 给出与发送的信息序列 M 最接近的估值序列 M。由于 M 与码字 C 之间存在一一对应关系，所以这等价于译码器根据 R 产生一个 C 的估值序列 C。显然，当且仅当 C=C 和 M=M 时，译码器正确译码。当给定接收序列 R 时，译码器的条件译码错误概率定义为(/)(/)P E RP CCR （3-6）所以译码器的错误译码概率：(/)()EPP E R P R （3-7）()P R是接收 R 的概率，与估值序列无关，所以译码错误概率最小的最佳译码规则是使EP最小，这等价于使(/)P CC R最小，亦即使(/)P CC R最大。因此，如果译码器对输入的 R,能在 2K个码字中选择一个使(/)iP CC R，i=1,2，2K最大的码字iC作为 C 的估值序列C，则这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验概率译。由贝叶斯公式 (/)()(/)/()iiiP CRP C P R CP R （3-8）可知，若发端发送每个码字的概率()iP C均相同，且由于 P(R)与译码方法无关，所以使EP最小，即使(/)iP CR最大，这等价于使(/)iP R C最大。一个译码器0 1 起 始状态 00 00 10 00 10 01 11 00 10 01 11 00 10 01 11 图 3-3 卷积码树状图 毕业设计（论文）第 12 页 共 52 页 的译码规则若能在码字 C 中选择某一个iC使上式最大，则这种译码规则称为最大似然译码。而对于无记忆二进制对称信道，最大似然又等价于使汉明距离(,)id R C最小15。Viterbi 译码算法并不是在网格上一次比较所有可能的 2kL条路径（序列），而是接收一段，计算、比较、选择一段最可能的码段（分支），从而达到整个码序列是一个由最大似然函数的序列。Viterbi 译码算法的基本步骤如下：从某一时间单位 j=N 开始，对进入每一状态的所有长为 j 段分支的部分路径，计算本分路径度量。对每一状态，挑选并存储一条最小度量的部分路径及其部分度量值，称此路径为幸存路径。j 增加 1，把此时刻进入每一状态的所有分支度量同这些分支相连的前一时刻的幸存路径的度量相加，得到了此时刻进入每一状态的幸存路径，把存储并删去其他所有路径，这样幸存路径就延长了一个分支。若 jbef2 ar7=127 由 i0 更新 i1、i2、i3 bfly_a bfly_b-ar1=0？-ar5=0？回溯 图 5-8 加比选流程图 trn寄存器低16位数据处理 ar1=7-ar7=0？i0+i4+，aft-bef,i0=0 是 是 是 否 否 否 毕业设计（论文）第 31 页 共 52 页 5.5.2 加-比-选程序仿真 图 5-9 加-比-选仿真 通过初始化与加比选的程序后，我们得到图 5-9 所示的 bef 与 tab_trn空间的数据。bef 表示的是接收 192bit 输入序列得到的最终的分支度量值，tab_trn表示的是 96-8=88 级的路径选择情况。5.6 回溯 由于结束信息 0000 0000 的作用，最后的幸存路径的状态必为 0000 0000 状态，这个时候的度量值最大，所以从最后一级的 0000 0000 状态开始，根据 tab_trn记录的选择进行回溯。tab_trn 中 1 个字 16bit，用了 16 个字表示 256 个状态，即一级的状态。为了便于理解，我们可以把 16 个字记做 1 个单元。tab_trn 存储了输入序列后面的88 级的路径选择情况，所以需要 88*16=1408 字的空间。每个比特中存储的都是“0”或“1”,为“0”则表示选择两条路径中上面的一条。为“1”则表示选择两条路径中下面的一条。路径选择是由 CMPS 语句完成的。例:CMPS A,*AR4+毕业设计（论文）第 32 页 共 52 页 说明：比较 A 累加器的低 16 位和高 16 位，把较大值放在*AR4 中。如果 A（31-16）A(15-0),则把 A(31-16)送人*AR4 中，同时 TRN 左移 1 位，将 0 存入 TRN的第 0 位。否则*AR4 存入的是 A(15-0)，同时 TRN 左移一位将 1 存入 TRN 的第 0位。CMPS 语句完成后，TRN 每存储 16bit 就存入 tab_trn 中。那么我们如果知道节点位于哪一级哪一状态，我们就可以知道该节点的路径选择情况。根据图 4-5（2,1,9）卷积码的蝶形结构，由于回溯是从到达状态反推初始状态，所以我们可以整理归纳，得到回溯蝶形结构图，如图 5-10 所示。其中 0j255，其 j 为偶数。当到达状态为奇数时，即用 2 进制表示时最低位为 1 时，我们可以知道分支输入为 1；当到达状态为偶数时，即用 2 进制表示时最低位为 0 时，我们可以知道分支输入为 0。我们已经知道最末端的状态为 0，我们可以知道分支输入值，从 tab_trn 的最后一个单元的第 0 字第 0 位，由回溯蝶形结构我们可以知道初始状态 m。将初始状态看成是新的到达状态，我们也有了新的蝶形结构，测试这新的到达状态的最低位，我们可以知道分支输入值，由于 m=16*x+y，即 m 看做是 8 位 2 进制时，y 为 m 的低 4 位，x 为 m 的高 4 位。我们可以知道从 tab_trn 的倒数第二个单元的第 x 字第 y 字获得路径选择情况，从而得知新的初始状态 m。同理类推可以知道第 95 级到第 8 级的分支输入值。由于从第 8 级到第 0 级，节点间没有交叉，没有路径可以选择，我们可以直接由表 4-1（2,1,9）状态转换表查得分支输入值。0(trn)1(trn)1(trn)0(trn)j/2 j/2+1 j j+1 图 5-10 回溯蝶形结构 毕业设计（论文）第 33 页 共 52 页 5.6.1 回溯流程图 加-比-选 到达状态置 0 由到达状态得分支输入值 查 tab_trn，更新到达状态 87 次？更新第 8 级到第 0 级的分支输入值 分支输入值输出到output 空间 结束 否 是 图 5-11 回溯流程图 毕业设计（论文）第 34 页 共 52 页 5.6.2 回溯仿真图 图 5-12 译码输入 图 5-13 译码输出 图 5-12、图 5-13 通过与图 4-2 编码输入、图 4-3 编码输出互相比较，我们可以看出得到了正确的译码结果，说明该程序能够实现 Viterbi 译码。5.7 Viterbi 纠错测试 下面做的是 Viterbi 译码程序纠正随机差错的尝试，在原来的输入的最后一列输入信息全部出错。更改后的输入序列如图 5-14 所示。图 5-14 错误的输入序列 经过 Viterbi 译码程序后，我们得到纠错译码输出，如图 5-15 所示。毕业设计（论文）第 35 页 共 52 页 图 5-15 纠错译码输出 对比图 5-15 纠错译码输出与图 5-12 译码输出，发现二者一模一样，成功验证了 Viterbi 译码具有纠正随机错误的能力。5.8 本章小结 本章对 Viterbi 译码进行详细的描述，按照实现功能、设计方案、流程图具体说明了初始化、加比选、回溯 3 个模块。按照 DSP 的特点对每个模块进行编写，并对每个模块进行了仿真测试。最后验证了 Viterbi 译码具有纠正错误的能力。毕业设计（论文）第 36 页 共 52 页 总结 随着对通信质量的不断要求，信道纠错编码作为提高信息传输可靠性的一种重要手段，越来越受到重视。本文以 N-CDMA 标准为研究背景，利用 TI 公司TMS320C54x 系列 DSP 的集成软件 CCS 为开发环境，实现了速率 1/2 的（2，1，9）卷积码编译码。首先，介绍了卷积编码与译码的原理。随后以复杂低的(2,1,3)卷积码为例分析 Viterbi 译码初步实现，从而了解 Viterbi 译码的基本实现步骤，有个具体的概念。然后，开始了解纠错能力更强但复杂较高的(2,1,9)卷积码 Viterbi 译码器。从(2,1,3)Viterbi 译码的基础上扩展深入，提出了“查表法”并结合“初始化”、“加-比-选”和“回溯”这 3 个步骤，并具体给出了实现方案与流程图，从而实现高效率的 Viterbi 译码器。最后对译码程序进行编译和仿真，得出数据传输发生错误时仍能还原出原始数据，也就是说程序起了作用。毕业设计（论文）第 37 页 共 52 页 参考文献 1胥凌燕、李定志 Viterbi 译码碟型算法的实现及性能分析J.通信技术，2007.5 2陈源、江修富 Viterbi 算法的关键问题研究及 DSP 实现J.装备指挥技术 学院学报，2005.10 3赵冰 卷积编码及基于 DSP 的 Viterbi 译码器设计J.信息与控制，2002.10 4方向前、魏平俊 基于 DSP 的 Viterbi 译码器J.半导体技术，2005.6 5张慎 卷积码编码器及 Viter