快速傅里叶变换 - 维基百科,自由的百科全书.pdf

2015/11/19 快速傅里叶变换 ­ 维基百科，自由的百科全书 快速傅里叶变换 维基百科，自由的百科全书 快速傅里叶变换 （英语：Fast Fourier Transform, FFT），是离散傅里叶变换的快速算法， 也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算 大整数乘法、求解偏微分方程等等。本条 目只描述各种快速算法。 对于复数串行 ，离散傅里叶变换公式为： 直接变换的计算复杂度是 （参见大O符号）。快速傅里叶变换可以计算出与直接计算相同 的结果，但只需要 的计算复杂度。通常，快速算法要求n能被因数分解，但不是所有 的快速傅里叶变换都要求n是合数，对于所有的整数n，都存在复杂度为 的快速算 法。 除了指数的符号相反、并多了一个1/n的因子，离散傅里叶变换的正变换与逆变换具有相同的形 式。因此所有的离散傅里叶变换的快速算法同时适用于正逆变换。 目录 1 一般的简化理论 2 快速傅里叶变换乘法量的计算 3 库利-图基算法 3.1 设计思想 3.2 算法实现 3.3 算法复杂度 4 其他算法 5 实数或对称资料专用的算法 6 复杂度以及运算量的极限 7 参考资料 8 参阅 一般的简化理论 假设一个M*N型矩阵S可分解成列向量以及行向量相乘： /wiki/%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2 1/9 2015/11/19 快速傅里叶变换 ­ 维基百科，自由的百科全书 若 有 个相异的非平凡值 （ where ）　 有 个相异的非平凡值 则S共需要 个乘法。 Step 1： Step 2： 简化理论的变型： 也是一个M*N的矩阵。 若 有 个值不等于0，则 的乘法量上限为 。 快速傅里叶变换乘法量的计算 假设 ，其中 彼此互质 点DFT的乘法量为 ，则 点DFT的乘法量为： 假设 ，P是一个质数。 若 点的DFT需要的乘法量为 且 当中 （ ） /wiki/%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2 2/9 2015/11/19 快速傅里叶变换 ­ 维基百科，自由的百科全书 有 个值不为 及 的倍数， 有 个值为 及 的倍数，但不为 的倍数， 则N点DFT的乘法量为： 库利-图基算法 库利-图基算法是最常见的FFT算法。这一方法以分治法为策略递归地将长度为 的离 散傅里叶变换分解为长度为 的 个较短串行的离散傅里叶变换，以及与 个旋转因子的 复数乘法。 这种方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作发表An algorithm for the machine calculation of complex Fourier series之后开始为人所知。但后来发现，实际 上这两位作者只是重新发明了高斯在1805年就已经提出的算法 （此算法在历史上数次以各种形式 被再次提出）。 库利-图基算法最有名的应用，是将串行长为N 的DFT分割为两个长为N/2 的子串行的DFT，因此 这一应用只适用于串行长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和