思考题源代码：
subplot(2,1,1);
k=0:9;
xn=[1 1 1 1 1 1 1 1 1 1]; stem(k,xn);
subplot(2,1,2);
yn=fft(xn,64);
stem(abs(yn));
axis([-4*pi,4*pi,0,15]);
运行结果图：
第二篇：fft算法实验报告
师：
生：
号： 算法的实现 卫 国 张 园 园 PB12207051 实验名称：FFT 老 学 学
实验2 FFT算法的实现 实验报告
实验目的：
1. 加深对FFT变换的理解。
2. 掌握FFT算法和其程序的编写。
3. 掌握算法性能测评的方法。
实验原理：
在各种信号序列中，有限长序列在数字信号处理中占有重要的地位。无限长的序列往往也可以用有限长的序列来逼近。对于有限长的序列我们可以用离散傅里叶变换（DFT），之一变化可以很好地反应序列的频域特性，并且容易利用快速算法在计算机上实现。当序列的长度为N时：定义离散傅里叶变换为：
kn X(k)?DFT[x(n)]??x(n)WN
n?0N?1
其中WN?e?j2?N。
它的反变换定义为：
1x(n)?IDFT[X(k)]?N?X(k)W
k?0N?1?knN。
但若直接计算DFT变换，运算的复杂度和序列长度的平方成正比，所以没法用计算机实现大规模数据的处理。为此，FFT算法应运而生，FFT是一种为了减少DFT算法的复杂度而出现的快速算法。它对变换式（1）进行一次次的分解，使其成为若干小点数的DFT的组合，从而减小运算量。常用的FFT是以2为基数，其长度N=2M，算法的流程图可以用蝶形算法来表示，以8点的基2-FFT算法为例，其蝶形图为：
图1 8点序列基2—FFT算法蝶形图
当需要进行变换的序列长度不是2的整数次方时，可以用末尾补零的方法，使其长度延长至2的整数次方。IFFT一般可以通过FFT程序完成。比较式（1）和（2），只要对X(k)取共轭，进行FFT运算，然后再取共轭，并乘以因子1/N，就可以完成IFFT。
实验内容和结果分析
2
实验2 FFT算法的实现 实验报告
1．程序如下：
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. for n=1:ml; ％n表示在做第n层蝶形运算；
10. for jk=1:M/(2^n); ％jk 表示第n层蝶形运算的个数；
11. for m=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. end
2. 验证程序的有效性
选取序列为：x(n)?nsinn ，n?1；为了能清晰的看出结果，我们用64个点做测试，用自己的程序做FFT，得到的幅频特性图为： 2
3
实验2 FFT算法的实现 实验报告
幅
度
图2 用自己的fft程序得到的64点序列的幅频图
和matlab中的FFT函数进行比较的结果为（用MATLAB中FFT函数的结果和自己
程序的结果做差再取绝对值）：
幅度
图2 自己的程序和matlab的fft函数的比较结果（N=64）
?11 由图2可知，两个结果差距在10
做更长序列的FFT，结果依然有效。 量级，故自己的FFT程序是有效的。也可以
4
实验2 FFT算法的实现 实验报告
3. 对所编写的FFT程序进行性能评估。
评价一个算法的性能，主要从时间复杂度和空间复杂度两方面进行评价。随着硬件设备的发展，空间复杂度对算法性能的影响越来越小，算法的时间复杂度变得更加重要。而时间复杂度主要依赖于算法的运算次数，众所周知，基2-FFT算法的复数乘法次数为1Nlog2N。所以，从算法的时间复杂度上来看，基2-FFT算法肯定优于直2
接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次，比较平均时间的长短，测试序列为： x(n)?nsinn ，n?1。
测试程序如下：
clear all;
tic;
for f=1:100;
clear all;
myfft(2048);
clear all;
5
2
实验2 FFT算法的实现 实验报告
end; toc;
因为考虑到matlab在第二次执行myfft时matlab已经将所需要的函数
编译到内存已经为myfft函数中的变量申请到了空间，所以程序执行时间会大大降低，但是并不合理，所以用了两个 clear all 命令。同时考虑到for循环也要消耗一定的时间，但是当执行myfft函数的次数比较多时，这一部分时间可以忽略不计，而且不管是对myfft还是dft函数for循环增加的运行时间是一样的，故可以这样进行测试。另外，程序的运行时间和计算机的性能也有很大关系，所以，这里的数据只是我在自己的笔记本上跑的结果，和别人的结果没有直接的可比性。
表1 myfft和直接做dft程序运行时间表
注：myfft为运行是基于fft算法的程序，mydft是基于直接dft算法的程序；画斜线的表示matlab出现内存空间不够，没法运行。也可以此说明计算的复杂度。
画出的曲线为：
6
实验2 FFT算法的实现 实验报告
myfft
mydft
程序执行时间
024681012141618
log2(N)
图3 myfft和mydft程序执行时间的比较
当序列的长度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次的时间。
7
实验2 FFT算法的实现 实验报告
6
7
8
9
10
11
12
13
3.187469 3.278499 3.604092 4.278500 5.715648 8.988992 15.86307
9
30.913983
0.248839 0.249915 0.247000 0.247972 0.279895 0.270566 0.303748
0.293595
表2 myfft和matlab的fft函数运算时间表
画出曲线来：
700
myfft
600
fft函数
50040030020010000
5
10
15
20
运算时间
log2(N)
图4 myfft和fft函数执行时间的比较
由此可以看出，自己编写的myfft函数性能明显比matlab中的fft函数差：对于特定长度的序列后者的运算时间比前者短得多，而且，随着N增大，myfft函数的运算时间的增长速度也比fft函数快得多。因为matlab中的fft函数是用更底层的C语言写的，并且进行了非常好的优化，所以这个结果也并不意外。
实验总结
8
实验2 FFT算法的实现 实验报告
基2-FFT算法和直接DFT算法相比，有明显的优势（从时间复杂度和空间复杂度上来说），使得用计算机进行频谱分析实用化。这次试验也很好地证明了这一点。
matlab语言是一种解释性语言，所以matlab程序的执行速度有时候并不理想。采用以下措施可以优化matlab程序：
1. 尽量用向量化的运算来代替循环操作。
2. 在必须采用多重循环的情况下，如果两个循环执行的次数不同，应该使用外循环执行
循环次数更少的，内层执行循环次数更多的。
3. 如果要定义大矩阵，应该首先用matlab的函数如zeros()为其申请空间。
4. 优先使用matlab的内在函数，如fft()，因为内在函数是由更底层的C语言编写的，并
且进行了很好地优化，其执行速度肯定更快。（自己写的myfft程序和fft函数的性能的比较也很好地说明了这一点）。
为了提高myfft程序的性能，我在优化的时候，尽量不采用for循环，而是改用了向量的运算，（比如在对序列进行反序存放时，本来用的是for循环，后来改成了向量运算）。同时，尽量避免无用的操作，做到程序的精简化。同时，尽量采用了matlab内在的函数。 这次试验使我对FFT算法有了更加深刻的理解，同时，我也对如何优化matlab程序和怎样用matlab测试程序的性能有了较多的了解。可谓获益匪浅！
9