《有限长序列线性卷积快速计算方法》由会员分享，可在线阅读，更多相关《有限长序列线性卷积快速计算方法（7页珍藏版）》请在金锄头文库上搜索。
1、目录1. 概述22. 有限长序列线性卷积原理22.1. 序列卷积的定义22.2. 序列卷积的性质32.3. DFT32.4. FFT 算法33. 在Mathematica中实现有限长序列线性卷积快速计算44. 结束语6有限长序列线性卷积快速计算方法白亮亮(陕理工物理系电信072班级)指导教师：龙姝明1. 概述在数字信号处理领域，离散时间系统的输出响应，可以直接由输入信号与系统单位冲激 响应的离散卷积得到。离散卷积在电子通信领域应用广泛，是工程应用的基础。如何快速有 效地计算出离散序列的卷积，一直是人们所关心的问题。如果直接在时域进行卷积，卷积过 程中所必须的大量乘法和加法运算，一定程度地限制了
2、数据处理的实时性，不能满足时效性 强的工程应用。探讨卷积的快速软件实现方法。许多文献讨论了卷积的计算方法麻烦。随着 计算机技术的发展，越来越多的计算问题交由计算机处理。Mathematica作为优秀的科学计 算软件，在工程计算、信号处理与通讯、图像处理等领域均得到广泛的应用。本文从实际应 用出发，使用Mathematica从卷积定义、傅里叶变换DFT、快速傅里叶变换(FFT)技术方面 来实现有限长序列线性卷积的快速计算。2. 有限长序列线性卷积原理2.1. 序列卷积的定义设给定两个有限长序列f a)、f (k)，则称f (k)= f (k)* f (k)=丈1 2f (f (k - i)(1)
3、1 2i=0为两个有限长序列的线性卷积2.2. 序列卷积的性质交换律：f a)* f )= f )* f a)12 2 1分配律：f )* f )+ f(k)L f (k)* f (k)+ f (k)* f (k)* f (k)J 3结合律:f (k)* If (k)* f QLf (k)* f (k)12312(2)(3)(4)f(k)与单位序列的卷积是它本身：f(k)*5(k)=8(k)*f(k)= f(k)(5)2.3. DFT设有限长序列的长度为M,它的DFT为XG)= DFtLCi)=艺x(n丄-j2Tk=O,l,N-1Nn=0傅里叶变换的逆变换如下：k=O,l N1x(n )= I
4、DFT x Q=艺 X (、产N n Nk=02.4. FFT 算法序列x(n)的N(N = 2m )点DFT为X G)= 1 x(n ly knk = 0,1,N 一 1(8)Nn=0由于W2ki = Wki，将上式按n的奇偶性可以分解为Nn2x 4)=3 (i Wki + Wk%x (lWkik = 0,1,N-11N -N2 N 2l=02l=0其中 x G)= x(2l), x G)= x(2l +1)1 2这样N点DFT经过分解变成两个N2点的DFT变换 复数加法和复数乘法运算次数由原来的N 2降到N22当N1时 N点DFT的运算量减少到近原来的一半经过多次这样的抽样分解来实现快速傅
5、里叶变换的根据时域循环卷积定理，x(n)与y(n)的线性卷积可以用循环卷积来代替。给出了一个 基于快速傅里叶变换(FFT)的卷积的实现方法，如图1所示。分别对补零后的x(n)和y(n) 进行FFT运算，得到对应的频域响应X(k)和Y(k)，将X(k)和Y(k)相乘的结果再做IFFT，即可以得到x(n)和h(n)的卷积结果y(n)图1有限长序列线性卷积框图3. 在Mathematica中实现有限长序列线性卷积快速计算Clearx,y,z,X,Y,m,n,xdata,Xl,Zl,k,zl; x=5.25856,5.36618,5.02709,5.77786,5.28104,5.91579,5.84
6、052,5.51468,4.97816,5.27166,5.8478 9,5.01951,5.28814,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.712 45,4.37391,4.61977,4.26855,4.14863,4.4911,4.675,4.05321,3.86839,4.07735,3.69387,4.
7、37437,4.2 7464,3.56848,3.24454,3.93667,4.03253,3.07675,3.5694,3.78431,3.72019,3.45085,3.44727,2.6631 4,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.8 75761,0.83652,0.7
8、78726,0.722388,0.315086,0.686349,0.401061,0.654607,0.719097,-0.0582219, 0.308125,0.145661,0.364799,0.186908,0.1738,-0.0410723,-0.920366,-0.734762,-0.958481,-1.107 55,-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,1 3.5732,14.0145,15.2597,
9、13.905,14.2472,14.9313,15.9254,14.9256,14.6166,14.4557,15.8337,14.9 947,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.7 648,16.2905,16.0646,17.5863,15.9284,15.811,15.688
10、1,16.8738,14.8197,17.3912,15.9816,15.0706 ,15.0986,15.6551,17.1003,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.807 1,12.3448,13.4208,12.0478,13.2322,11.3778,12.1314,10.5956,10.1526,12.1317,11
11、.4872,11.3953, 9.66466,10.9736,9.5823,10.4799,10.261,9.45163,8.69104,10.501,8.71633; yL=Lengthy;ListPlotx,FillingDimAxis,Blue,AxesLabelmk,x(k)ListPloty,FillingDlDAxis,Red,AxesLabelDk,y(k)X1m_=Sumxn+1 口-2 口 n I m/xL,n,0,xL-1;Y1m_=Sumyn+1 口-2 口 n I m/yL,n,0,yL-1;Z1m_=X1m Y1m;z1k_=1/xL SumZ1m 口2 口 k I
12、m/xL,m,0,xL-1;xdata=Tablem,Absz1m,m,0,xL-1;LengthxdataListPlotxdata,Filling-1DAxis,Red,PlotRangeDAllListPlotxdata,Filling-1D Axis,Red,PlotRangeDAlly(k161430ut6=1220406080 4700460045004400图2x(k)序列204060图3 y(k)序列8010、k)的图 4 x(k)y4300406080100X=Fourierx,FourierParameters口 1,-1;Y=Fouriery,FourierParameters口 1,-1;z=FourierX Y,FourierParametersD -1,1;ListPlotz,Filling 口 1 口 Axis,Red,AxesLabel 口 k,z(k)=x(k)*y(k),PlotRange-Allz(k)=x(k)+y(k)算量，在通信、信号处理等领域有很好的应用前景，这次课设也是我学到了很多。在此，感 谢在这次课设中老师的指导。参考文献1 吴大正、杨林耀、张永瑞、王松林等主编的信号与线性系统分系高等教育出版社.2 丁玉美、高西全等主编的数字信号处理西安电子科技大学出版社.
