中财网matlab 拉普拉斯变换:快速傅里叶变换（FFT）（图）（转载）
来源：百度文库 编辑：中财网 时间：2024/04/30 03:25:47
上一回说到，为了节省电脑的计算时间，实现数字信号的实时处理，科学界千方百计减少离散傅里叶变换（DFT）的计算量。
1965年，库利（T.W.Cooley）和图基（J.W.Tukey）发表《一个复数傅立叶级数之机械计算算法》论文，首次提出了DFT运算的一种快速算法。此后科学界创造出了各种各样的DFT快速算法，逐渐发展完善形成了一整套行之有效的算法设计思想和方法。这就是快速傅立叶变换（Fast Fouier Transform），简称FFT。
可见所谓的快速傅里叶变换（FFT），并不是一种新的傅立叶分析理论，而是减少DFT计算量的算法设计思想和DFT各种快速算法的统称。
上一回我们知道了：DFT的计算量与点数N的平方成正比。DFT的变换因子（也叫旋转因子）：
（1）
具有周期性和对称性。也就是说：
1、以N为周期，即：
（2）
2、复共轭对称性（关于实轴对称），即：
（3）
3、中心对称性（关于原点对称），即：
（4）
FFT算法设计的基本思想，就是充分利用DFT的周期性和对称性，减少重复的计算量；并把N点长序列分成几个短序列，减少每个序列长度，可大大减少计算量。
实践中使用最多的FFT是“基2”算法。所谓“基2”，就是令DFT的点数N满足
（5）
FFT基2算法分为时域抽取法（Decimation In Time）和频域抽取法（Decimation In Frequency）两大类。本文重点介绍其中的时域抽取法快速傅里叶变换（DIT－FFT），算法设计思想要点如下：
1、把长度为N的时域序列x（n）按n的奇偶分为两组，变成两个序列，长度均为N/2。即
（6）
其中一个N/2点的DFT为
（7）
另一个N/2点的DFT为
（8）
2、不难推出原序列x（n）的N/2点DFT为
（9）
注意：上式仅是X（k）的前一半即N/2点运算，整个N点DFT结果还要加上后一半计算。如果老老实实计算后一半N/2点DFT，则并没有减少任何计算量。
但考虑可利用DFT及其变换因子的周期性和对称性，并利用前一半计算结果，后一半计算可表示为
（10）
这种“一分为二”的DFT算法叫做蝶形运算。可以看出其计算量为
（11）
和
（12）
与普通的DFT相比，计算量减少了一半！
3、同理，如果把式（6）表示的时间序列“二分为四”，长度均为N/4，同时把式（9）、（10）中的N/2点DFT分解为N/4点的DFT，反复使用蝶形运算的方法，即
（13）
后一半DFT为
（14）
而
（15）
后一半DFT为
（16）
计算量可在式（11）和（12）的基础上再减少一半!
4、依此类推，直到把长度为N的序列细分成N/2个2点序列为止，循环使用蝶形运算的方法，即把N点DFT分解成N/2个2点DFT运算。这样，计算量大大减少。由式（5）知
（17）
则复数乘法总次数从原来的N2减少为：
（18）
复数加法总次数从原来的约N2减少为：
（19）
假设N=1024，复数乘法从原来直接DFT计算的104万次，减少为5120次，计算速度提高约200倍！
综上所述，快速傅里叶变换（FFT）大大降低了数字信号处理中的运算量，它的价值在于节省了CPU的处理时间，使得更多更复杂的数字信号得以快速的处理，为实现信息的实时处理开辟了广阔的发展前景。因此，FFT是数字信号处理技术发展史上的一个重要里程碑。
作为其快速算法设计思想精髓的典型代表，基2算法的时域抽取法快速傅里叶变换（DIT－FFT）中的蝶形运算式（9）、（10）和（13）、（14）、（15）、（16）等公式，被英国科学期刊《物理世界》2004年10月号公布为读者选出的“科学界历来最伟大的公式”之一，并且名列第九。
同期推选出的“科学界历来最伟大的公式”还有许多，有兴趣的朋友们请查阅周法哲的博文《科学的皇后》栏目。
（作者：周法哲2009-8-9于广东）