快速傅里叶变换发展史,快速傅里叶变换发展史知乎

('快速傅立叶变换(FFT)个人日记2010-04-1612:24:48阅读163评论0字号：大中小订阅近十多年来数字信号处理技术同数字计算机、大规模集成电路等先进技术一样，有了突飞猛进的发展，日新月异，已经形成了一门具有强大生命力的技术科学。由于它本身具有一系列的优点，所以能有效地促进各工程技术领域的技术改造和学科发展，应用领域也更加广泛、深入，越来越受到人们的重视。在数字信号处理中，离散傅里叶变换(DiscreteFourierTransform,DFT)是常用的变换方法，它在各种数字信号处理系统中扮演着重要的角色。傅里叶变换已有一百多年的历史了，我们知道频域分析常常比时域分析更优越，不仅简单，且易于分析复杂信号。但用较精确的数字方法，即DFT进行谱分析，在FFT出现以前是不切实际的。这是因为DFT计算量太大。直到1965年出现了DFT]运算的一种快速方法以后，情况才发生了根本的变化。快速傅里叶变换〔FastFourierTransfonn,FFT〕并不是与离散傅里叶变换不同的另一种变换，而是为了减少DFT计算次数的一种快速有效的算法。当时Garwin在自己的研究中极需要一个计算傅立叶变换的快速方法，而L.W.Tukey正在写有关傅里叶变换的文章，Tukey概括地对Garwin介绍了一种方法，它实质上就是后来著名的Cooley-Tukey算法。在Garwin的迫切要求下，1963年，IBM公司的Cooley根据Tukey的想法编写了第一个FFT算法程序。在FFT算法中，Tukey主要利用了旋转因子的周期性和对称性。这两个性质使DFT运算中的某些项可以合并，使DFT运算尽量分解为更少点数的DFT运算。因为DFT的运算量与Pow(N,2)成比例，所以如果将一个大点数的DFT分解为若干个小点数的DFT的组合，将有效地减少运算量。Cooley在计算机上实现该算法时，为节省存储空间和减少寻址时间，采用了3维标号映射方法和在算法内部的循环结构，这些结构和技巧对后来的FFT算法研究及实现同样产生了很大影响。1965年，Cooley和Tukey在《计算数学》上发表了著名的论文，并立即引起了广泛注意。FFT算法将运算量从O(N2)减少为2O(NlogN)，运算时间减少1-2个数量级，从理论上解决了数字信号处理运算量大的问题，是数字信号处理发展史上的—块里程碑。以计算l024点的序列为例，FFT将计算时间缩短为原来的1/100，从而使数字信号处理从一个计算数学的分支变为一门应用科学，逐步走向实用技术.在Cooley-Tukey算法提出之后，Sande提出了按照频率抽取的FFT算法，它可以作为按照时间抽取的Cooley-Tukey算法的对偶形式。Bergland提出了采用高基数结构的算法，如基-4或基-8算法能够达到更高的计算效率。增大基数虽然可以减少计算量，但同时每个计算单元的结构也更复杂。基4算法比基2算法所需的乘法次数减少了约1/4。当采用高于4的基数r时，虽然总的乘法次数更少，但比基4算法中所需的复乘次数减少得并不显著，并且r点的DFT中将包含乘法运算，因此实际应用中多采用基4算法。Bergland对任意因子的FFT算法也作了研究，提出了统一的FFT方法，即任意因子的FFT运算都可以由r(r是基数)点的DFT运算和与旋转因子相乘的运算来实现，Cooley-Tukey算法和Sande-Tukey算法都可以看作统一的FFT算法的特例，即基数r都相同。对于输入数据是实数情况，可以将N点的DFT运算转换为N/2点的DFT运算，或者同时计算两个实序列的DFT，都可以采用FFT算法。从七十年代中期开始，基于素因子分解的FFT算法重新得到了重视。事实上，在Cooley-Tukey算法提出之前，Good就提出用点数互素的短点数DFT运算组合来实现长点数DFT运算，并且这种实现方式不会引入附加的乘旋转因子的运算。在素因子算法中利用了数论中的中国余数定理，将一维DFT运算映射为标准的多维DFT运算，而各素因子的DFT运算可以通过循环卷积算法完成。在素因子算法中，由于避免了乘旋转因子的运算，因此比Cooley-Tukey算法的乘法运算次数要少得多，而加法次数与之相当。基于素因子分解的另一种快速算法是由IBM公司的Winograd博士提出的，可以称为WFTA算法。WFTA算法有两个主要思想：一是用Rader提出的方法将小N点DFT转换为循环卷积，利用多项式理论使卷积计算具有尽可能少的乘法次数;二是将小N点DFT运算进行嵌套来完成大N点的DFT运算。WFTA算法比素因子算法的乘法次数更少，而加法次数差别不大。但WFTA算法也有一些突出的问题，如算法不能采用原位运算，需要占用较大的存储空间，更重要的是，随着变换点数N的不同，为使运算所需的加法次数最少，要求采用不同的运算次序，这导致运算过程的规则性较差，且控制过程复杂。在素因子算法和WFTA算法出现的初期，人们都寄以厚望。但后来发现它们在实际应用中并不理想，尽管在理论上仍是有意义的进展。因此FFT的研究重点重又回到了带有与旋转因子相乘运算的共因子算法上，主要的研究成果包括Rader和Brenner提出的余割因子算法，王中德提出的对称分解法,Matens提出的割园分解法，Vetlerli和Nussbaumer提出的DFTDCT算法等，其中最具代表性的是法国的Duhamel和Hollman提出的分裂基算法。分裂基算法的特点是将基-2分解与基-4分解揉和在一起，对序列的不同部分分别实施基-2算法和基-4算法。分裂基算法的运算结构与Cooley-Tukey算法相似，并且对于长度为N=2M的变换，这一算法已达到了DFT运算的最小运算量，所需要的乘法和加法次数为。乘法:a=N（M－3）+4加法:A=3N（M－1）+4对于具体实现而言，算法的运算量只是一个方面，而算法的复杂性、规则性、模块性往往是更重要的。Cooley-Tukey算法运算过程的每一级都是由r(r是基数)点的DFT和与旋转因子的相乘构成，算法规则，且具有良好的模块性，并且可以实现原位计算，对输入数1据以及旋转因子的抽取具有规律性。这一算法相对简单、规则，且所有的运算单元均相同，具有良好的模块性，易于实现。WFTA算法的地址产生可以根据其计算公式或嵌套形式的算法流图来实现，该算法不能采用原位运算，需要占用较大的存储空间。为使运算所需的加法次数最少，随着变换点数N的不同，要求采用不同的运算次序，这导致运算过程的规则性较差，控制过程复杂。同时各“小N”，也各不相同，导致运算单元的模块性不好。对于PFA算法，由于没有与旋转因子相乘的运算，因此避免了对旋转因子的求取，但由于指标映射造成的地址表达式中具有乘、加及求模运算，而这些运算又不易采用简单的方法实现，因此PFA算法的控制单元要比Cooley-Tukey算法的复杂。另一方面，由于PFA算法中短点数DFT的变换长度各不相同，要求每一个DFT都采用不同的运算单元。虽然不同长度的短点数DFT运算单元可以采用统一的通用结构，但这不仅降低硬件的效率，同时影响运算单元的速度。可见PFA算法同样存在着模块性不好的问题。对于分裂基算法，由于不同地址中的数据分别输入到2点、4点DFT运算模块以及与旋转因子相乘的单元进行运算，模块性同样较差，对于程序控制来说比较困难。综上所述，各种DFT的快速算法，都利用了nkNW的周期性和对称性，通过将一个大点数N的DFT分解为若干小点数的DFT的组合，来减少运算量。对于变换点数N为2的整数次幕的情况，分裂基算法的乘法次数比基-2、基-4算法更少。当N可以分解为若千个互素因子的乘积时，可以采用素因子算法，当素因子属于2,3,4,5,7,8,9,16等“小N”时，也可以采用Winograd“小N”算法。二者都是通过指标映射，将一维DFT转化为多维DFT，同时避免了与旋转因子相乘的运算，因此都有更少的运算次数。虽然Cooley-Tukey算法的运算次数要多于其它几种算法，但由于其算法规则，各运算单元相同，可实现原位计算，具有良好的模块性，因此更容易实现。（原创）快速傅里叶变换（FFT）（图）信息科学札记2009-08-1022:42:01阅读3822评论19字号：大中小订阅上一回说到，为了节省电脑的计算时间，实现数字信号的实时处理，科学界千方百计减少离散傅里叶变换（DFT）的计算量。1965年，库利（T.W.Cooley）和图基（J.W.Tukey）发表《一个复数傅立叶级数之机械计算算法》论文，首次提出了DFT运算的一种快速算法。此后科学界创造出了各种各样的DFT快速算法，逐渐发展完善形成了一整套行之有效的算法设计思想和方法。这就是快速傅立叶变换（FastFouierTransform），简称FFT。可见所谓的快速傅里叶变换（FFT），并不是一种新的傅立叶分析理论，而是减少DFT计算量的算法设计思想和DFT各种快速算法的统称。上一回我们知道了：DFT的计算量与点数N的平方成正比。DFT的变换因子（也叫旋转因子）：（1）具有周期性和对称性。也就是说：1、以N为周期，即：（2）2、复共轭对称性（关于实轴对称），即：（3）3、中心对称性（关于原点对称），即：2（4）FFT算法设计的基本思想，就是充分利用DFT的周期性和对称性，减少重复的计算量；并把N点长序列分成几个短序列，减少每个序列长度，可大大减少计算量。实践中使用最多的FFT是“基2”算法。所谓“基2”，就是令DFT的点数N满足（5）FFT基2算法分为时域抽取法（DecimationInTime）和频域抽取法（DecimationInFrequency）两大类。本文重点介绍其中的时域抽取法快速傅里叶变换（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及其变换因子的周期性和对称性，并利用前一半计算结果，后一半计算可表示为3（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）知4（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月号公布为读者选出的“科学界历来最伟大的公式”之一，并且名列第九。同期推选出的“科学界历来最伟大的公式”还有许多，有兴趣的朋友们请查阅周法哲的博文《科学的皇后》栏目。5',)