1、 四川师范大学本科毕业设计卷积码编码与 viterbi译码的设计与实现学生姓名院系名称 物理与电子工程学院专业名称 电子信息工程班 级 2007 级 4 班学 号 20070704指导教师 陈万川完成时间 2011 年 5 月 11 日卷积码编码与 viterbi译码的设计与实现设计学生姓名： 指导老师：陈万川内容摘要：介绍了数字通信系统中一种卷积码为特比译码的软件实现算法,在 C 环境实现了卷积码 Viterbi 译码功能 ,在程序实现中充分利用了卷积码的特性, 运用网格图和回溯以得到译码输出。为了在实际中更好地利用卷积码的优异性能,文章从应用角度出发,对卷积码的译码方法进行了分析,给出了在
2、不同的情况下,如何利用各种译码方法,得到理论性能和实际应用的最佳结合。 (2,1,3)卷积码搭建了简单的系统来进行纠错展示,可以实现从编码,加入错误,译码,输入输出码字对比等基本功能,另外加入了交互模块,用户可以自己设定错误比特的数目和位置,使纠错功能显而易见。关键词：卷积编码；维特比译码；卷积码编码器;信道编码;信息论;Design Of Decoding Methods of Convolutional CodesAbstract:Describes a digital communication system, convolutional code is Viterbi decoding
3、 algorithm of the software.In the C environment to achieve the convolutional code Viterbi decoding functions . In the program to achieve full use of the characteristics of convolutional codes, using the grid map and to get the decoder output .In order to practically utilize the excellent performance
4、 of convolutional codes ,several decoding methods of convolutional codes are analyzed in the paper from the application angle . (2,1,3) Convolutional Codes built a simple system for correcting display can be realized from coding, joined errors, decoding, the input and output code contrast basic func
5、tions, adding to its interactive modules, Users can set their own errors and the number of bits, so that error-correcting functions obvious.Key words :convolution code ; viterbi decoding；convolutional coder ;channel coding ;information t heory .目 录1 概述 .11.1 课题背景及意义 .11.1.1 数字通信系统 .11.1.2 信道编解码 .21.
6、2 卷积码编码与维特比译码的发展应用 .31.3 设计要求 .42 信道编解码理论介绍 .42.1 纠错码基本理论 .42.1.1 纠错码概念 .42.1.2 基本原理和性能参数 .42.1.3 实现 .42.2 信道编码定理 .52.3 几种常用的纠错码 .62.4 卷积码编码原理及算法 .72.4.1 卷积码基本原理 .72.4.2 卷积码纠错性能 .82.5 卷积码表示方法 .82.6 卷积码译码方法 .102.7 viterbi 译码 原理及算法 .112.7.1 Viterbi 译码原理简述 .112.7.2 Viterbi 译码算法描述 .122.8 维特比译码算法性能 .123
7、卷积码编码与维特比译码的设计 .133.1 卷积码编码设计 .133.1.1 卷积码编码器原理 .133.1.2 卷积码编码过程 .133.2 viterbi 译码设计 .153.2.1 维特比译码器原理 .153.2.2 维特比译码过程 .163.3 对译码算法及实现的优化 .183.3.1 留存路径更新算法优化 .183.3.2 考虑数据溢出问题 .193.3.3 优化判决输出 .193.4 交互模块 .194 卷积码编码译码器的实现 .195 总结 .20致谢 .20参考文献 .20附录 .211卷积码编码与 viterbi译码的设计与实现1 概述1.1 课题背景及意义1.1.1 数字通
8、信系统数字通信系统是传递信息所需的一切技术设备的总和，包括信息源、发送设各、传输介质、信息接收者和接收设备。数字通信系统传输的数据是数字化了的信息。单向数字通信系统的结构，如图 1 所示图 1数字通信系统信息源中，模拟信息源（如模拟式电话机、电视摄像机）输出的是幅度连续变化的信号，离散信息源（如计算机）输出的是离散的符号序列或文字。通过采样和量化可以将模拟信息变换为离散信息。发送设各的基本功能是使不同种类和速率的信息源与传输媒介相匹配，通常是将信息源产生的信息经过编码，并变换为便于传送的信号形式，送往传输介质。编码包括信源编码与信道编码两部分。信源编码把连续消息变换为数字信号，信道编码则使数字
9、信号与传输介质匹配，提高传输的可靠性和有效性。调制是多种变换方式中最常见的一种。发送设各还包括为达到某些特殊要求所进行的各种处理，如多路复用、保密处理、纠错编码处理等。传输介质是发送设备到接收设备之间信号传递所经过的媒介，例如：电磁波、红外线等无线传输介质，各种电缆、光缆、双绞线等有线传输介质。传输过程中必然会引入热噪声、衰减、脉冲等干扰。介质的固有特性和干扰特性直接关系到编码方式的选取。信息源接收者译码 解制编码 调制传输介质噪声扰2接收设备的基本功能是完成对发送的反变换（解调、译码、解密等），从带有干扰的信号中恢复出正确的原始信息，对于多路复用信号还包括解除多路复用和实现正确分路（或称输出
10、扫描）。双向通信要求通信双方都有发送设备和接收设备，如果两个方向共用一个传输媒介，则必须采用分频或分时的办法。信息的传输系统和交换系统组成完整的通信系统，直至构成复杂的通信网络。1.1.2 信道编解码数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象。所以通过信道编码这一环节，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干扰能力，可极大地避免码流传送中误码的发生。误码的处理技术有纠错、交织、线性内插等。 提高数据传输效率，降低误码率是信道编码的任务。信道编码的本质是增加通信的可靠性。但信道编码会使有用的信息数据传输减少，信
11、道编码的过程是在源数据码流中加插一些码元，从而达到在接收端进行判错和纠错的目的，这就是我们常常说的开销。这就好象我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装 5000 各玻璃杯的，包装后就只能装 4000 个了，显然包装的代价使运送玻璃杯的有效个数减少了。同样，在带宽固定的信道中，总的传送码率也是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价了。将有用比特数除以总比特数就等于编码效率了，不同的编码方式，其编码效率有所不同。 数字电视中常用的纠错编码，通常
12、采用两次附加纠错码的前向纠错（FEC）编码。RS 编码属于第一个 FEC，188 字节后附加 16 字节 RS 码，构成（204，188）RS 码，这也可以称为外编码。第二个附加纠错码的 FEC 一般采用卷积编码，又称为内编码。外编码和内编码结合一起，称之为级联编码。级联编码后得到的数据流再按规定的调制方式对载频进行调制。 前向纠错码（FEC）的码字是具有一定纠错能力的码型，它在接收端解码后，不仅可以发现错误，而且能够判断错误码元所在的位置，并自动纠错。这种纠错码信息不需要储存，不需要反馈，实时性好。所以在单向传输系统都采用这种信道编码方式。信道编码又称纠错编码，它与信源编码是信息传输的两个方
13、面。它们之间存在对偶的关系。应用信道译码直接对一些自然信息进行处理，可以去掉剩余度，以达到压缩数据的目的。 为了使一种码具有检错或纠错能力，必须对原码字增加多余的码元，以扩大码字之间的差别，使一个码字在一定数目内的码元上发生错误时，不致错成另一个码字。准确地说，即把原码字按某种规则变成有一定剩余度的码字，并使每个码字的码元间有一定的关系。关系的建立称为编码。码字到达收端后，用编码时所用的规则去检验。如果没有错误，则原规则一定满足，否则就不满足。由此可以根据编码规则是否满足以判定有无错误。当不能满足时，在可纠能力之内按一定的规则确定错误所在的位置，并予以纠正。纠错并恢复原码字的过程称为译码；码元
14、间的关系为线性时，称为线性码；否则称为非线性码。检错码与其他手段结合使用，可以纠错。检错反馈重发系统（ARQ 系统）就是一例。 3在构造纠错码时，将输入信息分成 k 位一组以进行编码。若编出的校验位仅与本组的信息位有关，则称这样的码为分组码。若不仅与本组的 k 个信息位有关，而且与前若干组的信息位有关，则称为格码。这种码之所以称为格码，是因为用图形分析时它象篱笆或格架。线性格码在运算时为卷积运算，所以叫卷积码。卷积码是深度空间通信系统和无线通信系统中常用的一种差错控制编码。在编码过程中,卷积码充分利用了各码字间的相关性。在与分组码同样的码率和设备复杂性的条件下,无论从理论上还是从实践上都证明,
15、卷积码的性能都比分组码具有优势。而且卷积码在实现最佳译码方面也较分组码容易。因此卷积码广泛应用于卫星通信，CDMA 数字移动通信等通信系统，是很有前途的一种编码方式。对其进行研究有很大的现实意义。1.2 卷积码编码与维特比译码的发展应用在现代通信系统中,前向纠错编码(FEC)得到了广泛的应用。其中,卷积编码是应用最广泛的一种。C.E.仙农在 1948 年发表在通信的数学理论一文中的信道编码定理指出：只要采用适当的纠错码，就可在多类信道上传输消息，其误码率 pe 可以任意小。可惜的是这一定理仅仅指出理论上可以达到的目标，而未能给出构造性的实现方法。自仙农的论文发表以来，人们经过持续不懈的努力已找
16、到多种好码，可以满足许多实用要求。但在理论上，仍存在一些问题未能解决。 R.W.汉明于 1950 年首先给出可以纠正一个独立错误的线性分组码汉明码。差不多与此同时 E.戈雷给出一种可以纠正三个错误的完备码。完备码虽然十分罕见，但有较大实用意义。1954 年 D.E.莫勒提出一种能纠正多个错误的码；I.S.里德则立即给出它的译码方法，用的是择多判决法，这种码常称为 RM 码。1957 年，E.普勒齐引入了循环码的概念。19591960 年出现了 BCH 码,引进有限域 的概念，解决了循环码的构造和性能估计等基本问题。后来成为线性分组码中最重要的一类码。它能纠正多个错误，且在实用范围内接近信道编码
17、定理所指出的误码率值。但当 n 增大时，其误码率不能呈指数下降。BCH 码的译码问题是 W.W.彼得森解决的;钱天闻则提供了一种系统地搜索根的方法。1967 年，E.R.伯利坎普提出一种迭代算法，大大简化了译码，使纠错码趋于实用。1970 年 .戈帕提出一种线性分组码的构造方法，原则上它可以达到吉尔伯特限，实现了理论上预期的目标。但至今仍未解决如何具体构造这种码的问题。 卷积码最早由 P.伊莱亚斯于 1955 年提出。它的纠错能力较强，设备复杂程度与分组码大体相当。首先获得成功的译码方法是序列译码。1967 年 A.J.维特比提出的译码算法，能较好地按最大似然准则译码，且在许多领域中均可应用。
18、卷积码是深度空间通信系统和无线通信系统中常用的一种差错控制编码。在编码过程中,卷积码充分利用了各码字间的相关性。在与分组码同样的码率和设备复杂性的条件下,无论从理论上还是从实践上都证明,卷积码的性能都比分组码具有优势。在卷积码译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息。而且卷积码的纠错能力随约束长度的增加而增强，差错率则随着约束长度增加而呈指数下4降 。卷积码(n,k,m) 主要用来纠随机错误，它的码元与前后码元有一定的约束关系而且卷积码在实现最佳译码方面也较分组码容易。因此卷积码广泛应用于卫星通信，CDMA 数字移动通信等通信系统，
19、是很有前途的一种编码方式。对其进行研究有很大的现实意义。1.3 设计要求本题目的基本任务就是根据编码理论中所学习的卷积码编码方法和viterbi 译码方法，运用 C 或 C+来设计开发一个编译码软件，实现对信息的编码和译码。要求所设计实现的编译码软件操作简便、快捷。本题目的实现主要涉及到编码理论、C 程序设计（或面向对象程序设计）等课程的相关内容，必须对相关知识熟练掌握。2信道编解码理论介绍2.1 纠错码基本理论2.1.1 纠错码概念纠错码(error correcting code)，在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。为使一种码具有检错或纠
20、错能力，须对原码字增加多余的码元，以扩大码字之间的差别 ，即把原码字按某种规则变成有一定剩余度（见信源编码）的码字，并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收端后，可以根据编码规则是否满足以判定有无错误。当不能满足时，按一定规则确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。检错码与其他手段结合使用，可以纠错。2.1.2 基本原理和性能参数纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间的汉明距离 d(x，y)来衡量。它的定义为码字 x 与 y 之间的对应位取不同值的码元个数。一种纠错码的最小距离 d 定义为该种码中任两个码字之间的距离的最小
21、值。一种码要能发现 e 个错误,它的最小距离 d 应不小于 e+1。若要能纠正 t 个错误，则 d 应不小于 2t+1。一个码字中非零码元的个数，称为此码字的汉明重量。一种码中非零码字的重量的最小值，称为该码的最小重量。对线性码来说，一种码的最小重量与其最小距离在数值上是相等的。 在构造线性码时，数字上是从 n 维空间中选一 k 维子空间，且使此子空间内各非零码字的重量尽可能大。当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定；而多项式完全可由它的根规定。这样,就容易对码进行构造和分析。这是BCH 码等循环码构造的出发点。一
22、般地说，构造一种码时，均设法将它与某种代数结构相联系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。若一种码的码长为 n，码字数为 M,或信息位为 h,以及最小距离为 d，则可把此码记作【n,M,d】码。若此码为线性码，常简记作(n，k)或5(n,k,d)码。人们还常用 R=log2M/n 表示码的信息率或简称码率,单位为比特/码元。R 越大,则每个码元所携带的信息量越大，编码效率越高。 2.1.3 实现纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长 n 越大,则误码率越小。但 n 越大，编译码设备也越复杂,且延迟也越大。人们希望找到的
23、译码方法是:误码率随码长 n 的增加按指数规律下降;译码的复杂程度随码长 n 的增加接近线性地增加；译码的计算量则与码长 n 基本无关。可惜，已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展，既使应用比较复杂的但性能良好的码，成本也并不太高。因此，纠错码的应用越来越广泛。 纠错码传输的都是数字信号。这既可用硬件实现，也可用软件实现。前者主要用各种数字电路，主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。硬件实现的速度较高，比软件可快几个数量级。 在传信率一定的情况下，如果采用纠错码提高可靠性，要求信
24、道的传输率增加，带宽加大。因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和半导体存储器等。 在分组码的研究中，谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等，也得到较多的研究。2.2 信道编码定理C.E.仙农在 1948 年发表在通信的数学理论一文中的信道编码定理指出：只要采用适当的纠错码，就可在多类信道上传输消息，其误码率 pe 可以任意小（1）()NERPe(1)式中 N 为码长；Er(R)为信息率 R 的函数,与信道有关。当 R 小于信道容量 C
25、时,Er(R)为正值。可惜的是这一定理仅仅指出理论上可以达到的目标，而未能给出构造性的实现方法。自仙农的论文发表以来，人们经过持续不懈的努力已找到多种好码，可以满足许多实用要求。但在理论上，仍存在一些问题未能解决。 R.W.汉明于 1950 年首先给出可以纠正一个独立错误的线性分组码汉明码。差不多与此同时 E.戈雷给出一种可以纠正三个错误的完备码。完备码虽然十分罕见，但有较大实用意义。1954 年 D.E.莫勒提出一种能纠正多个错误的码；I.S.里德则立即给出它的译码方法，用的是择多判决法，这种码常称为 RM 码。1957 年，E.普勒齐引入了循环码的概念。19591960 年出现了 BCH
26、码,引进有限域的概念，解决了循环码的构造和性能估计等基本问题。后来成为线性分组码中最重要的一类码。它能纠正多个错误，且在实用范围内接近信道编码定理所指出的误码率值。但当 n 增大时，其误码率不能呈指数下降。BCH 码的译码问题是 W.W.彼得森解决的;钱天闻则提供了一种系统地搜索根的方法。1967 年，E.R.伯利坎普提出一种迭代算法，大大简化了译码，使纠错码趋于实用。1970 年 .戈帕提出一种线性分组码的构造方法，原则上它可以达6到吉尔伯特限，实现了理论上预期的目标。但至今仍未解决如何具体构造这种码的问题。 卷积码最早由 P.伊莱亚斯于 1955 年提出。它的纠错能力较强，设备复杂程度与分
27、组码大体相当。首先获得成功的译码方法是序列译码。1967 年 A.J.维特比提出的译码算法，能较好地按最大似然准则译码，且在许多领域中均可应用。卷积码还可用代数方法译码。它的设备虽较简单，但性能较差。卷积码在理论上不如分组码成熟，所用的工具也比较多样，尚缺乏系统的、统一的方法处理。 分组码和卷积码不但可以用来纠正独立错误，而且可以用来恢复删除错误和纠正突发错误。如分组码中有里德-索洛蒙码,法尔码等；卷积码中有岩垂码及扩散卷积码等。 为了实现低的误码率，根据式(1)，要求码长 n 较大。但已知的大多数码，当 n 变大时不是性能欠佳或者难以构造，就是译码过分复杂，不容易实现。但是，可以利用好的码进
28、行级连，以得到性能更好的码。级连码的内码和外码，用分组码和卷积码都可以。这在深空通信中应用较多。2.3 几种常用的纠错码（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）卷积码卷积码非常适用于纠正随机错误，但是，解码算
29、法本身的特性却是：如果在解码过程中发生错误，解码器可能会导致突发性错误。为此在卷积码的上部采用 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 个字节的错误）。为了纠正这些成串发生的比特差错及一些突发错误，可以运用交织技术来分散这些误差，使长串的比
