卷积吗编码与维特比译码

卷积吗编码与维特比译码 四川师范大学本科毕业设计 卷积码编码与viterbi译码的设计与实现 学生姓名 院系名称 物理与电子学院 专业名称 电子信息工程 班 级 2007 级 4 班 学 号 20070704 指导教师 陈万川 完成时间 2011年 5月 11 日 卷积码编码与viterbi译码的设计与实现设计 学生姓名: 指导老师:陈万川 内容摘要: 介绍了数字通信系统中一种卷积码为特比译码的软件实现算法,在C环境实现了 卷积码Viterbi 译码功能,在程序实现中充分利用了卷积码的特性, 运用网格图和回 溯以得到译码输出。为了在实际中更好地利用卷积码的优异性能,文章从应用角度出 发,对卷积码的译码进行了,给出了在不同的情况下,如何利用各种译码方法, 得到理论性能和实际应用的最佳结合。 (2,1,3)卷积码搭建了简单的系统来进行纠错 展示,可以实现从编码,加入错误,译码,输入输出码字对比等基本功能,另外加入了交 互模块,用户可以自己设定错误比特的数目和位置,使纠错功能显而易见。 关键词:卷积编码;维特比译码;卷积码编码器;信道编码;信息论; Design Of Decoding Methods of Convolutional Codes Abstract: Describes a digital communication system, convolutional code is Viterbi decoding 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 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 functions, 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 概述 ................................................................. 1 1.1 课题背景及意义 ................................................. 1 1.1.1数字通信系统 .............................................. 1 1.1.2信道编解码 ................................................ 2 1.2卷积码编码与维特比译码的发展应用 ................................ 3 1.3设计要求 ........................................................ 4 2信道编解码理论介绍 ................................................... 4 2.1纠错码基本理论 .................................................. 4 2.1.1纠错码概念 ................................................ 4 2.1.2基本原理和性能参数 ........................................ 4 2.1.3实现 ...................................................... 4 2.2信道编码定理 .................................................... 5 2.3几种常用的纠错码 ................................................ 6 2.4卷积码编码原理及算法 ............................................ 7 2.4.1卷积码基本原理 ............................................ 7 2.4.2卷积码纠错性能 ............................................ 8 2.5卷积码表示方法 .................................................. 8 2.6卷积码译码方法 ................................................. 10 2.7 viterbi译码原理及算法 ......................................... 11 2.7.1 Viterbi 译码原理简述 .................................... 11 2.7.2 Viterbi 译码算法描述 ..................................... 12 2.8维特比译码算法性能 ............................................. 12 3卷积码编码与维特比译码的设计 ........................................ 13 3.1卷积码编码设计 ................................................. 13 3.1.1卷积码编码器原理 ......................................... 13 3.1.2卷积码编码过程 ........................................... 13 3.2 viterbi译码设计 ............................................... 15 3.2.1维特比译码器原理 ......................................... 15 3.2.2维特比译码过程 ........................................... 16 3.3对译码算法及实现的优化 ......................................... 18 3.3.1留存路径更新算法优化 ..................................... 18 3.3.2 考虑数据溢出问题 ....................................... 19 3.3.3 优化判决输出 ........................................... 19 3.4交互模块 ....................................................... 19 4卷积码编码译码器的实现 .............................................. 19 5 ................................................................ 20 致谢 .................................................................. 20 参考文献 .............................................................. 20 附录 .................................................................. 21 卷积码编码与viterbi译码的设计与实现 1 概述 1.1 课题背景及意义 1.1.1数字通信系统 数字通信系统是传递信息所需的一切技术设备的总和，包括信息源、发送设各、传输介质、信息接收者和接收设备。数字通信系统传输的数据是数字化了的信息。单向数字通信系统的结构，如图 1所示 信 息 编码 调制 源 传输介质 噪声扰 接 收 解制 译码 者 图1数字通信系统 信息源中，模拟信息源(如模拟式电话机、电视摄像机)输出的是幅度连续变化的信号，离散信息源(如计算机)输出的是离散的符号序列或文字。通过采样和量化可以将模拟信息变换为离散信息。发送设各的基本功能是使不同种类和速率的信息源与传输媒介相匹配，通常是将信息源产生的信息经过编码，并变换为便于传送的信号形式，送往传输介质。 编码包括信源编码与信道编码两部分。信源编码把连续消息变换为数字信号，信道编码则使数字信号与传输介质匹配，提高传输的可靠性和有效性。调制是多种变换方式中最常见的一种。发送设各还包括为达到某些特殊要求所进行的各种处理，如多路复用、保密处理、纠错编码处理等。 传输介质是发送设备到接收设备之间信号传递所经过的媒介，例如:电磁波、红外线等无线传输介质，各种电缆、光缆、双绞线等有线传输介质。传输过程中必然会引入热噪声、衰减、脉冲等干扰。介质的固有特性和干扰特性直接关系到编码方式的选取。 1 接收设备的基本功能是完成对发送的反变换(解调、译码、解密等)，从带有干扰的信号中恢复出正确的原始信息，对于多路复用信号还包括解除多路复用和实现正确分路(或称输出扫描)。 双向通信要求通信双方都有发送设备和接收设备，如果两个方向共用一个传输媒介，则必须采用分频或分时的办法。信息的传输系统和交换系统组成完整的通信系统，直至构成复杂的通信网络。 1.1.2信道编解码 数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象。所以通过信道编码这一环节，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干扰能力，可 极大地避免码流传送中误码的发生。误码的处理技术有纠错、交织、线性内插等。 提高数据传输效率，降低误码率是信道编码的任务。信道编码的本质是增加通信的可靠性。但信道编码会使有用的信息数据传输减少，信道编码的过程是在源数据码流中加插一些码元，从而达到在接收端进行判错和纠错的目的，这就是我们常常说的开销。这就好象我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装5000各玻璃杯的，包装后就只能装4000个了，显然包装的代价使运送玻璃杯的有效个数减少了。同样，在带宽固定的信道中，总的传送码率也是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价了。将有用比特数除以总比特数就等于编码效率了，不同的编码方式，其编码效率有所不同。 数字电视中常用的纠错编码，通常采用两次附加纠错码的前向纠错(FEC) ，188字节后附加16字节RS码，构成(204，188)编码。RS编码属于第一个FEC RS码，这也可以称为外编码。第二个附加纠错码的FEC一般采用卷积编码，又称为内编码。外编码和内编码结合一起，称之为级联编码。级联编码后得到的数据流再按规定的调制方式对载频进行调制。 前向纠错码(FEC)的码字是具有一定纠错能力的码型，它在接收端解码后，不仅可以发现错误，而且能够判断错误码元所在的位置，并自动纠错。这种纠错码信息不需要储存，不需要反馈，实时性好。所以在单向传输系统都采用这种信道编码方式。 信道编码又称纠错编码，它与信源编码是信息传输的两个方面。它们之间存在对偶的关系。应用信道译码直接对一些自然信息进行处理，可以去掉剩余度，以达到压缩数据的目的。 为了使一种码具有检错或纠错能力，必须对原码字增加多余的码元，以扩大码字之间的差别，使一个码字在一定数目内的码元上发生错误时，不致错成另一个码字。准确地说，即把原码字按某种规则变成有一定剩余度的码字，并使每个码字的码元间有一定的关系。关系的建立称为编码。码字到达收端后，用编码时所用的规则去检验。如果没有错误，则原规则一定满足，否则就不满足。由此可以根据编码规则是否满足以判定有无错误。当不能满足时，在可纠能力之内按一定的规则确定错误所在的位置，并予以纠正。纠错并恢复原码字的过程称为译码;码元间的关系为线性时，称为线性码;否则称为非线性码。检错码与其他手段结合使用，可以纠错。检错反馈重发系统(ARQ系统)就是一例。 在构造纠错码时，将输入信息分成 k位一组以进行编码。若编出的校验位仅与本组的信息位有关，则称这样的码为分组码。若不仅与本组的 k个信息位 2 有关，而且与前若干组的信息位有关，则称为格码。这种码之所以称为格码，是因为用图形分析时它象篱笆或格架。线性格码在运算时为卷积运算，所以叫卷积码。卷积码是深度空间通信系统和无线通信系统中常用的一种差错控制编码。在编码过程中,卷积码充分利用了各码字间的相关性。在与分组码同样的码率和设备复杂性的条件下,无论从理论上还是从实践上都证明,卷积码的性能都比分组码具有优势。而且卷积码在实现最佳译码方面也较分组码容易。因此卷积码广泛应用于卫星通信，CDMA数字移动通信等通信系统，是很有前途的一种编码方式。对其进行研究有很大的现实意义。 1.2卷积码编码与维特比译码的发展应用 在现代通信系统中,前向纠错编码(FEC)得到了广泛的应用。其中,卷积编码是应用最广泛的一种。C.E.仙农在1948年发表在《通信的数学理论》一文中的信道编码定理指出:只要采用适当的纠错码，就可在多类信道上传输消息，其误码率pe可以任意小。可惜的是这一定理仅仅指出理论上可以达到的目标，而未能给出构造性的实现方法。自仙农的论文发表以来，人们经过持续不懈的努力已找到多种好码，可以满足许多实用要求。但在理论上，仍存在一些问题未能解决。 R.W.汉明于1950年首先给出可以纠正一个独立错误的线性分组码??汉明码。差不多与此同时E.戈雷给出一种可以纠正三个错误的完备码。完备码虽然十分罕见，但有较大实用意义。 1954年D.E.莫勒提出一种能纠正多个错误的码;I.S.里德则立即给出它的译码方法，用的是择多判决法，这种码常称为RM码。 1957年，E.普勒齐引入了循环码的概念。1959,1960年出现了BCH码,引进有限域 的概念，解决了循环码的构造和性能估计等基本问题。后来成为线性分组码中最重要的一类码。它能纠正多个错误，且在实用范围内接近信道编码定理所指出的误码率值。但当 n增大时，其误码率不能呈指数下降。BCH码的译码问题是W.W.彼得森解决的;钱天闻则提供了一种系统地搜索根的方法。 1967年，E.R.伯利坎普提出一种迭代算法，大大简化了译码，使纠错码趋于实用。 1970年В.Д.戈帕提出一种线性分组码的构造方法，原则上它可以达到吉尔伯特限，实现了理论上预期的目标。但至今仍未解决如何具体构造这种码的问题。 卷积码最早由P.伊莱亚斯于1955年提出。它的纠错能力较强，设备复杂程度与分组码大体相当。首先获得成功的译码方法是序列译码。1967年A.J.维特比提出的译码算法，能较好地按最大似然准则译码，且在许多领域中均可应用。 卷积码是深度空间通信系统和无线通信系统中常用的一种差错控制编码。在编码过程中,卷积码充分利用了各码字间的相关性。在与分组码同样的码率和设备复杂性的条件下,无论从理论上还是从实践上都证明,卷积码的性能都比分组码具有优势。在卷积码译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息。而且卷积码的纠错能力随约束长度的增加而增强，差错率则随着约束长度增加而呈指数下降 。卷积码(n,k,m) 主要用来纠随机错误，它的码元与前后码元有一定的约束关系而且卷积码在实现最佳译码方面也较分组码容易。因此卷积码广泛应用于卫星通信，CDMA数字移动通信等通信系统，是很有前途的一种编码方式。对其进行研究有很大的现实意义。 3 1.3设计要求 本题目的基本任务就是根据编码理论中所学习的卷积码编码方法和viterbi译码方法，运用C或C++来设计开发一个编译码软件，实现对信息的编码和译码。要求所设计实现的编译码软件操作简便、快捷。 本题目的实现主要涉及到编码理论、C程序设计(或面向对象程序设计)等课程的相关内容，必须对相关知识熟练掌握。 2信道编解码理论介绍 2.1纠错码基本理论 2.1.1纠错码概念 纠错码(error correcting code)，在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。为使一种码具有检错或纠错能力，须对原码字增加多余的码元，以扩大码字之间的差别 ，即把原码字按某种规则变成有一定剩余度(见信源编码)的码字，并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收端后，可以根据编码规则是否满足以判定有无错误。当不能满足时，按一定规则确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。检错码与其他手段结合使用，可以纠错。 2.1.2基本原理和性能参数 纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间的汉明距离 d(x，y)来衡量。它的定义为码字x与y之间的对应位取不同值的码元个数。一种纠错码的最小距离 d定义为该种码中任两个码字之间的距离的最小值。一种码要能发现e个错误,它的最小距离d应不小于e+1。若要能纠正t个错误，则d应不小于2t+1。一个码字中非零码元的个数，称为此码字的汉明重量。一种码中非零码字的重量的最小值，称为该码的最小重量。对线性码来说，一种码的最小重量与其最小距离在数值上是相等的。 在构造线性码时，数字上是从n维空间中选一k维子空间，且使此子空间内各非零码字的重量尽可能大。当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定;而多项式完全可由它的根规定。这样,就容易对码进行构造和分析。这是BCH码等循环码构造的出发点。一般地说，构造一种码时，均设法将它与某种代数结构相联系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。若一种码的码长为n，码字数为M,或信息位为h,以及最小距离为d，则可把此码记作【n,M,d】码。若此码为线性码，常简记作(n，k)或(n,k,d)码。人们还常用R=log2M/n表示码的信息率或简称码率,单位为比特/码元。R越大,则每个码元所携带的信息量越大，编码效率越高。 2.1.3实现 纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长n越大,则误码率越小。但n越大，编译码设备也越复杂,且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的 4 复杂程度随码长n的增加接近线性地增加;译码的计算量则与码长 n基本无关。可惜，已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展，既使应用比较复杂的但性能良好的码，成本也并不太高。因此，纠错码的应用越来越广泛。 纠错码传输的都是数字信号。这既可用硬件实现，也可用软件实现。前者主要用各种数字电路，主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。硬件实现的速度较高，比软件可快几个数量级。 在传信率一定的情况下，如果采用纠错码提高可靠性，要求信道的传输率增加，带宽加大。因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和半导体存储器等。 在分组码的研究中，谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等，也得到较多的研究。 2.2信道编码定理 C.E.仙农在1948年发表在《通信的数学理论》一文中的信道编码定理指出:只要采用适当的纠错码，就可在多类信道上传输消息，其误码率pe可以任意小 ,NER() (1) Pe,e (1)式中N为码长;Er(R)为信息率R的函数,与信道有关。当R小于信道容量C时,Er(R)为正值。可惜的是这一定理仅仅指出理论上可以达到的目标，而未能给出构造性的实现方法。自仙农的论文发表以来，人们经过持续不懈的努力已找到多种好码，可以满足许多实用要求。但在理论上，仍存在一些问题未能解决。 R.W.汉明于1950年首先给出可以纠正一个独立错误的线性分组码??汉明码。差不多与此同时E.戈雷给出一种可以纠正三个错误的完备码。完备码虽然十分罕见，但有较大实用意义。1954年D.E.莫勒提出一种能纠正多个错误的码;I.S.里德则立即给出它的译码方法，用的是择多判决法，这种码常称为RM码。1957年，E.普勒齐引入了循环码的概念。1959,1960年出现了BCH码,引进有限域的概念，解决了循环码的构造和性能估计等基本问题。后来成为线性分组码中最重要的一类码。它能纠正多个错误，且在实用范围内接近信道编码定理所指出的误码率值。但当 n增大时，其误码率不能呈指数下降。BCH码的译码问题是W.W.彼得森解决的;钱天闻则提供了一种系统地搜索根的方法。 1967年，E.R.伯利坎普提出一种迭代算法，大大简化了译码，使纠错码趋于实用。1970年В.Д.戈帕提出一种线性分组码的构造方法，原则上它可以达到吉尔伯特限，实现了理论上预期的目标。但至今仍未解决如何具体构造这种码的问题。 卷积码最早由P.伊莱亚斯于1955年提出。它的纠错能力较强，设备复杂程度与分组码大体相当。首先获得成功的译码方法是序列译码。1967年A.J.维特比提出的译码算法，能较好地按最大似然准则译码，且在许多领域中均可应用。卷积码还可用代数方法译码。它的设备虽较简单，但性能较差。卷积码在理论上不如分组码成熟，所用的工具也比较多样，尚缺乏系统的、统一的方法处理。 5 分组码和卷积码不但可以用来纠正独立错误，而且可以用来恢复删除错误和纠正突发错误。如分组码中有里德-索洛蒙码,法尔码等;卷积码中有岩垂码及扩散卷积码等。 为了实现低的误码率，根据式(1)，要求码长n较大。但已知的大多数码，当 n变大时不是性能欠佳或者难以构造，就是译码过分复杂，不容易实现。但是，可以利用好的码进行级连，以得到性能更好的码。级连码的内码和外码，用分组码和卷积码都可以。这在深空通信中应用较多。 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)卷积码 卷积码非常适用于纠正随机错误，但是，解码算法本身的特性却是:如果在解码过程中发生错误，解码器可能会导致突发性错误。为此在卷积码的上部采用RS码块， RS码适用于检测和校正那些由解码器产生的突发性错误。所以卷积码和RS码结合在一起可以起到相互补偿的作用。卷积码分为两种: ?基本卷积码: 基本卷积码编码效率为，η,1/2, 编码效率较低,优点是纠错能力强。 ?收缩卷积码: 如果传输信道质量较好，为提高编码效率，可以采样收缩截短卷积码。有编码效率为:η,1/2、2/3、3/4、5/6、7/8这几种编码效率的收缩卷积码。编码效率高，一定带宽内可传输的有效比特率增大,但纠错能力越减弱。 (3)Turbo码 1993 年诞生的Turbo 码，单片Turbo 码的编码/解码器，运行速率达40Mb/s。该芯片集成了一个32×32 交织器，其性能和传统的RS 外码和卷积内码的级联一样好。所以Turbo码是一种先进的信道编码技术，由于其不需要进行两次编码，所以其编码效率比传统的RS+卷积码要好。 (4)交织 在实际应用中，比特差错经常成串发生，这是由于持续时间较长的衰落谷点会影响到几个连续的比特，而信道编码仅在检测和校正单个差错和不太长的差错串时才最有效(如RS只能纠正8个字节的错误)。为了纠正这些成串发生的比特差错及一些突发错误，可以运用交织技术来分散这些误差，使长串的比特差错变成短串差错，从而可以用前向码对其纠错，例如:在DVB-C系统中，RS(204,188)的纠错能力是8个字节，交织深度为12，那么纠可抗长度为8×12,96个字节的突发错误。实现交织和解交织一般使用卷积方式。 交织技术对已编码的信号按一定规则重新排列，解交织后突发性错误在时间上被分散，使其类似于独立发生的随机错误，从而前向纠错编码可以有效的进行纠错，前向纠错码加交积的作用可以理解为扩展了前向纠错的可抗长度字节。纠错能力强的编码一般要求的交织深度相对较低。纠错能力弱的则要求更深的交织深度。 6 一般来说，对数据进行传输时，在发端先对数据进行FEC编码，然后再进行交积处理。在收端次序和发端相反，先做去交积处理完成误差分散，再FEC解码实现数据纠错。交积不会增加信道的数据码元。 (5)伪随机序列扰码 进行基带信号传输的缺点是其频谱会因数据出现连“1”和连“0”而包含大的低频成分，不适应信道的传输特性,也不利于从中提取出时钟信息。解决办法之一是采用扰码技术,使信号受到随机化处理，变为伪随机序列，又称为“数据随机化”和“能量扩散”处理。扰码不但能改善位定时的恢复质量，还可以使信号频谱平滑，使帧同步和自适应同步和自适应时域均衡等系统的性能得到改善。 扰码虽然“扰乱”了原有数据的本来规律，但因为是人为的“扰乱”，在接收端很容易去加扰，恢复成原数据流。 实现加扰和解码，需要产生伪随机二进制序列(PRBS)再与输入数据逐个比特作运算。PRBS也称为m序列，这种m序列与TS的数据码流进行模2加运算后，数据流中的“1”和“0”的连续游程都很短，且出现的概率基本相同。 利用伪随机序列进行扰码也是实现数字信号高保密性传输的重要手段之一。一般将信源产生的二进制数字信息和一个周期很长的伪随即序列模2相加，就可将原信息变成不可理解的另一序列。这种信号在信道中传输自然具有高度保密性。在接收端将接收信号再加上(模2和)同样的伪随机序列，就恢复为原来发送的信息。 2.4卷积码编码原理及算法 2.4.1卷积码基本原理 卷积码是1955年由Elias等人提出的，是一种非常有前途的编码方法。我们在一些资料上可以找到关于分组码的一些介绍，分组码的实现是将编码信息分组单独进行编码，因此无论是在编码还是译码的过程中不同码组之间的码元无关。卷积码和分组码的根本区别在于，它不是把信息序列分组后再进行单独编码，而是由连续输入的信息序列得到连续输出的已编码序列。即进行分组编码时，其本组中的n-k个校验员仅与本组的k个信息元有关，而与其它各组信息无关;但在卷积码中，其编码器将k个信息码元编为n个码元时，这n个码元不仅与当前段的k个信息有关，而且与前面的(m,1)段信 息有关(m为编码的约束长度)。 同样，在卷积码译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息。而且卷积码的纠错能力随约束长度的增加而增强，差错率则随着约束长度增加而呈指数下降 。卷积码(n,k,m) 主要用来纠随机错误，它的码元与前后码元有一定的约束关系，编码复杂度可用编码约束长度m*n来表示。一般地，最小距离d表明了卷积码在连续m段以内的距离特性，该码可以在m个连续码流内纠正(d-1)/2个错误。卷积码的纠错能力不仅与约束长度有关，还与采用的译码方式有关。总之，由于n，k较小，且利用了各组之间的相关性，在同样的码率和设备的复杂性条件下，无论理论上还是实践上都证明:卷积码的性能至少不比分组码差。 以二元码为例。输入信息序列为u,(u0，u1，„)，其多项式表示为u(x),u0+u1x，„，ulxl，„。编码器的连接可用多项式表示为g(1,1)(x),1+x+x2和g(1,2)(x),1+x2，称为码的子生成多项式。它们的系数矢量g(1,1)=(111) 7 和g(1,2)=(101)称作码的子生成元。以子生成多项式为阵元构成的多项式矩阵G(x),[g(1,1)(x),g(1,2)(x)]，称为码的生成多项式矩阵。由生成元构成的半无限矩阵 称为码的生成矩阵。其中(11,10,11)是由g(1,1)和g(1,2)交叉连接构成。编码器输出序列为c,u?G，称为码序列，其多项式表示为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)]。编码器的结构由k0×n0阶生成多项式矩阵给定。输出码序列由n0个子序列组成，即c(x),[c(x),c(x)，„，c(x)]，且c(x)=u(x)?G(x)。若m是所有子生成多项式g(x)中最高次式的次数，称这种码为(n0，k0，m)卷积码。 2.4.2卷积码纠错性能 卷积码中编码后的n个码元不仅与当前段的k个信息有关，而且也与前面(N-1)段的信息有关，编码过程中相互关联的码元为nN个。因此，这N时间内的码元数目nN通常被称为这种码的约束长度。卷积码的纠错能力随着N的增加而增大，在编码器复杂程度相同的情况下，卷段积码的性能优于分组码。 卷积码也是分组的, 但它的监督元不仅与本组的信息元有关, 而且还与前若干组的信息元有关。卷积码根据需要, 有不同的结构及相应的纠错能力,但都有类似的编码规律。值得指出的是一种( 2, 1)卷积码, 其码率为1 /2, 它的监督位只有1位, 编码效率较高, 也比较简单。如使用较长的约束长度, 则既可以纠正突发差错, 也可以纠正随机差错。 2.5卷积码表示方法 描述卷积码编码器过程的方法有很多，如矩阵法、多项式、码树和网格图等，这里我们主要介绍和卷积码编码器结构密切相关的多项式法，以及与卷积码译码密切相关的网格图法。 (1)多项式法 以二元码为例。输入信息序列为u,(u0，u1，„)，其多项式表示为u(x),u0+u1x，„，ulxl，„。编码器的连接可用多项式表示为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)]，称为码的生成多项式矩阵。由生成元构成的半无限矩阵 (2) 称为码的生成矩阵。其中(11,10,11)是由和交叉连接构成。编码器输出序列为c,u?G，称为码序列，其多项式表示为c(x)，它可看作是两个子码 8 序列c(x)和c(x)经过合路开关S合成的，其中c(x),u(x)?(x)和c(x),u(x)g(x),它们分别是信息序列和相应子生成元的卷积，卷积码由此得名。 在一般情况下，输入信息序列经过一个时分开关被分成k0个子序列,分别以u(x)表示,其中i=1，2,„k0，即u(x),[u(x),„,u(x)]。编码器的结构由k0×n0阶生成多项式矩阵 (3) 给定。输出码序列由n0个子序列组成，即 c(x),[c(x),c(x)，„，c(x)]，且c(x)=u(x)?G(x)。 (2)状态图 将编码器寄存器中的内容组合(x(n-1)、x(n-2))定义为编码器状态。如以(2，1，2)为例，则该编码器的状态有四种:00，10，01和11，下面分别用a，b，c，d来代替。编码器在每一个时钟沿打入一个输入信息x(n)，因此图示内容就变为(x(n)，x(n-1))即状态发生了转移，并同时输出G0(n)、G1(n)。由此我们可以将编码过程用图所示的状态图表示。 b 0111 a00 d100010 1101 c 图2编码状态图 由图所示，随着信息序列不断输入，编码器就不断从一个状态转移到另一个状态并同时输出相应的码序列，所以图2所示状态图可以简单直观的描述编码器的编码过程。因此通过状态图很容易给出输入信息序列的编码结果，假定输入序列为110100，首先从零状态开始即图示a状态，由于输入信息为“1”，所以下一状态为c并输出“11”，继续输入信息“1”，由图知下一状态为d、输出“01”„„其它输入信息依次类推，按照状态转移路径a->c->d->b->c->b->a 输出其对应的编码结果“110101001011”。 (3)网格图 状态图可以完整的描述编码器的工作过程，但是其只能显示状态转移的过程而不能显示状态转移发生的时刻，由此引出用来表示卷积码的另一种常用方法— 9 网格图。 图3网格图 网格图就是时间与对应状态的转移图(如图)，在网格图中每一个点表示该时刻的状态，状态之间的连线表示状态转移。通过观察网格图可以发现在网格图中输入信息x(n)并没有标出，但如观察到转移后的状态表示(x(n)，x(n-1))就可以发现输入信息已经隐含在转移后的状态中。在图中还可以发现两个网格图不同主要集中在转移后状态位置不同。重新排序结构(即所谓蝶型结构)是为了优化运算而设计的，因为其中蝶型与蝶型之间是相互独立的。 2.6卷积码译码方法 卷积码的Viterbi 译码若信道干扰序列为 K()(0),,Ftb,bt1，ae (4) ()()()lllEeee,(,,...,)in120其中。接收序列为 ,iRxcxExRx()()(),，,,i0i, (5) ()()()lll()()()lllRrrr,(,,...,)rce,，jjjin120其中和。 这里“+”为模 2 运算(q=p元码按模p运算)。译码就是根据编码规则和信道干扰的统计特性，对信息序列u(x)作出估值的方法。常用的有三类译码方法，即代数译码、维特比译码和序贯译码。 (1)代数译码 代数译码是将卷积码的一个编码约束长度的码段看作是[n0(m+1)，k0(m+1)]线性分组码，每次根据(m+1)分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。如果假设输入的信息序列为,(10111)，相应的编码输出序列为 c,(11100001100111)。在未超出编码约束长度的情况下，可以通过译码时将接受序列与所有可能的输出编码序列进行比较，通过比较可以得到最小距离，进而可以得到可能的最大概率。按同样方法判决，将每一位进行比较，进行纠错。若此时接收序列R,(10100001110111),先根据R的前三个分支(101000)和码树中前三个分支长的所有可能的 8条路径 10 (000000„)、(000011„)、(001110„)、(001101„)、(111011„)、(111000„)、 (110101„)和(110110„)进行比较，可知(111001)与接收序列(101000)的距离最小，于是判定第 0分支的信息数字为 0。然后以R的第 1,3分支数字(100001)按同样方法判决,依此类推下去,最后得到信息序列的估值为=(10111)，遂实现了纠错。这种译码法，译码时采用的接收数字长度或译码约束长度为(m+1)n0，所以只能纠正不多于(dmin-1)/2个错误(n长上的)。实用中多采用反馈择多逻辑译码法实现。 (2)维特比译码 维特比译码是根据接收序列在码的格图上找出一条与接收序列距离(或其他量度)为最小的一种算法。它和运筹学中求最短路径的算法相类似。若接收序列为R=(10100101100111)，译码器从某个状态,例如从状态ɑ出发,每次向右延伸一个分支(对于l,L,从每个节点出发都有2=2种可能的延伸,其中L是信息序列段数,对l?L，只有一种可能),并与接收数字相应分支进行比较,计算它们之间的距离，然后将计算所得距离加到被延伸路径的累积距离值中。对到达每个状态的各条路径(有2=2条)的距离累积值进行比较，保留距离值最小的一条路径，称为幸存路径(当有两条以上取最小值时，可任取其中之一),译码过程如图。图中标出到达各级节点的幸存路径的距离累积值。对给定 R的估值序列为=(10111)。这种算法所保留的路径与接收序列之间的似然概率为最大，所以又称为最大似然译码。这种译码的译码约束长度常为编码约束长度的数倍，因而可以纠正不多于(df/2)个错误。 。它在卫星和维特比译码器的复杂性随m呈指数增大。实用中m不大于10深空通信中有广泛的应用。在解决码间串扰和数据压缩中也可应用。 (3)序贯译码 序贯译码是根据接收序列和编码规则，在整个码树中搜索(既可以前进，也可以后退)出一条与接收序列距离(或其他量度)最小的一种算法。由于它的译码器的复杂性随m值增大而线性增长,在实用中可以选用较大的m值(如20,40)以保证更高的可靠性。许多深空和海事通信系统都采用序贯译码。 2.7 viterbi译码原理及算法 2.7.1 Viterbi 译码原理简述 维特比译码算法基本原理是:将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送序列。 卷积码的Viterbi 译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程,找到最佳路径即完成了译码过程,并可以纠正接收码字中的错误比特。所谓“最佳”, 是指最大后验条件概率:P( C/ R) = max [ P ( Cj/ R) ] , 一般来说, 信道模型并不使用后验条件概率,因此利用Beyes 公式、根据信道特性出结论:max[ P ( Cj/ R) ]与max[ P ( R/ Cj) ]等价。考虑到在系统实现中往往采用对数形式的运算,以求降低运算量,并且为求运算值为整数加入了修正因子a1 、a2 。 令M ( R/ Cj) = log[ P ( R/ Cj) ] =Σa1 (log[ P( Rm/ Cmj ) ] + a2) 。 其中, M 是组成序列的码字的个数。因此寻找最佳路径, 就变成寻找最大M( R/ Cj) , M( R/ Cj) 称为Cj 的分支路径量度,含义为发送Cj 而接收码元为R 的似然度。 11 2.7.2 Viterbi 译码算法描述 卷积码的viterbi译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程，找到最佳路径即完成了译码过程，并可以纠正接收码字中的错误比特。Viterbi 译码算法步骤如下描述: ?根据接收码符号R ,计算出相应的分支量度值BM( R/ Cj) , j = 1 、2 ; ?进入某一状态的2 条分支量度BM ( R/ Cj)与其前状态路径量度PM累加求和; ?比较到达当前状态的2 条新的路径量度PM的大小，选择最大者作为新的状态路径量度存储起来，并保存与此路径对应的码字; 个状态都实施上述加、比、选(ACS) 运算; ?对所有的256 ?在每一译码时刻，满足延时就从256 条留存路径中，选择路径量度最大的一条路径作为译码数据输出; ?进入下一译码时刻，重复以上步骤，直至译码结束。 2.8维特比译码算法性能 对于(n，k，m)卷积码，其编码存储度(移位寄存器单元的数量)为m，幸存路径有2m条。每条幸存路径(或信息序列)存储器单元数是n*D，其中，n是卷积码码组宽度，D是需要存储的码组的个数。D的取值一般考虑取m的整倍数，称D为幸存路径长度。编码存储度和幸存路径长度的取值问题关系到芯片规格、传输时延等问题。若D很大，则译码器的存储量太大而难以实用。一般情况下，当译码进行到第5级(每级包括m个时刻)以后，每个状态幸存路径的前几个分支已基本重合在一起，这就是说每个路径存储器不必存储D个很大的码序列。译码时，当译码器接收并处理完第D个码组后，译码器中的幸存路径存储器已全部存满，当译码器开始处理第D+1个码组时，他就对幸存路径存储器中的最顶端的码组做出判决并输出。 (1)适当增加幸存路径的长度可以提高译码器的纠错能力。 (2)幸存路径的长度在增加到一定值时，译码器纠错能力趋于稳定。当N值增加到6以上，误比特率降低幅度大为减小，曲线有合二为一的趋势。因此，可以认为幸存路径长度D取编码存储度的6倍以上就可以取得比较好的译码性能。 (3)选择合适的延时。路经量度(似然度)的累加选取和码字延时判决输出提高了译码的准确性，D 越大越有利于判决的正确性，但是这又和通信的实时性背道而驰，一般D 为卷积码约束长度N的5~10 倍即可，本文算法D 取50。 (4)留存路径的更新的描述。每个状态的留存路径选择实际上是从当前时刻往前推的，例如，在时刻t，又假设到达状态s2 的路径有两个，分别为s4 和s5，对应的输出码字分别是00 和11，我们分别计算出两条路经的分支量度BM，并累加它们对应的前状态路径量度PM_l，发现累加后s5- s2的PM值比s4- s2 的大，所以保留s5 所对应的留存路径，并更新状态s2 所对应的留存路径存储器。对每一状态都做如此比较，保存大的分支量度BM，然后再累加前一状态路径量度PM_l，最后完成所有状态的选择，比较当前所有状态的路经量度PM,选择最大路径，如果延时超过D 就判决输出码字。显然此处判决的码字要延时D 时刻才能移位输出。 12 b3 3卷积码编码与维特比译码的设计 3.1卷积码编码设计 3.1.1卷积码编码器原理 卷积码编码器一般主要由移位寄存器和加法器组成。输入移位寄存器包括N段，每段有k个，共Nk个寄存器，负责存储每段的k个信息码元;各信息码元通过n个模2加法器相加，产生每个输出码组的n个码元，并寄存在一个n级的移位寄存器中移位输出。整个编码过程可以看成是输入信息序列与由移位寄存器和模2加法器之间连接所决定的另一个序列的卷积，卷积码即由此得名。通常把N称为卷积码的约束长度，通常把卷积码记为:(n，k，N);其中，n为码长，k为码组中信息码元的个数，它的编码效率为R=k/n。 b2 b3 b1 M1 M2 1 输入 c1 c2 输出 图4(2，1，3)编码器原理框图 它的编码方法是:输入序列依次送入一个两级移位寄存器，编码器每输入 cccc1212一位信息b，输出端的开关就在，之间来回切换一次，输出和。在图4 mcbmcbb1212123中，与 为移位寄存器，它们的起始状态均为零。、与、、之间 cbbb,，，cbb,，1123213的关系如下: ; 。 3.1.2卷积码编码过程 表1 信息D进行卷积编码时的状态 输入信息1 1 0 1 0 0 0 0 D 00 01 11 10 01 10 00 00 bb32 11 01 01 00 10 11 00 00 输出c c12 13 对于图4所示的(2，1，3)卷积码编码电路，其树状图如图5所示。这里， mm12分别用a，b，c和d表示寄存器和的四种可能状态:00，10，01，11，作 为树状图中每条支路的节点。 b1以全零状态a为起点，当第一位信息=0时，输出码元为00，寄存器保持 b1状态a不变，对应图中从起点出发的上支路;当=1时，输出码元为11，寄存 00器则转移到状态b，对应图中的下支路;然后再分别以这两条支路的终节点a和a=00 00ab作为处理下一位输入信息b的起点，从而得到4条支路。以此类推，可以得到b=10i状2整个树状图。显然，对于第i个输入信息比特，图中将会出现条支路。但从第c=0111b态4位信息开始，树状图的上半部和下半部都完全相同，这意味着此时的输出码元00d=11一盒第1位信息无关，由此可以看出吧卷积码的约束长度定义为N的意义。 a10 c11 01 d00 a11 a 00 b11 0b01 c 10起点d信 a00息 11a 11 10b c10 100c 01 d b11 01a 00 图5(2，1，3)卷积码的树状图 01b主要程序: d01{ 10c int j; 10 unsigned int input,a1=0,a2=0; d for(j=0;j>1)&1)^(state2&1)^(state1&1); sym2=((state2>>1)&1)^(state1&1); sym=(sym1<<1) | sym2; if ( ((state1&2)>>1)==(state2&1)) c=((m&1)^(sym&1))+(((m>> 1)&1)^((sym >> 1)&1)); else c=10000; return(c); } 3.2 viterbi译码设计 3.2.1维特比译码器原理 viterbi译码的前提是建立合适的网格图，以便寻找最优路径。或者可以认为，维特比译码的关键是寻找最优路径。在实际的译码操作过程中，怎样建立网格以及建立网格后的路径的选择是译码的关键问题。 注意:由于D1D2D3表示的顺序不同，所产生的网格图和状态转移图也不同，并且译码过程是根据网格图实现，所以本文所以涉及的维特比译码方法具有一定的特殊性，但是整体过程还是具有研究价值。 b 0111 a00 d100010 1101 c 图6 (2,1，3)码状态转移图 15 维特比译码可分为网格图建立，寻找最优路径，译码这三部分。 译码程序流程如图7所示: 开始 建立网格图 判断最优路径 译码输出 图7译码流程图 3.2.2维特比译码过程 ?网格图建立 图8(2,1,3)码网格图 根据图8所示的(2,1,3)码的网格图，可以发现D1D2D3决定了从000—111的8个状态。并且进一步观察网格图可以发现从状态000-011是由输入的信息位0产生，从状态100-111是由输入的信息位1产生。此外，以001状态为例，可 16 以看出状态001是由状态010和状态011产生。由上面可知，假设当前状态为i,那么在前一时刻中，产生状态i的两个状态是2*i和2*i+1。根据i是否小于4，来判断状态i是由信息位0还是信息位1生成。进一步可以推知指向状态i的前一时刻的两个状态生成的码组，这样便于以判断汉明距离。 ?寻找最优路径 网格图建立之后，根据接收码组和网格图中生成的码组比较，判断最优路径。 ，首先判断前一时刻所有状态中，是哪两个状态指向当前假设某一时刻的状态i 状态i;其次，根据这两个指向当前状态i的状态生成的码组和前一时刻接收的码组比较，保留汉明距离最小的那条路径以及到达状态i时的最小汉明距离。下一时刻，同样操作，但是保留的最小汉明距离是前面最小汉明距离累加。 在所有的接收码组处理完之后，会得到一组汉明距离以及所对应的最优路径。比较选择出最小的汉明距离，那么该最小汉明距离所对应的路径即为最优路径。 ?译码 如图9所示，其中红线表示计算得到的最优路径。观察其变化规律，可以发现，假设i时刻的状态和第(i+1)时刻比较得知，若第(i+1)时刻小于第i时刻，那么对应代表实际信息中0;若大于，则为1。然后逐次比较译出信息值。 图9 状态图找出最优路径 主要程序: void viterbi(int initialstate, /*定义解码器初始状态*/ int *viterbiinput, /*解码器输入码字序列*/ int *viterbioutput /*解码器输出码字序列*/ ) { struct sta /*定义网格图中每一点为一个结构体,其元素包括*/ {int met; /*转移到此状态累计的度量值*/ int value; /*输入符号 */ struct sta *last; /*及指向前一个状态的指针*/ 17 }; struct sta state[4][N]; struct sta *g,*head; int i,j,p,q,t,r,u,l; for(i=0;i<4;i++) /* 初始化每个状态的度量值*/ for(j=0;j #include "Conio.h" #define N 7 #include "math.h" #include #include #define randomize() srand((unsigned)time(NULL)) encode( unsigned int *symbols, /*编码输出*/ unsigned int *data, /*编码输入*/ unsigned int nbytes, /*nbytes=n/16,n为实际输入码字的数目*/ unsigned int startstate /*定义初始化状态*/ ) { int j; unsigned int input,a1=0,a2=0; for(j=0;j>1)&1)^(state2&1)^(state1&1); sym2=((state2>>1)&1)^(state1&1); sym=(sym1<<1) | sym2; if ( ((state1&2)>>1)==(state2&1)) c=((m&1)^(sym&1))+(((m>> 1)&1)^((sym >> 1)&1)); else c=10000; return(c); } int traninput(int a,int b) /*状态从a到b时输入卷积码的符号*/ {int c; c=((b&2)>>1); return(c); } int tranoutput(int a,int b) /*状态从a到b时卷积码输出的符号*/ {int c,s1,s2; s1=(a&1)^((a&2)>>1)^((b&2)>>1); s2=(a&1)^((b&2)>>1); c=(s1<<1)|s2; return(c); } void viterbi(int initialstate, /*定义解码器初始状态*/ int *viterbiinput, /*解码器输入码字序列*/ int *viterbioutput /*解码器输出码字序列*/ ) {struct sta /*定义网格图中每一点为一个结构体,其元素包括*/ {int met; /*转移到此状态累计的度量值*/ int value; /*输入符号 */ struct sta *last; /*及指向前一个状态的指针*/ }; struct sta state[4][N]; struct sta *g,*head; int i,j,p,q,t,r,u,l; for(i=0;i<4;i++) /* 初始化每个状态的度量值*/ for(j=0;j0;u--) /*向前递归的找出最大似然路径 */ {*(viterbioutput+(u-1))=g->value; g=g->last; } /* for(u=0;u<8;u++) *(viterbioutput+u)=state[u][2].met; */ /*此行程序可用于检测第n列的 度量值*/ } void decode(unsigned int *input, int *output,int n) { int viterbiinput[100]; int j; for(j=0;j