【STM32F407的DSP教程】第25章DSP变换运算-快速傅⾥叶变 换原理（FFT）
第25章 DSP变换运算-快速傅⾥叶变换原理（FFT）
在数字信号处理中常常需要⽤到离散傅⽴叶变换(DFT)，以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量⼤，耗时长，不利于计算机实时对信号进⾏处理。因此导致DFT被发现以来，在很长的⼀段时间内都不能被应⽤到实际⼯程项⽬中，直到⼀种快速的离散傅⽴叶计算⽅法——FFT被发现，离散是傅⽴叶变换才在实际的⼯程中得到⼴泛应⽤。需要强调的是，FFT并不是⼀种新的频域特征获取⽅式，⽽是DFT的⼀种快速实现算法。 特别声明：FFT原理的讲解来⾃⽹络和书籍。
25.1 FFT由来
25.3 直接计算DFT的问题及改进路径
化学战争25.3 改善DFT运算效率的基本途径
25.4 按时间抽选的基2-FFT算法
25.5 按频率抽选的基2-FFT算法
25.6 总结
25.1 初学者重要提⽰
1、为⼤家推荐西电的国家级精品课程信号与系统，含课堂视频，书籍和课堂PPT
2、⾮常好的DSP基础知识普及书籍：
25.2 FFT的由来
离散傅⾥叶变换（Discrete Fourier Transform，DFT）是数字信号处理最重要的基⽯之⼀，也是对信号进⾏分析处理时，最常⽤的⼯具之⼀。在200多年前，法国数学家、物理学家傅⾥叶提出以他的名字命名的傅⾥叶级数之后，⽤DFT这个⼯具来分析信号就已经被⼈们所知。
历史上最伟⼤的数学家之⼀，欧拉是第⼀个使⽤“函数”⼀词来描述包含各种参数的表达式，例如：y = f(x)。他是把微积分应⽤于物理学的先驱者之⼀，给出了⼀个⽤实变量函数表⽰傅⽴叶系数的⽅程，⽤三⾓级数来描述离散声⾳在媒介中传播，发现某些函数可以通过余弦函数之和来表达。但在很长时间内，这种分析⽅法并没有引起更多的重视，最主要的原因在于这种⽅法运算量⽐较⼤。直到1965年，
Cooley和Tukey在《计算机科学》发表著名的《机器计算傅⽴叶级数的⼀种算法》论⽂，FFT才开始⼤规模应⽤。
那个年代，有个肯尼迪总统科学咨询委员会，其中有项研究主题是对苏联核测试进⾏检测，Tukey就是其中⼀员。美国/苏联核测试提案的批准，主要取决于不实地访问核测试设施⽽做出检测⽅法。其中⼀个想法是，分析离海岸的地震情况，这种计算需要快速算法来计算DFT。其它应⽤是国家安全，如⽤声学探测远距离的核潜艇。所以在军事上，迫切需要⼀种快速的傅⽴叶变换算法，这也促进了FFT的正式提出。
FFT充分利⽤了DFT运算中的对称性和周期性，从⽽将DFT运算量从N2减少到。当N⽐较⼩时，FFT优势并不明显。但当N⼤于32开始，点数越⼤，FFT对运算量的改善越明显。⽐如当N为1024时，FFT的运算效率⽐DFT提⾼了100倍。在库利和图基提出的FFT算法中，其基本原理是先将⼀个N点时域序列的DFT分解为N个1点序列的DFT，然后将这样计算出来的N个1点序列DFT的结果进⾏组合，得到最初的N点时域序列的DFT值。实际上，这种基本的思想很早就由德国伟⼤的数学家⾼斯提出过，在某种情况下，天⽂学计算（也是现在FFT应⽤的领域之⼀）与等距观察的有限集中的⾏星轨道的内插值有关。由于当时计算都是靠⼿⼯，所以产⽣⼀种快速算法的迫切需要。⽽且，更少的计算量同时也代表着错误的机会更少，正确性更⾼。⾼斯发现，⼀个富⽒级数有宽度N=N1*N2，可以分成⼏个部分。计算N2⼦样本DFT的N1长度和N1⼦样本DFT的N2长度。只是由于当时尚⽋东风——计算机还没发明。
在20世纪60年代，伴随着计算机的发展和成熟，库利和图基的成果掀起了数字信号处理的⾰命，因⽽FFT发明者的桂冠才落在他们头上。
之后，桑德（G.Sand）-图基等快速算法相继出现，⼏经改进，很快形成了⼀套⾼效运算⽅法，这就是现在的快速傅⽴叶变换（FFT）。这种算法使DFT的运算效率提⾼1到2个数量级，为数字信号处理技术应⽤于各种信号的实时处理创造了良好的条件，⼤⼤推进了数学信号处理技术。1984年，法国的杜哈梅（P.Dohamel）和霍尔曼（H.Hollamann）提出的分裂基块快速算法，使运算效率进⼀步提⾼。
库利和图基的FFT算法的最基本运算为蝶形运算，每个蝶形运算包括两个输⼊点，因⽽也称为基-2算法。在这之后，⼜有⼀些新的算法，进⼀步提⾼了FFT的运算效率，⽐如基-4算法，分裂基算法等。这些新算法对FFT运算效率的提⾼⼀般在50%以内，远远不如FFT对DFT运算的提⾼幅度。从这个意义上说，FFT算法是⾥程碑式的。可以说，正是计算机技术的发展和FFT的出现，才使得数字信号处理迎来了⼀个崭新的时代。除了运算效率的⼤幅度提⾼外，FFT还⼤⼤降低了DFT运算带来的累计量化误差，这点常为⼈们所忽略。
25.3 直接计算DFT的问题及改进路径
25.3.1 问题的提出
设有限长序列x(n)，⾮零值长度为N，若对x(n)进⾏⼀次DFT运⾏，共需要多⼤的运算⼯作量。
25.3.2 DFT的运算量
DFT和IDFT的变换式：
下⾯以DFT为例说明计算量：
计算机运算时（编程实现）：
由上⾯的结算可得DFT的计算量如下：
复数乘法的计算量：(a+jb)(c+jd)=(ab-bd)+j(bc+ad)
下⾯通过两个实例来说明计算量：
例⼀：计算⼀个N点DFT，共需次复乘。以做⼀次复乘1 计算，若N=4096，所需时间为
例⼆：⽯油勘探，有24个通道的记录，每通道波形记录长度为5秒，若每秒抽样500点/秒。1. 每道总抽样点数：500*5 = 2500点。
2. 24道总抽样点数：24*2500=6万点。
3.
由于计算量⼤，且要求相当⼤的内存，难以实现实时处理，限制了DFT的应⽤，⼈们⼀直在寻求⼀种能提⾼DFT运算速度的⽅法。FFT便是Cooley和Tukey在1995年提出来的快速算法，它可以使运算速度提⾼⼏百倍，从⽽使数字信号处理成为⼀个新兴的应⽤学科。
25.4 改善DFT运算效率的基本途径
1、利⽤DFT运算的系数的固有对称性和周期性，改善DFT的运算效率。
1）对称性
2）周期性
3）可约性
陈庆炎2、将长序列DFT利⽤对称性和周期性分解为短序列DFT的思路
藻花香猪
因为DFT的运算量与N2成正⽐，如果⼀个⼤点数N的DFT能分解为若⼲⼩点数DFT的组合，则显然可以达到减少运算⼯作量的效果。
FFT算法的基本思想：
利⽤DFT系数的特性，合并DFT运算中的某些项。
把长序列DFTà短序列DFT，从⽽减少运算量。
FFT算法分类：
时间抽选法
DIT: Decimation-In-Time
频率抽选法
DIF: Decimation-In-Frequency
25.5 按时间抽选的基2-FFT算法
25.5.1 算法原理
设输⼊序列长度为N = 2M（M为正整数），将该序列按时间顺序的奇偶分解为越来越短的⼦序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。
其中基2表⽰：N = 2M，M为整数。若不满⾜这个条件，可以⼈为地加上若⼲零值（加零补长）使其达到N = 2,M。
小儿急性胰腺炎25.5.2 算法步骤
分组，变量置换
分组，变量置换
其中k = 0， 1，…. N/2 – 1。和只有N/2个点，以N/2为周期；⽽X(k)却有N个点，以N为周期。要⽤x1
睡美宁
(k)和x2(k)表达全部的X(k)值。还必须利⽤系数的周期特性。
有了上⾯的计算结果后，我们可以得到如下的蝶形运算流图符号：
关于这个蝶形运算流图符号说明如下：
1. 1个蝶形运算需要1次复乘，2次复加。
2. 左边两路为输⼊。李雯
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议