快速傅里叶变换

维基百科，自由的百科全书

這是與数学相關的小作品。你可以通过编辑或修订扩充其内容。

快速傅里叶变换（Fast Fourier Transform，FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。本条目只描述各种快速算法，对于离散傅里叶变换的性质和应用，请参见离散傅里叶变换。

对于复数序列 $x_{0},\ x_{1},\ ...,\ x_{n-1}$ ，离散傅里叶变换公式为：
$y_i=\sum_{k=0}^{n-1} x_k e^{-j {2 \pi \over n} ik } \qquad i = 0,\dots,n-1.$
直接变换的计算复杂度是 $\mathcal{O}(n^2)$ （参见大O符号）。快速傅里叶变换可以计算出与直接计算相同的结果，但只需要 $\mathcal{O}(n \log n)$ 的计算复杂度。通常，快速算法要求n能被因数分解，但不是所有的快速傅里叶变换都要求n是合数，对于所有的整数n，都存在复杂度为 $\mathcal{O}(n \log n)$ 的快速算法。

除了指数的符号相反、并多了一个1/n的因子，离散傅里叶变换的正变换与逆变换具有相同的形式。因此所有的离散傅里叶变换的快速算法同时适用于正逆变换。

[编辑] Cooley-Tukey算法

主条目：Cooley-Tukey快速傅里叶变换算法

Cooley-Tukey算法是最常见的FFT算法。这一方法以分治法为策略递归地将长度为 $N = N 1 N 2$ 的DFT分解为长度分别为 $N 1$ 和 $N 2$ 的两个较短序列的DFT，以及与 $\mathcal{O}(N)$ 个旋转因子的复数乘法。

这种方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作发表An algorithm for the machine calculation of complex Fourier series之后开始为人所知。但后来发现，实际上这两位作者只是重新发明了高斯在1805年就已经提出的算法。(and subsequently rediscovered several times in limited forms).

Cooley-Tukey算法最有名的应用，是将序列长为N 的DFT分割为两个长为N/2 的子序列的DFT，因此这一应用只适用于序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和Cooley与Tukey都指出的那样，Cooley-Tukey算法也可以用于序列长度N 为任意因数分解形式的DFT，即混合基FFT，而且还可以应用于其他诸如分裂基FFT等变种。尽管Cooley-Tukey算法的基本思路是采用递归的方法进行计算，大多数传统的算法实现都将显示的递归算法改写为非递归的形式。另外，因为Cooley-Tukey算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。

[编辑] 其他算法

在Cooley-Tukey算法之外还有其他DFT的快速算法。对于长度N = N1N2且N_1与N_2互质的序列，可以采用基于中国剩余定理的质因子FFT算法将N 长序列的DFT分解为两个子序列的DFT。与 Cooley-Tukey 算法不同的是，质因子算法不需要旋转因子。Rader-Brenner 算法是类似于 Cooley-Tukey 算法，但是采用的旋转因子都是纯虚数，以增加加法运算和降低了数值稳定性为代价减少了乘法运算。