fft算法实验报告

实验名称：FFT算法的实现老师：卫国学生：张园园学号：PB12207051实验2FFT算法的实现实验报告2实验目的：1.加深对FFT变换的理解。2.掌握FFT算法和其程序的编写。3.掌握算法性能测评的方法。实验原理：在各种信号序列中，有限长序列在数字信号处理中占有重要的地位。无限长的序列往往也可以用有限长的序列来逼近。对于有限长的序列我们可以用离散傅里叶变换（DFT），之一变化可以很好地反应序列的频域特性，并且容易利用快速算法在计算机上实现。当序列的长度为N时：定义离散傅里叶变换为：10()[(n)](n)NknNnXkDFTxxW其中2jNNWe。它的反变换定义为：101(n)[X(k)](k)WNknNkxIDFTXN。但若直接计算DFT变换，运算的复杂度和序列长度的平方成正比，所以没法用计算机实现大规模数据的处理。为此，FFT算法应运而生，FFT是一种为了减少DFT算法的复杂度而出现的快速算法。它对变换式（1）进行一次次的分解，使其成为若干小点数的DFT的组合，从而减小运算量。常用的FFT是以2为基数，其长度N=2M，算法的流程图可以用蝶形算法来表示，以8点的基2-FFT算法为例，其蝶形图为：图18点序列基2—FFT算法蝶形图当需要进行变换的序列长度不是2的整数次方时，可以用末尾补零的方法，使其长度延长至2的整数次方。IFFT一般可以通过FFT程序完成。比较式（1）和（2），只要对()Xk取共轭，进行FFT运算，然后再取共轭，并乘以因子1/N，就可以完成IFFT。实验内容和结果分析实验2FFT算法的实现实验报告31．程序如下：1.function[]=myfft(M);M是序列长度；2.ml=log2(M);3.n=1:M;4.x=n.^2.*sin(n);％x是序列，进行测试的序列为：x(n)=n2sinn；5.x1=zeros(1,M);6.x1=x(bitrevorder(n-1)+1);％对序列进行反序存储；7.n=1:ml;8.w=exp(-j*2*pi./2.^n);％第n层的旋转因子；9.forn=1:ml;％n表示在做第n层蝶形运算；10.forjk=1:M/(2^n);％jk表示第n层蝶形运算的个数；11.form=1:2^(n-1);12.p=x1((jk-1)*2^n+m);13.q=x1((jk-1)*2^n+m+2^(n-1));14.x1((jk-1)*2^n+m)=p+q*(w(n)^(m-1));15.x1((jk-1)*2^n+m+2^(n-1))=p-q*(w(n)^(m-1));％做蝶形运算16.end;17.end;18.end;19.20.y=fft(x);％用matlab中的fft函数计算；21.Y=abs(y);22.z=x1-y;％将自己程序的结果和matlab的fft函数的结果进行比较；23.figure;24.stem(abs(z));25.26.27.end2.验证程序的有效性选取序列为：2(n)sinnxn，n1；为了能清晰的看出结果，我们用64个点做测试，用自己的程序做FFT，得到的幅频特性图为：实验2FFT算法的实现实验报告4图2用自己的fft程序得到的64点序列的幅频图和matlab中的FFT函数进行比较的结果为（用MATLAB中FFT函数的结果和自己程序的结果做差再取绝对值）：图2自己的程序和matlab的fft函数的比较结果（N=64）由图2可知，两个结果差距在1110量级，故自己的FFT程序是有效的。也可以做更长序列的FFT，结果依然有效。幅度幅度实验2FFT算法的实现实验报告53.对所编写的FFT程序进行性能评估。评价一个算法的性能，主要从时间复杂度和空间复杂度两方面进行评价。随着硬件设备的发展，空间复杂度对算法性能的影响越来越小，算法的时间复杂度变得更加重要。而时间复杂度主要依赖于算法的运算次数，众所周知，基2-FFT算法的复数乘法次数为2log12NN。所以，从算法的时间复杂度上来看，基2-FFT算法肯定优于直接DFT算法。在matlab中，为了验证比较两个算法直接的效率，常常需要计算某段程序的运行间，而常用的也就是三种方法：①tic和toc命令对。tic命令表示开启一个matlab的计时器，toc则表示停止之前与之对应的tic开启的计时器，并得到最后的计时结果。②clock加etime函数。clock命令是获取系统的时间矢量，而etime函数则是计算两个时间矢量之间的差并以秒单位形式表示。其中，clock作为时间矢量包含了年月日时分秒六个参数。③用两个cputime命令计算运行时间。其中，cputime命令是获取matlab自启动后所占用cpu的运行时间。首先，从精度上来说，第一种方法精度最高，由于是matlab自身的计时器，精度上要比后两者高，其次是cputime，最低的是clock只有毫秒级的精度。再者，从最接近实际电路运行时间上来说，也是第一种方法最为接近，我们知道，想得到某段程序在matlab中运行的时间，目的是在于对该程序所实现的算法在实际电路中处理的时间有个大概的估计与比较，所以我们最想要的是它在cpu运行的时间。这一点第二种方法则不太适合了，因为它采用的是系统时间作为计算参数，在这个时间内肯定还有着别的后台运行程序等。而对于第三种方法，cputime所对应的测量对象是matlab整个程序，而并不是对于我们所测量的这段程序而（matlab也可以看做是一个编译器，对我们编写的m代码进行编译，所以它还需要进行着别的操作）。再看看我们的第一种matlab推荐的方法，tic是启动一个matlab内部的计时器，所以说它也是一种基于cpu时间的计时，而且更重要的是，计时开始的时间是我们设定在代码前的，可以说tic和toc中间对于matlab来说，大部分时间就是运行这段代码，所以时间上是最接近实际在电路中运行的时间的。所以我们采用tic和toc命令对进行测试。1)为了验证基2-FFT算法的优势，对自己所编写的FFT程序和直接用DFT算法写的程序进行比较。采取的方法是将两个程序分别连续执行20次，比较平均时间的长短，测试序列为：2(n)sinnxn，n1。测试程序如下：clearall;tic;forf=1:100;clearall;myfft(2048);clearall;实验2FFT算法的实现实验报告6end;toc;因为考虑到matlab在第二次执行myfft时matlab已经将所需要的函数编译到内存已经为myfft函数中的变量申请到了空间，所以程序执行时间会大大降低，但是并不合理，所以用了两个clearall命令。同时考虑到for循环也要消耗一定的时间，但是当执行myfft函数的次数比较多时，这一部分时间可以忽略不计，而且不管是对myfft还是dft函数for循环增加的运行时间是一样的，故可以这样进行测试。另外，程序的运行时间和计算机的性能也有很大关系，所以，这里的数据只是我在自己的笔记本上跑的结果，和别人的结果没有直接的可比性。100次tlog2(N)程序12345myfft3.0326953.0244233.0456663.0692803.085829mydft0.5514180.5506830.5506220.5523540.5955856789101112133.1874693.2784993.6040924.2785005.7156488.98899215.86307930.9139830.7438611.3632764.12458516.14093763.603917283.746271290.5141516171863.383829133.734814290.890308615.335191表1myfft和直接做dft程序运行时间表注：myfft为运行是基于fft算法的程序，mydft是基于直接dft算法的程序；画斜线的表示matlab出现内存空间不够，没法运行。也可以此说明计算的复杂度。画出的曲线为：实验2FFT算法的实现实验报告7当序列的长度N较小时，myfft程序因为执行的操作更加复杂，所以，运算时间长于mydft程序，但是当N增大时，myfft程序的优势变得越来越明显，运算时间明显短于mydft。同时，由图可以看出，mydft的运算时间曲线的增长速度比myfft快得多。所以，可以说明基2-FFT算法在时间复杂度上优于直接DFT算法。2)在空间复杂度上分析比较基2-FFT算法和直接DFT算法：因为做蝶形运算不需要申请额外的存储空间，而直接DFT算法在计算的过程中，需要用到NN的矩阵。所以，从空间复杂度上开看，基2-FFT算法还是较优。4．myfft程序和matlab程序fft函数的性能比较：采用和3相同点方法，比较两个函数运行100次的时间。100次tlog2(N)程序12345Myfft3.0326953.0244233.0456663.0692803.085829Matlab中的fft函数0.2395750.2497470.2464460.2541970.252704024681012141618程序执行时间log2(N)图3myfft和mydft程序执行时间的比较myfftmydft实验2FFT算法的实现实验报告86789101112133.1874693.2784993.6040924.2785005.7156488.98899215.86307930.9139830.2488390.2499150.2470000.2479720.2798950.2705660.3037480.293595141516171863.383829133.734814290.890308615.3351910.3406460.4191550.5640450.8320721.380966表2myfft和matlab的fft函数运算时间表画出曲线来：由此可以看出，自己编写的myfft函数性能明显比matlab中的fft函数差：对于特定长度的序列后者的运算时间比前者短得多，而且，随着N增大，myfft函数的运算时间的增长速度也比fft函数快得多。因为matlab中的fft函数是用更底层的C语言写的，并且进行了非常好的优化，所以这个结果也并不意外。实验总结010020030040050060070005101520运算时间log2(N)图4myfft和fft函数执行时间的比较myfftfft函数实验2FFT算法的实现实验报告9基2-FFT算法和直接DFT算法相比，有明显的优势（从时间复杂度和空间复杂度上来说），使得用计算机进行频谱分析实用化。这次试验也很好地证明了这一点。matlab语言是一种解释性语言，所以matlab程序的执行速度有时候并不理想。采用以下措施可以优化matlab程序：1.尽量用向量化的运算来代替循环操作。2.在必须采用多重循环的情况下，如果两个循环执行的次数不同，应该使用外循环执行循环次数更少的，内层执行循环次数更多的。3.如果要定义大矩阵，应该首先用matlab的函数如zeros()为其申请空间。4.优先使用matlab的内在函数，如fft()，因为内在函数是由更底层的C语言编写的，并且进行了很好地优化，其执行速度肯定更快。（自己写的myfft程序和fft函数的性能的比较也很好地说明了这一点）。为了提高myfft程序的性能，我在优化的时候，尽量不采用for循环，而是改用了向量的运算，（比如在对序列进行反序存放时，本来用的是for循环，后来改成了向量运算）。同时，尽量避免无用的操作，做到程序的精简化。同时，尽量采用了matlab内在的函数。这次试验使我对FFT算法有了更加深刻的理解，同时，我也对如何优化matlab程序和怎样用matlab测试程序的性能有了较多的了解。可谓获益匪浅！