fft快速傅里叶变换

《fft快速傅里叶变换》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、快速傅里叶变换[编辑]维基百科，自由的百科全书跳转至：导航、搜索傅里叶变换Z变换傅里叶级数傅里叶变换离散傅里叶级数离散时间傅里叶变换离散傅里叶变换快速傅里叶变换分数傅里叶变换短时距傅立叶变换小波变换离散小波变换连续小波变换快速傅里叶变换（英语：FastFourierTransform,FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。本条目只描述各种快速算法。对于复数序列，离散傅里叶变换公式为：直接变换的计算复杂度是（参见大O符号）。快速傅里叶变换可以计算出与直接计算相同的

2、结果，但只需要的计算复杂度。通常，快速算法要求n能被因数分解，但不是所有的快速傅里叶变换都要求n是合数，对于所有的整数n，都存在复杂度为的快速算法。除了指数的符号相反、并多了一个1/n的因子，离散傅里叶变换的正变换与逆变换具有相同的形式。因此所有的离散傅里叶变换的快速算法同时适用于正逆变换。目录 [隐藏] ·1一般的简化理论·2快速傅里叶变换乘法量的计算·3Cooley-Tukey算法o3.1设计思想·4其他算法·5实数或对称资料专用的算法·6复杂度以及运算量的极限·7参考资料·8参阅一般的简化理论[编辑]假设一个M*NSub-rectangularmatrixS可分解成列向

3、量以及行向量相乘：若有个相异的non-trivialvalues(where)有个相异的non-trivialvalues则S共需要个乘法。Step1：Step2：简化理论的变型：也是一个M*N的矩阵。若有个值不等于0，则的乘法量上限为。快速傅里叶变换乘法量的计算[编辑]假设，其中彼此互质点DFT的乘法量为，则点DFT的乘法量为：假设，P是一个质数。若点的DFT需要的乘法量为且当中()有个值不为及的倍数，有个值为及的倍数，但不为的倍数，则N点DFT的乘法量为：Cooley-Tukey算法[编辑]主条目：Cooley-Tukey快速傅里叶变换算法Cooley-Tukey算法是最

4、常见的FFT算法。这一方法以分治法为策略递归地将长度为的DFT分解为长度分别为和的两个较短序列的DFT，以及与个旋转因子的复数乘法。这种方法以及FFT的基本思路在1965年J.W.Cooley和J.W.Tukey合作发表AnalgorithmforthemachinecalculationofcomplexFourierseries之后开始为人所知。但后来发现，实际上这两位作者只是重新发明了高斯在1805年就已经提出的算法(此算法在历史上数次以各种形式被再次提出)。Cooley-Tukey算法最有名的应用，是将序列长为N的DFT分割为两个长为N/2的子序列的DFT，因此这一应

5、用只适用于序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和Cooley与Tukey都指出的那样，Cooley-Tukey算法也可以用于序列长度N为任意因数分解形式的DFT，即混合基FFT，而且还可以应用于其他诸如分裂基FFT等变种。尽管Cooley-Tukey算法的基本思路是采用递归的方法进行计算，大多数传统的算法实现都将显式的递归算法改写为非递归的形式。另外，因为Cooley-Tukey算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。设计思想[编辑]下面，我们用N次单位根来表示。的性质：1.周期性，具有周期，即2.对称性

6、：。3.若是的约数，为了简单起见，我们下面设待变换序列长度。根据上面单位根的对称性，求级数时，可以将求和区间分为两部分：和是两个分别关于序列奇数号和偶数号序列N/2点变换。由此式只能计算出的前N/2个点，对于后N/2个点，注意和都是周期为N/2的函数，由单位根的对称性，于是有以下变换公式：··。这样，一个N点变换就分解成了两个N/2点变换。照这样可继续分解下去。这就是库利-图基快速傅里叶变换算法的基本原理。根据主定理不难分析出此时算法的时间复杂度为其他算法[编辑]在Cooley-Tukey算法之外还有其他DFT的快速算法。对于长度N=N1N2且N_1与N_2互质的序列，可以采

7、用基于中国剩余定理的互质因子算法将N长序列的DFT分解为两个子序列的DFT。与Cooley-Tukey算法不同的是，互质因子算法不需要旋转因子。Rader-Brenner算法是类似于Cooley-Tukey算法，但是采用的旋转因子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。这方法之后被split-radixvariantofCooley-Tukey所取代，与Rader-Brenner算法相比，有一样多的乘法量，却有较少的加法量，且不牺牲数值的准确性。Bruun以及QFT算法是不断的