基于MATLAB的卷积码的分析与应用毕业设计

1、毕业设计东北大学本科毕业设计（论文）摘要毕业设计（论文）任务书毕业设计（论文）题目：基于MATLAB的卷积码的分析与应用设计（论文）的基本内容：（1）介绍纠错控制编码的相关理论，重点分析卷积码的相关编码和解码理 论。（2）在MATLAB中编写卷积码的编码和解码程序，模拟通信系统，针对 TD-SCDMA系统中的卷积码进行仿真。（3）进行纠错译码验证，纠错比较及误码率相关因素分析。毕业设计（论文）专题部分：题目设计或论文专题的基本内容：学生接受毕业设计（论文）题目日期第2周指导教师签字：2010年3月8日基于MATLAB的卷积码的分析与应用摘要随着现代通信的发展，特别是在未来 4G通信网络中，高速

2、信息传输和高可 靠性传输成为信息传输的两个主要方面， 而可靠性尤其重要。因为信道状况的恶 劣，信号不可避免会受到干扰而出错。为实现可靠性通信，主要有两种途径：一 种是增加发送信号的功率，提高接收端的信号噪声比；另一种是采用编码的方法 对信道差错进行控制。前者常常受条件限制， 不是所有情况都能采用。因此差错 控制编码得到了广泛应用。介绍了多种信道编码方式，着重介绍了卷积码的编码方法和解码方式。介绍了 MATLAB的使用方法、编程方法、语句、变量、函数、矩阵等。介绍了 TD-SCDMA通信系统和该系统下的卷积码，搭建了系统通信模型。编写卷积码 的编码和解码程序。用 MATLAB仿真软件对TD-SC

3、DMA系统的卷积码编解码 进行仿真。对其纠正错码性能进行验证， 并且对误码率进行仿真和分析。 卷积码 的编码解码方式有很多，重点仿真 Viterbi算法。Viterbi算法就是利用卷积码编 码器的格图来计算路径度量，选择从起始时刻到终止时刻的惟一幸存路径作为最 大似然路径。沿着最大似然路径回溯到开始时刻， 所走过的路径对应的编码输出 就是最大似然译码输出序列。它是一种最大似然译码方法，当编码约束长度不大、 或者误码率要求不是很高的情况下，Viterbi译码器设备比较简单，计算速度快， 因而Viterbi译码器被广泛应用于各种领域。关键词：卷积码；信道编码；TD-SCDMA ； MATLAB-I

4、II-东北大学本科毕业设计(论文)目录目录毕业设计（论文）任务书 I摘要IIAbstract错误！未定义书签。第1章绪论1.1.1课题研究的背景和来源 1.1.2主要内容2.第2章相关理论介绍3.2.1信道编码3.2.1.1信道编码的分类 3.2.1.2编码效率3.2.2线性分组码3.2.3循环码5.2.4卷积码6.2.4.1卷积码简介7.2.4.2卷积码的编码7.2.4.3卷积码的解码13第3章 MATLAB 应用213.1数和算术的表示方法 213.2向量与矩阵运算 213.2.1通过语句和函数产生 213.2.2矩阵操作223.3矩阵的基本运算 223.3.1矩阵乘法223.3.2矩阵除

5、法233.4MATLAB 编程233.4.1关系运算233.4.2控制流25第4章卷积码的设计与仿真274.1TD-SCDMA 系统274.1.1系统简介274.1.2仿真通信系统模型 274.2卷积编码设计284.3编解码程序实现294.3.1卷积码编解码设计294.3.2卷积码编解码程序设计 .324.4卷积码实现344.4.1 (2,1)卷积码的仿真研究 .344.4.2 (3,1)卷积码的仿真研究 .364.5卷积码误码率38第5章结论415.1总结415.2展望41参考文献43致谢45-V-东北大学本科毕业设计（论文）第1章绪论第1章绪论1.1课题研究的背景和来源纠错编码己有五十几年

6、历史，早在 1948年，香农（Shannon在他的开创性论 文 通信的数学理论”中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错码的基石。以后，纠错码受到了越来越多 的通信和数学工作者，特别是数学家的重视，使纠错码无论在理论上还是在实际 中都得到了飞速发展。随着现代通信的发展，特别是在未来 4G通信网络中，高速信息传输和高可 靠性传输成为信息传输的两个主要方面， 而可靠性尤其重要。因为信道状况的恶 劣，信号不可避免会受到干扰而出错。为实现可靠性通信，主要有两种途径：一 种是增加发送信号的功率，提高接收端的信号噪声比；另一种是采用编码的方法 对信道差错进行控

7、制。前者常常受条件限制，不是所有情况都能采用。例如卫星通信系统以很远的距离传送数据，由于衰落、噪声和干扰等的影响，信号在传输 过程中将产生严重的畸变。如果要求信号具有尽可能大的能量， 卫星体积和载重 就会大大增加，使成本相对于原来大大增加，所以不可能给信号提供太大的能量， 而建立在香农基础上的编码理论正可以解决这个问题，使得成本降低，实用性增强。前向纠错技术（FEC）特别是卷积编码是当今无线数字通信系统的一个十分重 要的组成部分。它是一种有效的信道编码方法，在实际中广泛应用。目前无线数字通信系统都采用某一形式的卷积编码如在W-CDMA、DVB-S、DVB-T、IEE802.11系统中都使用了卷

8、积编码。由于其出色的纠错性能，一般在级联码中 作为内码使用，从而保证外码有效地工作，大大提高了整个系统的纠错能力。而 Viterbi译码器正是针对卷积码的一种最佳译码方法。CDMA系统以其容量大、抗干扰能力强的特点成为第三代移动通信系统的 标准。CDMA系统的信道编码大多米用卷积编码，这是因为卷积码的纠错能力 强，不仅能纠随机差错，还可以纠突发差错。在CDMA系统中，对卷积码的译码采用Viterbi算法，它是一种最大似然译码方法，当编码约束长度不大、或者 误码率要求不是很高的情况下，Viterbi译码器设备比较简单，计算速度快，因而 Viterbi译码器被广泛应用于各种领域。现代通信中，随着信

9、号序列的传输速率的不断提高， 要求卷积码译码的速度 也要不断提高，Viterbi译码由于充分利用信号序列统计概率的特性而具有最佳性 能。信道编码的应用领域主要包括深空通信、卫星通信、数据传输、移动通信、东北大学本科毕业设计（论文）第1章绪论文件传输和数字音频/视频传输等。卷积编码作为信道编码方式中最重要一种， 被广泛使用于卫星通信、无人机测控、深空通信、移动通信、水声通信等数字通 信系统，甚至被采纳到某些无线通信的标准之中， 如GSM、IS.95和CDMA2000 的标准。在卫星通信中，码率为 1/2和1/3的卷积码己经成为商业卫星通信系统 中的标准编码方法。在无人机测控中，与传统的信道改善控

10、制指令传输误码的方 式比较，利用卷积码对无人机遥控信道进行编码，在一定信道条件下，其控制指令传输误码有明显下降。在码速率不增加的条件下，无人机系统控制指令传输可 靠性得到明显改善3。随着数字通信系统业务的不断拓展，随着卷积编码理论的不断发展和完善， 卷积码的应用必将越来越广泛，卷积码在现在通信系统中的作用必将越来越大。1.2主要内容论文框架：第一章介绍了卷积码的研究背景， 第二章介绍了卷积码的相关理 论，信道编码、线性分组码、循环码及卷积码的表示方式、编码方式、解码方式， 第三章介绍了实现卷积码仿真所需要的软件方式，第四章进行卷积码设计与仿 真，介绍了 TD-SCDMA系统下的卷积码，对卷积码

11、性能进行了研究。主要内容：介绍了信道编码方式。着重研究列举了卷积码的编码方法和解码 方式，介绍了 MATLAB的使用方法和TD-SCDMA系统。编写卷积码的编码和 解码程序。并且用 MATLAB仿真软件对TD-SCDMA系统的卷积码编解码进行 仿真，Viterbi算法就是利用卷积码编码器的格图来计算路径度量，选择从起始时刻到终止时刻的惟一幸存路径作为最大似然路径。沿着最大似然路径回溯到开始 时刻，所走过的路径对应的编码输出就是最大似然译码输出序列。它是一种最大似然译码方法，当编码约束长度不大、或者误码率要求不是很高的情况下，Viterbi 译码器设备比较简单，计算速度快，因而 Viterbi译

12、码器被广泛应用于各种领域。-#东北大学本科毕业设计(论文)第2章相关理论介绍第2章相关理论介绍2.1信道编码在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编 码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。信道编码现在已经得到广泛的应用。2.1.1信道编码的分类信道编码有多种分类方式，主要有按照关系、范围及用途三种。(1) 根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性 码。如果函数关系是线性的，即满足一组线性方程式，贝U称为线性码，否则为非 线性码。(2) 根据上述关系涉及的范围，

13、可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。(3) 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定 能纠错；而纠错码以纠错为目的，一定能检错4,5。2.1.2编码效率用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。定 义编码效率尺来衡量有效性：R=k/n,其中，k是信息元的个数，n为码长。对纠 错码的基本要求是：检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简 单。2.2线性分组码线性分组码中的线性是指码组中码元间的约束关系是线性的， 而分组则是对 编码方法而言，即编码时将

14、每k个信息位分为一组进行独立处理， 变换成长度为 n(nk)的二进制码组。线性分组码的编码过程可以简单描述成一个矢量和一个矩阵相乘的结果，即C=mG,其中C是经过编码后得到的n维编码输出co,d, ,6-1，m是信息序列分 组mo,m1, ,mk-1，G是由k个n维矢量go,g1, ,gk-1构成的矩阵。线性分组码编码问题的核心就是如何在n维线性空间Vn中找出满足一定要求的、由2k个矢量组成的k维线性子空间，也就是说，在满足给定码字最小距 离或编码速率的前提下，如何根据已知的k个信息比特求得r=n-k个校验比特通过对码字生成矩阵 G的初等变换，可以得到惟一的行简化梯形矩阵，再经过列交换可以得到

15、如下形式的生成矩阵。g0g。,。g,ig 0,n- g” 1P,0p,1 p0,n _kJ_:10 0pt,0P1,1 :P.上丄:01 0a*Pk丄0Pk丄1Pk丄n上丄:00 10丄卫乜,0g.ig k 1 ,1gi,ig k 1, n 1G 二g1,oI * k*(n _k)k k(2.1)其中P是k(n-k)的矩阵。 这种形式的生成矩阵G称为标准生成矩阵,c 二mG 二m Ip I - :po, p1,，p其中前n-k-1个比特为校验比特，其值为按照标准矩阵生成的码字为,mo,m15k J(2.2)pmpo,i1乩mk丄p， omsk1(2.3)后面k个比特就是信息比特。这种在生成码字

16、中包含信息序列的编码码字称为线性系统分组码，简称为系统码系统码的编码结构相当简单，以系统(7，4)为例，其生成矩阵为:-9(2.4)系统码的编码结构非常简单，比如对系统(7，4)码，根据上面的生成矩阵G,只要在输入编码器的每组k个数字的后面,附加上(n-k)个监督码元就可得到所-10110001110100G =11000100110001编出的n个码字系统(7，4)码对应的监督矩阵为10 0 1110(2.5)H = 0 1 0 0 1 1 10 0 1110 1假如发送的码字为c=(1001011),而接收到的码字为丫=(1001001),信道传输 中产生的错误为e=(0000010)。由

17、 S=y Ht可求出 S=(1,1,1)o2.3循环码循环码是线性分组码中最重要的一类， 循环码是指码集合中的任一码字经过 循环移位后得到的码字仍然是码集合中的码字。 循环码的码字可以用矢量的形式 表示，即：c =(8 0Q 丄)(2.6)也可用码多项式表示，即：n 1c(x) =Co Cix Cn丄X 一(27)循环码C向右移一位的码字可由下式得出2n2n_1_nfCxc(x) =CoXCiX Cn丄XCndCoXCiX CnzXFod(x-1)(28)(2.9)(2.10)(2.11)(2.12)循环码可由它的生成多项式g(x)二g。gx gnXxn唯一确定。信息序列也可以表示成多项式k

18、1m(x)mix mk丄x _那么生成码字可表示成C(x) =m(x)g(x) mod/-1)由于多项式乘法等价于多项式系数的卷积，故n _kCi - mj g jj Z0循环码编码则可以通过移位寄存器组成的乘法电路结构实现。由数论知识可知，(n，k)循环码的生成多项式g(x)一定是xn-1的n-k次因式：xn -1 二g(x)h(x) =(g+g1x e+gnr(ho+h1x + +hkxk)(2.13)反之，若g(x)为n-k次多项式，且xn-1能被g(x)整除，则g(x)一定能生成一个(n，k)循环码。以g(x)为生成多项式所构成的(n, k)循环码中(2.14)(2.15)k-1g(x

19、),xg(x), ,x g(x)等七个多项式必定是线性无关，则循环码的生成矩阵g g1gn上 000 g g1gn上 00 0g。ggn循环码的编码也可以通过移位寄存器组成的除法电路结构实现。以(7, 4)循环码为例，选(7，4)码生成矩阵3g(x)= g3(x)=1+x+x(2.16)它除尽1+x7，若输入信息码元为m(x)=1+x3则由n_k7 _433 623(2.17)(2.18)x -m(x) =x -(1 X)二 X X 二X x ,mod(1 X X)因此，码多项式为n27_4323 6c(x) =r(x) x - m(x)二x X X _ (1 X x x x x对应的码字为C

20、=(0 1 1 1 0 0 1)其中最右边的4位是信息元，详细的编码过程如 下：(1) 三级移位寄存器初始状态为000,此时门打开，信息组以n 上7 _433 6x _m(x)=X _(1+x)=X +x(2.19)即1001次序分两路进入编码器：一路直接输出；另一路送入g(x)除法电路。 经4次移位后，信息组1001全部输出，它就是系统码的4个信息元；另 一路则将全部信息元送入g(x )除法电路，并完成除法运算，这时移位寄存器中的 状态就是余式r(x)系数，即为码的监督元(c0 c1 c2)。(3) 输出开关倒向上面2,经3次移位，移位器由监督元(C0 C1 C2)，跟在信息 元(C3C4

21、c5 c6)后面依次输出为 C=( c0 c1 c2 c3 c4 c5 c6) =(0111001)。(4) 送入第二组信息元，重复上述过程。该码最小距离为3,它能纠正7个码元一组中任何单个错误，这7种错误图 样和全零矢量一起组成译码表的陪集首，它组成了所有可能纠正的图样。现假设 接收的多项式为y(x)=y0曲曲曲(2.20)即 Y=(1 1 1 1 0 0 1)。译码器工作步骤如下：(1) 将移位寄存器清零。(2) 输入丫分两路进入译码器：一路进入缓存器；另一路经门1进入伴随式计算电路与寄存器，并分别计算 Sc、S1、S2值。(3) 在输出丫的同时，S0、S1、S2依次循环移位。无错误时，错

22、误检测电路 无输出，最后输出的码字 C的码元与丫相对应码元一致，有错误时，S0= S2=1, S1=0，错误检测电路输出为“ 1,它正好与丫中错误位在输出端的模2加中相遇， 并予以纠正后再输出。2.4卷积码相对于分组码而言，分组码的编码和译码都是各分组独立的进行， 彼此不相 关联。而卷积码的每一组不仅与本组的 k位信息位有关，还和这以前各组的信息 位有关。卷积码的结构比较复杂，但 n和k的值相对于分组码来说比较小。译码东北大学本科毕业设计(论文)第2章相关理论介绍也相对比较容易些2.4.1卷积码简介非分组码的卷积码的编码器是在任一段规定时间内产生n个码元，但它不仅取决于这段时间中的k个信息位，

23、还取决于前（K-1）段规定时间内的信息位，这K 段时间内的码元数目为 K k,称参数K为卷积码的约束长度，每k个比特输入， 得到n比特输出，编码效率为k/n，约束长度为K。在k=1的条件下，移位寄存 器级数m=K-1。卷积码一般可用（n, k，K）来表示，其中k为输入码元数，n为输出码元数， 而K则为编码器的约束长度。典型的卷积码一般选 n和k （ k n ）值较小，但约 束长度K可取较大值（K10），以获得既简单又高性能的信道编码 。卷积码是1955年Elias最早提出，1957年Wozencraft提出了序列译码。1963 年Massey提出了一种性能稍差，但比较实用的门限译码方法。196

24、7年维特比（Viterbi）提出了最大似然译码。它对存储器级数较小的卷积码的译码很容易实现， 称为维特比算法或维特比译码。2.4.2卷积码的编码卷积码的编码器是由一个有k个输入位（端）、n个输出位（端），且具有m级 移位寄存器所构成的有限状态的有记忆系统，通常称它为时序网络。2.4.2.1卷积码的解析表示法一个二元（2,1,4）卷积码的编码器，它是由k=1，即一个输入位（端），n=2，即 两个输出位（端），K=4,m=3即三级移位寄存器所组成的有限状态的有记忆系统。（1）离散卷积若输入信息序列为（这里的卷积码是U0首先输入）(2.21)(2.22)(2.23)u =（UoU1U2 ）则对应输出

25、为两个码字序列 c =（Co C1 C2 ）_ c （Co C1 C2 ）其相应编码方程可写为 *C -u g *c _u g C =（C ,C ）其中像”表示卷积运算，gg表示编码器的两个脉冲冲击响应，即编码可由输入信息序列U和编码器的两个冲击响应的卷积得到，故称为卷积码 。这里的脉 冲冲击响应是指，当输入信息为 u=(100)时，所观察到的两个输出序列值。由 于编码器有m=3级寄存器，故冲激响应至多可持续到 K=m+仁3+1=4位，且可写成:g (1011)g =(1111)(2.24)在一般情况下有:(2.25) c(C。C0 C1 C1 )(2.26)若输入信息序列为： g =(go

26、g gm) g =(go g gm)经编码器后，两个输出序列合并为一个输出码字序列为:u =(10111)(2.27)则有:c (10111)*(1011) =(10000001)C二(10111)*(1111) =(11011101)(2.28)(2.29)最后输出的码字为:C (1101000101010011)(2.30)(2)生成矩阵上述冲激响应gg又称为生成序列，若将该生成序列gg按如下方法排列，构成如下生成矩阵(当K=4,m=3时):- g。g。 g1g1g2g2g3g3ggg1g1g2g2g3g3G =ggg1g1g2g2 g3 g3(2.31)上述矩阵中，其中空白部分均为 0。

27、则上述编码方程可改为矩阵形式c =u -G(2.32)G为卷积码的生成矩阵，若输入信息序列为一无限序列时，即 u=(10111)生成矩阵则为一个半无限矩阵，即有起点无终点，因此称它为半无限。若: (2.33)U -(10111), g (1011), g (1111)-13则:c =u G 10111)=11 01 00 01 011111011111110111111101111101001110101111111 11(2.34)(3)码多项式 若将生成序列表达成多项式形式，有g 二g 1111= 1+输入信息序列也可表达为多项式形式23011 + x + x2x + x +(2.35)2

28、34u = 10111+ x + x + x则卷积码可以用下列码多项式形式表达23423c i X X X 1 X X23424563567T X X X X X X X X X X X(2.36)(2.37)234567t 2x 2x 2x 2x 2x x=1 - x (10000001 )234c =1 X X X234=1 X X X1 xx2x33452456xxxxxxxx3丄 4丄 5丄 7=1 x x x x x(2.38)=1 x7=110111012.4.2.2卷积码的图形表示法卷积码的图形表示法有很多种，在此介绍最常用的三种，状态图表示法、树 图表示法、网格图表示法。(1)

29、状态图表示法卷积编码器在下一时刻的输出取决于编码器当前的状态及下一时刻的输入。 当前状态取决于编码器在当时各移位寄存器所存储的内容，称编码器的各移位寄存器在任一时刻的存数(0或1)为编码器在该时刻的一个状态。编码器的总可能 状态数是2mk个。对于n=2，k=1, K=3, m=2的(2，1, 3)卷积编码器，则其总的 可能状态数是4个。设以S表示某状态，i =0，1，2，3,在某tj时刻，此(2,1,3)东北大学本科毕业设计(论文)第2章相关理论介绍卷积编码器的输出表述为Cj =Uj U-1 Uj-2(2.39)Cj 二Uj 二 Uj-2它取决于Uj,uj-1及Uj-2三个值，其中Uj是当前的

30、输入值，Uj-1及Uj-2是以前输 入的两个值。若要求出下一个tj+1时刻的输出值，贝U要知道当前的 Uj及Uj-1值。 当输入下一时刻的Uj+1值时，就可以求出下一个tj+1时刻的Cj+1及c+1值。所以， 为决定下一个tj+1时刻编码器的输出，此(2, 1, 3)卷积编码器在当前tj时刻的状 态用S=(Uj,Uj-1)(i=0,1,2,3)表示即可。如表2.1所示。表2.1 状态转移表UjUj-1Si00So=a10So=b01S0=c11S0=d设输入信息序列为：U =U0U1U2 Ui i；=1011100 (2.40)1) 首先，对移位寄存器清洗、复0,移存器状态为00;2) 输入:

31、U0=1，输出c=1二0二0 =1， c=1二0 =1，故c11，移位寄存器状态改为10;3) 输入:U1=0，贝肪根据(010)，可算出：c =1,c=0，故e=(10)，移位寄存器 状态改为01;4) 输入:U2=1，贝肪根据(101)，可算出：c；，c；，故C2 =(00)，移位寄存 器状态改为10;5) 输入:U3=1，贝肪根据(110)，可算出：& =0(； =1，故0=(01)，移位寄存器 状态改为11;6) 输入:U4=1，贝U根据(111)，可算出：1 =1, C： =0，故C4=(10)，移位寄存器 状态改为11;7) 输入:U5=0，贝肪根据(011)，可算出：& =0,c

32、二1，故Q=(01)，移位寄存器 状态改为01;8) 输入:U6=0，贝肪根据(001)，可算出：c： =1(刊，故C广(11)，移位寄存器 状态改为00;9)输入:U7=0，则根据(000),可算出： = 0，C； = 0，故C7 =(00)，移位寄存 器状态改为00;按照上述步骤，可画出状态图如图2.1所示。图2.1中，4个圆圈中的数字表示状态，状态之间的连线与箭头表示转移方 向，称作分支，分支上的数字表示由一个状态到另一个状态转移时的输出码字， 而括号中数字表示相应的输入信息数字。例如若当前状态为11，即Ss=11，则当下一时刻的输入信息位为 U1=0时，输出码字C1=01，下一刻的状态

33、为S2=01 o若 输入信息位U1=1，则输出码字为C1=10，下一时刻的状态仍为S3=11 o树图表示法如果要展示出编码器的输入、输出所有可能情况，则可采用树图来描述，它是将上述编码器的状态图按时间展开而成的，如图2.2所示。由图2.2可见，若设初始状态S0=00作为树根，对每个时刻可能的输入进行 分支，若分支的节点级数用l表示，则当1=0时，有两个可能分支。若U0=0，则 向上，即0分支向上，若U0=1则向下，即1分支向下，它们都达到下一个一级 节点(1 =1 )o当丨=1时，对每个一级节点根据U1的取值也将产生上、下两个分支， 并推进到相应的二级节点(I =2)。依此类推，就可以得到一个

34、无限延伸的树状结 构图。图2.2中各分支上的数字表示相应输出的码字。 字段a、b、c、d表示编码 器所处的状态。对于特定输入信息序列：u=(10111000)(2.41)相应的输出：c=(11 10 00 01 10 01 11 00)(2.42)(3)网格图表示法网格图的纵坐标表示所有状态，横坐标表示时间。这类网格图描述法在卷积 码的概率译码中，特别在维特比译码中特别有用，它综合了状态图与树图的优点， 即网格图既具有状态图结构简单，又具有树图的时序关系清晰特点。以(2,1,3)卷积码为例，当节点级数大于I = m 1 =2 1 =3时，状态 a、b、c、d呈现重复。利用这种重复，即如果将图

35、2.2中1=3以后，码树上处 于同一状态的同一节点折叠起来加以合并，就可以得到纵深宽度(或称高度)为2km=22=4的网格图，如图2.3所示。图2.3中实线表示输入为0时所走的分支，虚线表示输入为1时所走的分支。 由图2.3可见这个图实质上是将图2.2的树图重复部分合并而成的。它自1=2即 第二级节点开始，从同一状态出发所延伸的树结构完全一样。 因此网格图能更为 简洁地表示卷积码。如果任意给定一个输入信息序列，则它在网格图中就必将存在一条特定的路 径，比如u=(1011100)，其输出编码为c=(11 10 00 01 10 01 11)即为上述网格图 2.3中粗黑线所表示的路径。网格图是研究

36、卷积码最大似然译码维特比算法的重 要工具。-1-17东北大学本科毕业设计（论文）第2章相关理论介绍243卷积码的解码卷积码的解码方式可以分为两类：代数解码和概率解码。代数解码是利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑解码，又称门限解码，是卷积码代数解码的最主要一种方法，也可以应用于循环码的解码。 大数逻辑解码对于约束长度较短的卷积码最为有效，而且设备较简单。概率解码（又称最大似然解码）则是基于信道的统计特性和卷积码的特点进行计算。首先由沃 曾克拉夫特针对无记忆信道提出的序贯解码就是概率解码方法之一；另一种概率解码方法是维特比（Viterbi）算法。当码的约束长度较短时，它

37、比序贯解码算法的 效率更高、速度更快，目前得到广泛的应用9,10。2.4.3.1大数逻辑解码卷积码的大数逻辑解码是基于卷积码的代数表述运算的，其一般工作原理如图2.4所示。首先将接受信息位暂存于移存器中，并从接收码元的信息位和监督位计算校 正子。然后，将计算得出的校正子暂存，并用它来检测错码的位置。在信息位移 存器输出端，接有一个模2加电路；当检测到输出的信息位有错时，在输出的信息为上加“ 1,从而纠正之11。在图2.5中画出了一个（2,1,6）卷积码编码器。-1-#东北大学本科毕业设计（论文）第2章相关理论介绍图2.4大数逻辑解码一般工作原理图2.5中编码器的监督位和信息位的关系如下，当输入

38、序列为bib2b3b4时,监督位为:CiC2F2C3 =b3匕+b4C5 b2 bC6 * b2 b b其监督关系式如下:s P +bS2p+b2p+bs54 P +bi55 =C5 +b +& +b5(2.43)(2.44)56 =C6 bi b2 b3 b6S（i=16）称为校正子，经过简单线性变换，可以得出如下正交校验方程组：& =Ci +bS49 b b4（245）S5 =C5 +bl +b2 +b52 +S6 =C2 +C6 +bl +b3 +b6只有信息位bi出现在每个方程中，监督位和其他信息位均最多只出现一次。 因此，在接收端解码时，考察 bi ci至b6 C6等12个码元，仅当

39、bi出错时，才可 能有3个或3个以上方程等于“i。从而能够纠正bi的错误。按照这一原理画出 的此（2,i,6）卷积码解码器原理方框图示于图 2.6中。由图2.6可见，当信息位出现一个错码时，仅当它位于信息位移存器的第 &3、2和i级时，才使校正子等于“i。因此，这时的校正子序列为iOOiii;反之， 当监督位出现一个错码时，校正子序列将为 iOOOOOo由此可见，当校正子序列 中出现第一个“ i时，表示已经检出一个错码。后面的几位校正子则指出是信息 位错了，还是监督位错了。门限电路将这 4个电压（非模2）相加。当相加结果大 于或等于3时，门限电路输出“i,它除了送到输出端的模2加法器纠正输出码

40、 元bi的错码外，还送到校正子移存器纠正其中错误i9,2io此卷积码除了能够纠正两位在约束长度中的随机错误外，还能纠正部分多于东北大学本科毕业设计(论文)第2章相关理论介绍两位的错误。为了克服突发错误，可以米用更长的约束长度和在约束长度中能纠 正更多错误的码。243.2维特比解码算法维特比解码算法是维特比于1967年提出的。这种算法的基本原理是将接收 到的信号序列和所有可能的发送信号序列比较， 选择其中汉明距离最小的序列认 为是当前发送信号序列。若发送一个k位序列，则有2k种可能的发送序列。当K 较大时，存储量太大，使实用受到限制。维特比算法对此作了简化，使之能够实 用。一种(3,1,3)卷积

41、码编码器方框图如图2.7。该(3,1,3)卷积码的状态图如图2.8图2.8(3,1,3)卷积码状态图设发送信息位为：1101，为了使图2.7中移存器的信息位全部移出，需要在信息位后面加入三个“0”故经过编码后的发送序列为111 110 010 100 001 011000,并且假设接收序列为111 010 010 110 001 011 000其中第4和第11个码元为错码。由于这是一个(n,k,N)=(3,1,3)卷积码，发送序列的约束度N=3,所以首先-1-6需要考察nN=9东北大学本科毕业设计(论文)第2章相关理论介绍该(3,1,3)卷积码网格图如图2.900000000000000011

42、1bc11110111011/ 011001001J、/110110010010011100101111111001101110010001100 101图2.9(3,1,3)卷积码网格图1-7该(3,1,3)卷积码编码举例如图2.10。 /d图2.10(3,1,3)卷积码编码路径举例第一步考察接收序列前9位“ 111 010 010”此码的网格图2.10可见，沿路 径每一级有4种状态a,b,c,d。每种状态只有两条路径可以到达。故 4种状态有8 条到达路径。现在比较网格图中的这 8条路径和接收序列之间的汉明距离。例如，由出发点状态a经过三级路径后到达状态a的两条路径中上面一条为“000 00

43、0 0000它和接收序列“ 111 010 01(的汉明距离等于5;下面一条为“111001 011”，它和接收序列的汉明距离等于 3。同样，由出发点状态a经过三级路 径后到达状态b,c,d的路径分别都有两条，故总共有 8条路径。在表2.2中列出 了这8条路径和汉明距离。东北大学本科毕业设计（论文）第2章相关理论介绍表22维特比算法解码第一步计算结果序号路径对应序列汉明距离幸存否1aaaa000 000 0005否2abca111 001 0113是3aaab000 000 1116否4abcb111 001 1004是5aabc000 111 0017否6abdc111 110 0101是7

44、aabd000 111 1106否8abdd111 110 1014是现在将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为幸存路径。若两条路径的汉明距离相同，则可以任意保存一条。这样就 剩下4条路径了，即表中第2,4,6和8条路径。第二步将继续考察接收序列中的后继 3位“ 110现在计算4条幸存路径上 增加一级后的8条可能路径的汉明距离。计算结果列于表 2.3中。表2.3维特比算法解码第二步计算结果序号路径原幸存路径的距离新增路径段新增距离总距离幸存否1abca+a3aa25否2abdc+a1ca23是3abca+b3ab14否4abdc+b1cb12是5abcb+c4b

45、c37否6abdd+c4dc15是7abcb+d4bd04是8abdd+d4dd26否表2.3中最小的总距离等于2,其路径是abdc+b,相应序列为111 110 010 10Q它和发送序列相同，故对应发送信息位1101。按照表2.3中的幸存路径画出的网 格图示于图2.12中。图中粗线路径是汉明距离最小（等于2）的路径。I U I图2.12 对应信息位“ 1101的幸存路径网格图为了使输入的信息位全部通过编码器的移存器，使移存器回到初始状态，在信息位1101后面加了三个“0。若把这三个“（仍看作是信息位，则可以按照上 述算法继续解码。这样得到的幸存路径网格图示于图2.13中，图中的粗线仍然是汉

46、明距离最小的路径，但是，若已知这三个码元是（为结尾而补充的）“0”则在 解码计算时就预先知道在接收这三个“ 0码元后，路径必然应该回到状态 a。而由图可见，只有两条路径可以回到a状态。所以，这时图2.13可以简化成图2.14。-1-19东北大学本科毕业设计（论文）第2章相关理论介绍101 101 101图2.13 对应信息位 “ 1101000的勺幸存路径网格图 一 一一 一一一 101_ 1Q1图2.14 对应信息位“ 1101及以“000结束的幸存路径网格图-#东北大学本科毕业设计（论文）第3章卷积码实现第3章MATLAB应用3.1数和算术的表示方法Matlab中数的表示方法和一般的编程语

47、言没有区别。如：3-990.00019.639721.6021E-206.02252e23数学运算符有：+加-减*乘/右除左除八幕这里1/4和41有相同的值都等于0.25（注意比较：14=4）。只有在矩阵的除 法时左除和右除才有区别。3.2向量与矩阵运算3.2.1通过语句和函数产生（1）向量的产生除了直接列出向量元素（即所谓的 穷举法”外卜，最常用的用来产生相同增量 的向量的方法是利用“:算符（即所谓的 描述法” O）在Matlab中，它是一个很重要 的字符。如：z=1:5z =12345即产生一个15的单位增量是1的行向量，此为默认情况。用“:号也可以产生单位增量不等于 1的行向量，语法是把

48、增量放在起始量 和结尾量的中间。如：x=0:pi/4:pi即产生一个由0pi的行向量，单位增量是 pi/4=3.1416/4=0.7854x =00.78541.57082.35623.1416也可以产生单位增量为负数的行向量。如：-2-21东北大学本科毕业设计(论文)第3章卷积码实现y=6:-1:1y :=65432 1(2)矩阵的产生Matlab提供了一批产生矩阵的函数,如表3.1所示。表3.1矩阵函数函数名功能函数名功能zeros产生一个零矩阵diag产生一个对角矩阵ones生成全1矩阵tril取一个矩阵的下三角eye生成单位矩阵triu取一个矩阵的上三角magic生成魔术方阵pasca

49、l生成PASCAL矩阵除了以上产生标准矩阵的函数外，Matlab还提供了产生随机(向量)矩阵的函 数rand和randn,及产生均匀级数的函数linspace产生对数级数的函数logspace 和产生网格的函数meshgrid等等。详细使用请查阅随机文档。“：冒号可以用来 产生简易的表格，为了产生纵向表格形式，首先用冒号“:产生行向量，再进行转置，计算函数值的列，然后形成有二列的矩阵。322矩阵操作在Matlab中可以对矩阵进行任意操作，包括改变它的形式，取出子矩阵，扩充矩阵，旋转矩阵等。其中最重要的操作符为“:,”它的作用是取出选定的行与列。例如：A(:,:)代表A的所有元素；A(:,J)代

50、表A的第J列；A(J:K)代表A(J)，A(J+1)，A(K)，如同A(:)的第J到第K个元素；A(:,J:K)代表 A(:,J)，A(:,J+1)，A(:,K)。Matlab 中有内部函数 fliplr ( Flip matrix in the left/right direction)，它对矩阵进 行左右旋转。3.3矩阵的基本运算3.3.1矩阵乘法矩阵乘法用“* ”符号表示，当A矩阵列数与B矩阵的行数相等时，二者可 以进行乘法运算，否则是错误的。计算方法和线性代数中所介绍的完全相同。如：A=12 ;3 4; B=56 ;7 8; C=A*B，-23东北大学本科毕业设计(论文)第3章卷积码实现-27即Matlab返回：结果为12、z56、1x5 + 2x71 x 6 + 2x 8、1922、C=4X4350 丿C =19224350如果A或B是标量，则A*B返回标量A(或B)乘上矩阵B(或A)的每一个元 素所得的矩阵。3.3.2矩阵除法在Matlab中有两种矩阵除法符号：即左除和即右除。如果A矩阵是非奇异方阵，则AB是A的逆矩阵乘B，即inv(A)*B ;而B/A是B乘A的逆 矩阵，即B*inv(A)。具体计算时可不用逆矩阵而直接计算。x=AB就是A*x=B的解；