《有限长序列线性卷积快速计算方法.doc》由会员分享，可在线阅读，更多相关《有限长序列线性卷积快速计算方法.doc（7页珍藏版）》请在金锄头文库上搜索。
1、 目录1. 概述22. 有限长序列线性卷积原理22.1. 序列卷积的定义22.2. 序列卷积的性质22.3. DFT32.4. FFT算法33. 在Mathematica中实现有限长序列线性卷积快速计算44. 结束语6 有限长序列线性卷积快速计算方法 白亮亮 （陕理工物理系电信072班级）指导教师：龙姝明1. 概述 在数字信号处理领域，离散时间系统的输出响应，可以直接由输入信号与系统单位冲激响应的离散卷积得到。离散卷积在电子通信领域应用广泛，是工程应用的基础。如何快速有效地计算出离散序列的卷积，一直是人们所关心的问题。如果直接在时域进行卷积，卷积过程中所必须的大量乘法和加法运算，一定程度地限制
2、了数据处理的实时性，不能满足时效性强的工程应用。探讨卷积的快速软件实现方法。许多文献讨论了卷积的计算方法麻烦。随着计算机技术的发展，越来越多的计算问题交由计算机处理。Mathematica作为优秀的科学计算软件，在工程计算、信号处理与通讯、图像处理等领域均得到广泛的应用。本文从实际应用出发，使用Mathematica从卷积定义、傅里叶变换DFT、快速傅里叶变换(FFT)技术方面来实现有限长序列线性卷积的快速计算。2. 有限长序列线性卷积原理2.1. 序列卷积的定义设给定两个有限长序列、，则称（）为两个有限长序列的线性卷积2.2. 序列卷积的性质交换律：（）分配律：（） 结合律： （）与单位序列
3、的卷积是它本身：（）2.3. DFT 设有限长序列的长度为M，它的DFT为 k=0,1,N-1 （6）傅里叶变换的逆变换如下： k=0,1N-1 (7)2.4. FFT算法 序列的点DFT为 （8）由于，将上式按n的奇偶性可以分解为 其中 ， （9） 这样N点DFT经过分解变成两个 点的DFT变换 复数加法和复数乘法运算次数由原来的 降到 当 时 N点DFT的运算量减少到近原来的一半 经过多次这样的抽样分解来实现快速傅里叶变换的 根据时域循环卷积定理，x(n)与y(n)的线性卷积可以用循环卷积来代替。给出了一个基于快速傅里叶变换(FFT)的卷积的实现方法，如图1所示。分别对补零后的x(n)和y
4、(n)进行FFT运算，得到对应的频域响应X(k)和Y(k)，将X(k)和Y(k)相乘的结果再做IFFT，即可以得到x(n)和h(n)的卷积结果y(n)FFT IFFT x(n)X(k)FFT y(n) Y(k)Z(k)z(n) 图1 有限长序列线性卷积框图3. 在Mathematica中实现有限长序列线性卷积快速计算 Clearx,y,z,X,Y,m,n,xdata,X1,Z1,k,z1;x=5.25856,5.36618,5.02709,5.77786,5.28104,5.91579,5.84052,5.51468,4.97816,5.27166,5.84789,5.01951,5.2881
5、4,5.17372,5.46323,5.49417,5.7322,4.76301,4.86094,5.39123,5.05035,4.92522,4.79883,4.69632,4.6403,5.39888,4.60129,4.73609,5.16334,4.27199,4.53288,4.97513,4.91889,4.71245,4.37391,4.61977,4.26855,4.14863,4.4911,4.675,4.05321,3.86839,4.07735,3.69387,4.37437,4.27464,3.56848,3.24454,3.93667,4.03253,3.07675
6、,3.5694,3.78431,3.72019,3.45085,3.44727,2.66314,2.74888,2.76025,2.45175,2.95853,2.10271,2.70892,2.15267,2.21627,2.47916,1.80922,2.56819,1.88196,2.17424,2.13912,2.14971,1.69807,1.82028,1.66584,1.10778,1.36439,1.47306,1.5095,0.875761,0.83652,0.778726,0.722388,0.315086,0.686349,0.401061,0.654607,0.7190
7、97,-0.0582219,0.308125,0.145661,0.364799,0.186908,0.1738,-0.0410723,-0.920366,-0.734762,-0.958481,-1.10755,-0.517617;xL=Lengthx;y=12.9807,12.1693,11.7929,12.6385,12.445,14.5169,14.019,12.7954,14.1967,13.8327,15.2822,13.5732,14.0145,15.2597,13.905,14.2472,14.9313,15.9254,14.9256,14.6166,14.4557,15.83
8、37,14.9947,15.6307,15.6658,15.0256,14.7296,14.6828,15.0701,15.5127,15.8653,17.1888,16.3172,17.262,16.2991,16.4613,15.2738,15.0945,15.6029,15.535,16.771,15.7006,17.3073,17.6423,16.1285,16.7648,16.2905,16.0646,17.5863,15.9284,15.811,15.6881,16.8738,14.8197,17.3912,15.9816,15.0706,15.0986,15.6551,17.10
9、03,14.3891,14.6036,14.654,16.1645,15.2097,16.4822,14.9084,16.0617,13.5935,14.1975,13.0611,14.3985,13.3618,15.5721,14.4967,12.8958,13.6074,14.801,14.0786,13.8071,12.3448,13.4208,12.0478,13.2322,11.3778,12.1314,10.5956,10.1526,12.1317,11.4872,11.3953,9.66466,10.9736,9.5823,10.4799,10.261,9.45163,8.691
10、04,10.501,8.71633;yL=Lengthy;ListPlotx,Filling1Axis,Blue,AxesLabelk,x(k)ListPloty,Filling1Axis,Red,AxesLabelk,y(k)X1m_=Sumxn+1 -2 p n I m/xL,n,0,xL-1;Y1m_=Sumyn+1 -2 p n I m/yL,n,0,yL-1;Z1m_=X1m Y1m;z1k_=1/xL SumZ1m 2 p k I m/xL,m,0,xL-1;xdata=Tablem,Absz1m,m,0,xL-1;LengthxdataListPlotxdata,Filling-
11、1Axis,Red,PlotRangeAllListPlotxdata,Filling-1Axis,Red,PlotRangeAll 图2 x(k)序列 图3 y(k)序列 图4 x(k)y与y(k)卷积的图 X=Fourierx,FourierParameters1,-1;Y=Fouriery,FourierParameters1,-1;z=FourierX Y,FourierParameters-1,1;ListPlotz,Filling1Axis,Red,AxesLabelk,z(k)=x(k)*y(k),PlotRange-All 图5 x(k)与y(k)卷积的图4. 结束语 本文讨论了用Mathematica计算有限长序列线性卷积和方法与实现过程，用到了序列的卷积的定义、傅里叶变换、快速傅里叶变换等相关的理论知识，大大削减了信号处理过程中的计算量，在通信、信号处理等领域有很好的应用前景，这次课设也是我学到了很多。在此，感谢在这次课设中老师的指导。 参考文献 1吴大正、杨林耀、张永瑞、王松林等主编的信号与线性系统分系高等教育出版社.2丁玉美、高西全等主编的数字信号处理西安电子科技大学出版社.1
