因果序列卷积的listconvolve 算法程序设计

毕业设计因果序列卷积的LISTCONVOLVE算法程序设计院系物理与电信工程学院专业电子信息科学与技术班级电信101班2014年5月20日因果序列卷积的LISTCONVOLVE算法程序设计摘要采用调用MATHEMATICA的内部函数LISTCONVOLVE进行因果序列卷积算法的程序设计，并编写因果序列卷积的LISTCONVOLVE算法和其它两种算法的程序，以及与其它两种算法的比较。并从实例展示其程序用法和高效性。关键字MATHEMATICA程序卷积LISTCONVOLVE算法因果序列CAUSALSEQUENCECONVOLUTIONALGORITHMDESIGNLISTCONVOLVEABSTRACTINVOKETHEMATHEMATICALISTCONVOLVEINTERNALFUNCTIONISADOPTEDTOIMPROVETHEPROGRAMLCAUSALSEQUENCECONVOLUTIONALGORITHMDESIGN,ANDWRITEACAUSALSEQUENCEOFCONVOLUTIONLISTCONVOLVEALGORITHMPROGRAMANDOTHERTWOKINDSOFALGORITHM,ANDCOMPAREDWITHTHEOTHERTWOALGORITHMSFROMEXAMPLESSHOWITSPROGRAMUSAGEANDEFFICIENCYKEYWORDSMATHEMATICAPROGRAMCONVOLUTIONLISTCONVOLVEALGORITHMCAUSALSEQUENCE；目录引言11因果序列卷积的意义22常见有限长因果序列卷积的计算方法221LISTCONVOLVE算法222矩阵乘法算法223矢量乘法算法23各种卷积计算方法程序实现的编程思路231各种算法编程前的准备2311构造滤波器2312计算滤波器时域系统函数的采样数据3313构造信号432因果序列卷积的各种算法编程实现6321LISTCONVOLVE算法程序设计6322矩阵乘法算法程序设计7323矢量乘法算法程序设计84各种卷积算法的比较941LISTCONVOLVE算法本身的比较942卷积的三种算法比较95应用实例96结语11致谢11参考文献12引言MATHEMATICA是由英国科学家斯蒂芬沃尔夫勒姆领导的著名公司沃尔夫勒姆研究公司开发的一款广泛使用的科学计算软件。它拥有强大的数值计算和符号运算能力，是使用最广泛的数学软件之一。MATHEMATICA的发布标志着现代科技计算的开始1。当然MATHEMATICA是世界上通用计算系统中最强大的系统。自从1988发布以来，它已经对如何在科技和其它领域运用计算机产生了深刻的影响。就像人们常说，MATHEMATICA的发布标志着现代科技计算的开始。自从上世纪六十年代以来，在数值、代数、图形、以及其它方面一直有个别的软件包存在。但是，MATHEMATICA的基本概念是用一个连贯的和统一的方法创造一个能适用于科技计算各个方面的软件系统。至于如何实现这一点的关键之处是发明了一种新的计算机符号语言。这种语言可以仅仅用很少量的基本元素制造出广泛的物体，而满足科技计算的广泛性。这在人类历史上还是第一次出现。而且长期以来，MATHEMATICA核心设计的普遍性使得它涉及的领域不断增长，扩大。从刚开始的是一个主要用于数学和科技计算的系统，到而今发展成为许多计算领域的主要力量，MATHEMATICA已经成为世界上最强大的通用计算系统之一。MATHEMATICA应用广泛，MATHEMATICA的用户群中最主要的是科技工作者和其它专业研究人士。不仅如此，MATHEMATICA还被广泛地用于教学中。数学中的许多计算是非常繁琐的，特别是函数的作图费时又费力，而且所画的图形很不规范，所以现在流行用MATHEMATICA符号计算系统进行学习，从高中到研究生院的数以百计的课程都是在使用它，很多问题便可以迎刃而解。此外，随着学生版的出现，MATHEMATICA已经在全世界的学生中流行起来，成为了一个著名的学习，研究工具。在运算领域里，MATHEMATICA作为当前国际控制界最流行的面向工程与科学计算的高级语言，近年来得到了业界的一致认可27。而且在控制各种系统的分析、设计算法方面得到了非常广泛的应用，其自身也因此得到了迅速的发展，功能也在不断扩充。便于对通信系统的物理概念和运行过程的直观理解，所以近年来在通信工程专业中得到了广大师生的特别重视和广泛的应用，在理论教学、课程实践环节，以及理论和技术前沿的研究中发挥了非常重要作用。而传统的因果序列卷积运算方法主要可以归纳为图解法,解析法,位移法和乘式法，矩阵乘法和矢量乘法等等。至于图解法直观明了但烦琐,不便于编程计算而解析法适合于短序列编程,当序列较长时,表达式冗长,不便于编程计算乘式法与解析法有相同特点,不适合较长的两个序列的卷积和运算移位法有效的解决了较长序列的卷积和运算,是一种较好的计算方法,特别对于长序列更显示出其计算能力,但是需要考虑数据存储结构问题,而且也不便于理解。而本次毕业设计中主要提出了另一种计算方法,即LISTCONVOLVE算法，易于编程，算法高速8。LISTCONVOLVE算法适用于因果序列卷积的运算,而且算法高速，占据内存小，因此是一种有效的计算方法在工程实际中具有较大的应用价值。在此调用MATHEMATICA软件中的软件LISTCONVOLVE算法进行程序设计，使其能够实现因果序列卷积的LISTCONVOLVE算法的运算，使卷积运算更加简便。许多文献讨论了卷积的计算方法以及对各种算法的总结，离散信号的卷积的多种求解方法，包括解析法、列表法、利用卷积和性质求解，应用单位样值信号求解，LISTCONVOLVE算法，矩阵算法及矢量空间算法。一般利用定义式、图解法和卷积性质这些通用方法进行求解连续信号的卷积或离散信号的卷积和。其中，利用定义式及卷积性质的求解，需要根据信号形式做繁琐的积分或求和；利用图解法进行的反转、平移、相乘、求和四个步骤，绘图过程麻烦9。而利用LISTCONVOLVE算法则简单高速，但算法不够透明，而矩阵算法则属于算法过程透明，但却占内存过大，矢量空间算法则运算时间过长。总之各种算法都有利有弊。本文将利用矩阵乘法和矢量乘法与LISTCONVOLVE算法相比较来突显出LISTCONVOLVE算法的优越性。对于本文来说，主要研究了LISTCONVOLVE算法的如何调用，矩阵乘法算法和矢量乘法算法的计算方法是如何实现的。以及如何各种算法的程序编写10。因为卷积在信号处理过程中是很常见的，所以研究如何实现卷积滤波是非常只有用的。相信卷积滤波会得到广泛应用。1因果序列卷积的意义任意两个序列的卷积并无意义的，只有一个代表离散信号的序列FK与描述离散LTI系统的序列GK（GK是离散LTI系统在单位脉冲序列K在它激励下的零状态响应。）卷积YKFKGK才有真实的物理意义，它就是离散LTI系统在输入离散信号FK激励下的零状态响应，即系统的输出，能够代表真是的离散信号的序列，只能是因果序列，所以，本文只讨论一个描述输入信号的有限长序列与一个描述系统滤波特性的有限长序列之间的卷积，其结果是输入信号经过滤波器滤波后的结果。因为在信号处理过程中会常遇到卷积计算问题，所以对于研究因果序列卷积的算法是非常有用的。2常见有限长因果序列卷积的计算方法21LISTCONVOLVE算法LISTCONVOLVE算法，对于学者而言，只知道经过编程实践发现，它的算法很优越，省时省空间，目前来说它的时间复杂度和空间复杂度都是最低的。它是由世界著名软件公司（MATHEMATICA软件）的精英们设计的，所以也只有他们清楚其内部算法。这种算法的透明度不高，至于为什么还要对其进行研究，是因为要学习如何熟练的使用它，如何熟练地调用其内部函数，以充分的利用其高速性与占据内存小的特点。22矩阵乘法算法矩阵乘法是一种高效的算法可以把一些一维递推优化到LOG（N，还可以求路径方案等，所以更是一种应用性极强的算法。矩阵，是线性代数中的基本概念之一。一个MN的矩阵就是MN个数排成M行N列的一个数阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型。例如序列X2,3,4和序列Y4,5,6,7的卷积，可以等效为矩阵234和矩阵作卷积结果为16,22,43,52,45,2845670023矢量乘法算法将两个长度分别为M与N的序列X，Y进行卷积求和，则其卷积结果序列长度为LMN1,其计算过程为，第一个序列保持不变，第二个序列补M1个零，放在前面，后面加上倒置的第二个序列，构成新的第二个序列，在相乘的过程中，新生成的第二个序列每乘一次就右循环滚动一次（第一次乘就要右循环滚动一次），其求和方式为每一次对应位置相乘求和，即为矢量乘法算法。例如序列X2,3,4和序列Y4,5,6,7的卷积，Y序列改写为Y14,0,0,7,6,5Y60,0,7,6,5,4卷积结果如下8，22，43，52，45，283各种卷积计算方法程序实现的编程思路因为有物理意义的卷积是，一个序列代表输入信号，另一个描述滤波器的滤波特性，它们的卷积结果就是信号加到滤波器上以后，滤波的输出信号，所以，要讨论序列卷积，都必须先准备描述滤波器的序列。因此，有如下编程。31各种算法编程前的准备311构造滤波器滤波器设计主要是借助MATLAB，设计程序如下确定阶数255；确定通带上限频率；N255W025BFIR1N,WSAVEZJFILTER,B312计算滤波器时域系统函数的采样数据TS001FS1/TSB00000764706,00001864,0000188868,00000795429,00000811504,0000200526,0000205885,00000878161,0000090675,0000226607,0000235119,0000101259,0000105479,0000265703,0000277638,0000120318,0000126014,0000318913,0000334555,0000145459,0000152751,0000387389,0000407035,0000177171,0000186186,0000472349,0000496314,0000215976,000022685,0000575094,0000603722,0000262434,0000275315,0000697038,0000730702,0000317159,000033221,0000839738,0000878855,0000380831,0000398235,000100494,000104998,0000454219,0000474185,000119462,000124613,0000538208,0000560979,000141109,000146971,0000633833,0000659697,000165708,000172356,0000742329,0000771633,000193586,000201113,0000865196,0000898366,000225145,000233666,000100429,000104186,000260885,000270545,000116194,000120458,000301444,000312429,000134114,000138974,000347646,000360199,00015458,000160153,000400579,000415026,000178116,000184558,000461713,0004785,000205434,000212963,000533079,000552834,000237534,000246463,000617569,0006412,000275862,000286649,000719432,000748305,000322583,000335934,00084517,000881436,000381089,000398144,00100525,00105248,000457004,000479728,0012176,00128223,000560359,000592447,00151574,00161053,00071094,00076023,00197024,00212454,000953894,00104034,00275931,00305833,00141941,00161227,0045,00532711,00270068,00347619,011759,0196093,0243741,0243741,0196093,011759,00347619,00270068,00532711,0045,00161227,00141941,00305833,00275931,00104034,000953894,00212454,00197024,00076023,00071094,00161053,00151574,000592447,000560359,00128223,0012176,000479728,000457004,00105248,00100525,000398144,000381089,000881436,00084517,000335934,000322583,000748305,000719432,000286649,000275862,0006412,000617569,000246463,000237534,000552834,000533079,000212963,000205434,0004785,000461713,000184558,000178116,000415026,000400579,000160153,00015458,000360199,000347646,000138974,000134114,000312429,000301444,000120458,000116194,000270545,000260885,000104186,000100429,000233666,000225145,0000898366,0000865196,000201113,000193586,0000771633,0000742329,000172356,000165708,0000659697,0000633833,000146971,000141109,0000560979,0000538208,000124613,000119462,0000474185,0000454219,000104998,000100494,0000398235,0000380831,0000878855,0000839738,000033221,0000317159,0000730702,0000697038,0000275315,0000262434,0000603722,0000575094,000022685,0000215976,0000496314,0000472349,0000186186,0000177171,0000407035,0000387389,0000152751,0000145459,0000334555,0000318913,0000126014,0000120318,0000277638,0000265703,0000105479,0000101259,0000235119,0000226607,0000090675,00000878161,0000205885,0000200526,00000811504,00000795429,0000188868,00001864,00000764706LLENGTHBLHFLOORL/2TSRANGE0,L1TSLISTPLOTTRANSPOSETS/TS,B,FILLINGAXIS,AXESLABEL“T/TS“,“HN“,PLOTRANGEALL,PLOTSTYLEPOINTSIZE0005B2FOURIERB,FOURIERPARAMETERS1,1B1/2BAABSB1LHCURLYPHIARGB1LHFRANGE0,LH1FS/LLISTPLOTTRANSPOSEF,BA,FILLINGAXIS,PLOTSTYLEPOINTSIZE0005,PLOTRANGEALL,AXESLABEL“F/HZ“,“AF“LISTPLOTTRANSPOSEF,CURLYPHI,FILLINGAXIS,PLOTSTYLEPOINTSIZE0005,PLOTRANGEALL,AXESLABEL“F/HZ“,“CURLYPHIF“313构造信号A10,5,4,1,05,7,2,4F2,6,8,10,13,15,18,20CURLYPHI00,0,PI/2,PI/4,PI/8,PI/12,0,PI/20LALENGTHAXT_SUMAKCOS2PIFKTCURLYPHI0K,K,1,LAP1PLOTXT,T,0,256SL2000M100TS2RANGE0,SL1TSXNXTS2P2LISTPLOTTRANSPOSETS2,XN1M,FILLINGRULEAXISJOINEDTRUE,PLOTSTYLEPOINTSIZE0005,AXESLABEL“T/TS“,“XN“程序运行结果如下滤波器单位冲激响应时域波形如图31图31滤波器单位冲激响应时域波形图滤波器幅频特性如图32图32滤波器幅频特性波形图滤波器相频特性如图33图33滤波器相频特性波形图待处理信号滤波器波形如图340204060810TTS2010102030XN图34待处理信号滤波器波形32因果序列卷积的各种算法编程实现321LISTCONVOLVE算法程序设计CLEARX,Y,A,B,C,D,U,V,WTK0,0,0,3600,60,1XTABLERANDOM,K,5000YTABLERANDOM,K,8000T3DATEZ3LISTCONVOLVEX,Y,1,1,0T4DATELISTPLOTZ3,FILLINGAXIS,ASPECTRATIO1/4,PLOTRANGEALL,PLOTSTYLEPOINTSIZE00001,AXESORIGIN0,0PRINT“引用LISTCONVOLVE函数方法计算耗时“,T4T3TK,“SEC“运行结果引用LISTCONVOLVE函数方法计算耗时0108SEC运行结果图35LISTCONVOLVE算法运行图IN3CLEARU,V,W,X,Y,Z,PLISTCONVOLVEU,V,W,X,Y,Z,P,1,1,0OUT4UX,VXUY,WXVYUZ,PUWYVZ,PVWZ,PW322矩阵乘法算法程序设计CLEARX,Y,Z,STK0,0,0,3600,60,1XTABLECOSPIK/171EXP00002K,K,0,79YTABLE0999K,K,0,59T1DATEZ2LISTCONVOLVEX,Y,1,1,0T3DATENLENGTHXMLENGTHYLNM1Y0PADRIGHTY,LTEMY0MTEMFORJ1,J1/4,PLOTRANGEALL,PLOTSTYLEPOINTSIZE00001PRINT“按矩阵乘法计耗时“,DATET1TK,“SECNLISTCONVOLVE用时“,T3T1TK,“SEC“204060801001201401020304050图36矩阵乘法算法运行图按矩阵乘法计算耗时01080062SECLISTCONVOLVE用时00010000SEC323矢量乘法算法程序设计CLEAR“X“,“Y“,“Z“,STK0,0,0,3600,60,1XTABLECOSPIK/171EXP00002K,K,0,9999YTABLE0999K,K,0,9T1DATEMLENGTHXNLENGTHYLMN1ZCONSTANTARRAY0,LSJOINCONSTANTARRAY0,M1,YN11FORJ1,JALL,PLOTSTYLEPOINTSIZE0006,REDP2LISTPLOTZ2115,PLOTRANGEALL,PLOTSTYLEPOINTSIZE0003,BLUESHOWP1,P2PRINT“矢量乘法用时“,T2T1TK,“SECNLISTCONVOLVE用时“,T3T2TK,“SEC“2468101214246810图37矢量乘法算法运行结果矢量乘法用时123147043SECLISTCONVOLVE用时00840048SEC4各种卷积算法的比较41LISTCONVOLVE算法本身的比较表41LISTCONVOLVE算法不同长序列耗时比较算法名称序列（长度）耗时1250008000极短，可以忽略不计LISTCONVOLVE算法100002000000156000SEC500008000000468001SECLISTCONVOLVE算法本身是一种非常高速的算法，在序列数值不大的情况下算法耗时几乎看不到，但在其对序列长度差异很大的序列进行卷积运算时还是会有耗时上的差异，即长序列耗时大于短序列耗时。42卷积的三种算法比较表42卷积的三种算法比较算法名称序列（长度）耗时时间，空间复杂度12LISTCONVOLVE算法极短都很小矩阵乘法算法50008000无法计算空间复杂度过大矢量乘法算法171444299SEC都一般根据本次毕业设计对以上三种算法的对比，可以明显体现出LISTCONVOLVE算法的高速性，当然，这三种算法也各有利弊，对于LISTCONVOLVE算法当然就用来计算长序列数值大的这类序列卷积，而矩阵算法则用于学者做研究，至于矢量空间算法一般不太用。所以，在选择运用那种算法时，要结合它们的特点来选择。5应用实例N63WP03FPWPFS/2BFIR1N,WPSAVE“ZJ009“BCDH0000798867,0000390074,0000436796,000110852,0000950907,0000255716,00017797,000217304,0000463884,000253415,000424909,000232847,000275781,000706324,0005921,000152669,00100959,00116871,000237057,00123678,00199452,00106029,00123052,00312472,0026339,000694942,00481115,00601859,00138395,0088797,0208625,0289004,0289004,0208625,0088797,00138395,00601859,00481115,000694942,0026339,00312472,00123052,00106029,00199452,00123678,000237057,00116871,00100959,000152669,0005921,000706324,000275781,000232847,000424909,000253415,0000463884,000217304,00017797,0000255716,0000950907,000110852,0000436796,0000390074,0000798867FS100TS1/FSTA0TB5NTBTA/TSTSRANGE0,N1TSLLENGTHHTS1RANGE0,L1TSLISTPLOTTRANSPOSETS1,H,FILLINGAXIS,PLOTRANGEALL,PLOTSTYLEPOINTSIZE0008,AXESLABEL“SUBSCRIPTT,K/S“,“HSUBSCRIPTT,K“FRANGE0,L/21FS/LHFOURIERH,FOURIERPARAMETERS1,1LISTPLOTTRANSPOSEF,ABSH1L/2,JOINEDTRUE,PLOTSTYLEPOINTSIZE0008,AXESLABEL“F/HZ“,“|HF|“ST_10COS10PIT5COS40PIT2COS80PIT05COS100PITSNSTSLISTPLOTTRANSPOSETS,SN1100,FILLINGAXIS,PLOTRANGEALL,PLOTSTYLEPOINTSIZE0008,AXESLABEL“SUBSCRIPTT,K/S“,“SSUBSCRIPTT,K“ZNLISTCONVOLVEH,SN,1,1,0YNZNL/2NL/21LISTPLOTTRANSP