蝶形算法
各偏旁-商业包装
2023年2月20日发(作者：建军大业读后感)FFT算法实现与分析MATLAB
FFT算法实现
厚
2.1实验⽬的
I、加深对快速傅⾥叶变换的理解。
II、掌握FFT算法及其程序的编写。
III、掌握算法性能评测的⽅法。
IV、熟悉MatLab编程。
2.2实验原理
⼀个连续信号Xa(t)的频谱可以⽤它的傅⾥叶变换表⽰为：
如果对该信号进⾏理想采样，可以得到采样序列：
同样可以对该序列进⾏z变换，其中T为采样周期：
当z=e^jω的时候，我们就得到了序列的傅⾥叶变换：
其中w称为数字频率，它和模拟域频域的关系为：
其中fs是采样频率。上式说明数字频率是模拟频率对采样率fs的归⼀化。同模拟域的情况相似，数字频率代表了序列值变化的速率，⽽序
列的傅⽴叶变换称为序列的频谱。序列的傅⽴叶变换和对应的采样信号频谱具有下式的对应关系。
即序列的频谱是采样信号频谱的周期延拓。从上式可以看出，只要分析采样序列的频谱，就可以得到相应的连续信号的频谱。
在各种信号序列中，有限长序列在数字信号处理中占有很重要的地位。⽆限长的序列也往往可以⽤有限长序列来逼近。对于有限长的序列我
们可以使⽤离散傅⽴叶（DFT），这⼀变换可以很好地反应序列的频域特性，并且容易利⽤快速算法在计算机上实现当序列的长度是N
时，我们定义离散傅⽴叶变换为：
其中W_N=e^(-2Πj/N)，它的反变换定义为：
若直接计算DFT变换，整个DFT运算需要4N^2次实数相乘和2N(2N-1)次实数相加。
所以直接计算乘法次数与加法次数都和N^2成正⽐。例如N=10点的DFT，需要100次复数相乘，⽽N=1024时则需要1,048,576即⼀百
多万次复数乘法运算。这对于实时性要求很强的信号处理来说，必将对计算速度有⼗分严苛的要求。为此，FFT作为对DFT的改进诞⽣。
快速傅⾥叶变换FFT并不是与DFT不相同的另⼀种变换，⽽是在DFT计算规律上建⽴的⼀种减少运算次数的快速算法。常⽤FFT是以基-2
的，长度N=2^M。运算效率⾼，程序简单，使⽤⽅便。本实验就使⽤以2为基实现FFT。算法流程图可以⽤蝶形算法来表⽰，以8点的基2-
FFT算法为例：
每个蝶形运算为：
可以看到，每个蝶形运算都可原位运算。
当需要进⾏变换的序列长度不是2的整数次⽅的时候，为了使⽤以2为基的FFT，可以⽤末尾补零的⽅法，使其长度延长⾄2的整数次⽅。IFFT⼀般可以通过
FFT程序来完成，只要对X(k)取共轭，进⾏FFT运算，然后再取共轭，并乘以因⼦1/N，就可以完成IFFT。
2.3实验内容
1、算法实现
以对⾼斯序列进⾏FFT代码为例：
①、使⽤bitrevorder()函数对待变换信号顺序进⾏调整，存⼊x1中。例如M=8时
原顺序：000(0)，001(1)，010(2)，011(3)，100(4)，101(5)，110(6)，111(7)
对⼆进制翻转之后为：
新顺序：000(0)，100(4)，010(2)，110(6)，001(1)，101(5)，011(3)，111(7)
对⽐实验原理中M=8的FFT输⼊序列发现两者顺序⼀致。
②、n=1:m1表⽰⼀共有m1层运算，⽐如M=8时有3层。
k=1:M/(2^n)表⽰第n层分为k部分，⽐如M=8的第⼀层分为4个单独蝶形运算，第⼆层分为2个两两蝶形运算，第三部分为1个四四蝶形运
算。
m表⽰第k部分的第m个蝶形运算。
③、因为蝶形运算是原位运算，就不需要另外开辟空间，计算结果仍然存在原位置。
④、绘出编写的FFT计算结果与MATLAB的FFT计算结果，以及两者的差。
2、选取实验1中的典型信号序列验证算法的有效性
I、三⾓波
II、反三⾓波
III、⾼斯序列
IV、衰减正弦序列
V、单位脉冲序列
VI、矩形窗序列
VII、理想采样序列
注意每个序列⾃⼰编写的FFT计算结果和MATLAB的FFT计算结果，两者相差数量级
在10(-14)。说明编写的FFT算法正确性没有问题。
3、对所编制的FFT算法进⾏性能评估
算法的评估⾸先是其正确性，是否能够完成预期功能决定了该算法是否有意义，
上⼀部分已经通过典型信号序列验证了编写的FFT算法的有效性。
这⾥接下来主要从时间复杂度和空间复杂度两⽅⾯来进⾏评价。空间复杂度是指该算法运⾏过程需要占⽤多少内存空间，随着半导体产业的
发展，内存空间变得越来越廉价，空间复杂度对算法性能的影响也越来越⼩。⼈们往往根据时间复杂度来评价⼀个算法的性能。⽽时间复杂
度主要依赖于算法的计算次数。已知基2-FFT算法的复数乘法次数为1/2〖Nlog〗_2N。相⽐于加法，乘法在运算中要复杂得多，占⽤资
源也更多，所以时间复杂度主要依赖乘法次数。从理论复杂度来看，FFT显然⽐DFT的N^2更优。在MARLAB中查看程序运算时间有以下
办法：
①、tic和toc命令组合
tic；
operation；
toc；
tic⽤来保存当前时间，也就是operation开始运⾏时间，toc⽤来记录程序完成时间。MATLAB会⾃动计算时间差并显⽰（以秒为单位但能
精确到⼩数点后6位，即us）。
②、etime(t1,t2)和clock配合
t1=clock；
operation；
t2=clock；
etime(t1,t2);
通过调⽤windows系统时钟进⾏时间差计算得到运⾏时间，t1和t2之间的时间差。
③cputime函数
t1=cputime；
operation；
t2=cputime-t1；
使⽤cpu主频计算运⾏时间差，得到程序运⾏时间。
(-16)到10
tic/toc是MATLAB⾃⾝计数器，精度要⾼于后两者。⽽且，如②调⽤系统时钟计算时间差，这段时间中系统可能还有其他后台程序。
MATLAB官⽅推荐使⽤tic/toc组合，Whentimingthedurationofanevent,usetheticandtocfunctionsinsteadofclockor
etime.所以接下来的评估程序运⾏时间，本实验使⽤tic/toc命令。此外，程序运⾏时间和计算机本⾝的计算能⼒有着直接关系，以下数据都
是在个⼈笔记本电脑测得。由于电脑属于商务本，计算能⼒很有限，时间相对会稍长⼀些。
以上主要说明了FFT算法评估⽅法和侧重点，具体评估数据在下⾯的dofft与DFT、dofft与MATLAB-FFT的性能⽐较中给出。
2.4实验报告要求
1、总结⾃⼰实现的FFT算法时采⽤了哪些⽅法减少了运算量。
1）使⽤matlab的bitrevorder()函数实现⼆进制翻转，由于matlab的函数是基于更底层的的c语⾔编写的，有很专业的优化，执⾏速度肯定
更快。
2）尽量使⽤⼩循环套⼤循环，因为执⾏的跳转原因，⼤循环单次执⾏时间优于⼩循环。
3）利⽤蝶形运算的原位性，使⽤同⼀个地址空间存储变换前序列和变换后序列。
4）每相邻计算的蝶形运算数据在地址上尽量连续，减少寻址时间。
2、给出⾃⼰的FFT算法与实验1中的DFT算法性能⽐较结果。
为避免运算时间过短不利于记录，使⽤20次循环。dofft程序见2.3，其余程序如下
DFT程序：
dofft测试程序：
DFT测试程序：
运⾏时间记录如下：
N
算法83225651210242048
dofft1.5241021.5636021.8209891.9846342.8144333.088558
DFT0.3675550.3759530.9450364.49177022.746014107.771205
作图：
测试序列为理想采样序列。为避免循环运⾏时，MATLAB程序在前⼀循环已在内存中开辟空间和留有数据，测试程序中使⽤了clearall命令
来清除内存中的数据。这样测得的时间更加准确。从记录的运⾏时间中可以看到，当N⽐较⼩的时候，DFT运⾏时间⽐dofft时间更⼩，这是
因为DFT算法使⽤的是向量运算，⽽dofft中使⽤了循环。MATLAB本⾝对于向量计算的速度快于循环的计算速度。所以如果进⼀步优化
dofft算法，可以改⽤向量运算，避免循环。当N趋于更⼤时,DFT运⾏时间迅速上升，很快和dofft运⾏时间不在⼀个数量级。这和DFT、
FFT两算法的理论时间复杂度⼀致。
3、给出⾃⼰的FFT算法和MATLAB中fft算法性能⽐较结果。
采⽤与2中相同的测试⽅法，同样使⽤20次循环。
fft程序：
fft测试程序：
运⾏时间记录如下：
N
算法5121192
dofft1.9846342.8144333.0885583.5793885.438975
FFT0.3490010.3694330.3656320.4034130.334651
N
算法55364
dofft13.30710418.96164928.58572761.441558125.271445
FFT0.3502250.4315610.4307170.4450770.530932
作图：
⾃⼰编写的dofft在进⾏变换长度的横坐标下近似线性增长。⽽MATLAB本⾝的FFT基本上随着N的增⼤，运⾏时间基本上没有变化。显然
dofft性能⽐fft性能差。想必MATLAB中的fft函数进⾏了更多技巧和优化。
4、总结实验中根据实验现象得到的其他结论。
①实验中测运⾏时间，当前后两个程序运⾏时间相差不⼤时，可能时间⼤⼩有波动。⽐如MATLAB中的fft函数在做2048点计算时所⽤时
间⽐1024点计算时间稍⼩，这与MATLAB当前占CPU和电脑状态相关。也会出现同⼀个程序在不同时刻测运⾏时间⼤⼩稍有差异，多测
⼏次时间取平均时间长。
②DFT在N较⼩时运⾏时间⼩于dofft，说明MATLAB更优于计算向量。所以编写MATLAB程序时应尽量把for循环改为矩阵运算，尽量向
量化。
③同样的算法，基于不同的编程，在运⾏速度上仍然会有很⼤的不同，⽐如在MATLAB中使⽤for循环编写，MATLAB本⾝的FFT，和⽤C
语⾔编写的FFT在运⾏速度上都会有很⼤不同。所以提⾼编程技巧，了解程序具体流⽔线、地址开辟、循环嵌套等等如何对优化程序有很⼤
意义。
④MATLAB带有众多功能强⼤，⾼优化⽔平的函数，在编写程序时，尽可能查询MATLAB有⽆相关函数，充分利⽤，以提⾼编写的程序的
执⾏效率，⽐如dofft中的bitreorder。
⑤测量运⾏时间的时候要把绘图的函数注释掉，否者会占⽤程序⼤量运⾏时间。