FFT快速傅里叶变换.docx

快速傅里叶变换[ \o 编辑段落：0 编辑] 维基百科，自由的百科全书 跳转至： 导航、 搜索 傅里叶变换 \o Z变换 Z变换 \o 傅里叶级数 傅里叶级数 \o 傅里叶变换 傅里叶变换 \o 离散傅里叶级数 离散傅里叶级数 \o 离散时间傅里叶变换 离散时间傅里叶变换 \o 离散傅里叶变换 离散傅里叶变换 快速傅里叶变换 \o 分数傅里叶变换 分数傅里叶变换 \o 短时距傅里叶变换 短时距傅立叶变换 \o 小波变换 小波变换 \o 离散小波变换 离散小波变换 \o 连续小波变换 连续小波变换 快速傅里叶变换（ \o 英语 英语：Fast Fourier Transform, FFT），是 \o 离散傅里叶变换 离散傅里叶变换的快速 \o 算法 算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如 \o 数字信号处理 数字信号处理、计算 \o 大整数乘法（页面不存在） 大整数乘法、求解 \o 偏微分方程 偏微分方程等等。本条目只描述各种快速算法。 对于复数序列，离散傅里叶变换公式为： 直接变换的计算复杂度是（参见 \o 大O符号 大O符号）。快速傅里叶变换可以计算出与直接计算相同的结果，但只需要的计算复杂度。通常，快速算法要求n能被 \o 因数分解 因数分解，但不是所有的快速傅里叶变换都要求n是 \o 合数 合数，对于所有的整数n，都存在复杂度为的快速算法。 除了指数的符号相反、并多了一个1/n的因子，离散傅里叶变换的正变换与逆变换具有相同的形式。因此所有的离散傅里叶变换的快速算法同时适用于正逆变换。 目录 ?[ 隐藏]? 1 一般的简化理论 2 快速傅里叶变换乘法量的计算 3 Cooley-Tukey算法 3.1 设计思想 4 其他算法 5 实数或对称资料专用的算法 6 复杂度以及运算量的极限 7 参考资料 8 参阅 一般的简化理论[ \o 编辑段落：一般的简化理论 编辑] 假设一个M*N Sub-rectangular matrix S可分解成列向量以及行向量相乘： 若有个相异的non-trivial values( where ) 有个相异的non-trivial values 则S共需要个乘法。 Step 1： Step 2： 简化理论的变型： 也是一个M*N的矩阵。 若有个值不等于0，则的乘法量上限为。 快速傅里叶变换乘法量的计算[ \o 编辑段落：快速傅里叶变换乘法量的计算 编辑] 假设，其中彼此互质 点DFT的乘法量为，则点DFT的乘法量为： 假设，P是一个质数。 若点的DFT需要的乘法量为 且 当中 () 有个值不为及的倍数， 有个值为及的倍数，但不为的倍数， 则N点DFT的乘法量为： Cooley-Tukey算法[ \o 编辑段落：Cooley-Tukey算法 编辑] 主条目： \o Cooley-Tukey快速傅里叶变换算法 Cooley-Tukey快速傅里叶变换算法 Cooley-Tukey算法是最常见的FFT算法。这一方法以 \o 分治法 分治法为策略 \o 递归 递归地将长度为的 \o DFT DFT分解为长度分别为和的两个较短序列的DFT，以及与个旋转因子的复数乘法。 这种方法以及FFT的基本思路在 \o 1965年 1965年J. W. Cooley和J. W. Tukey合作发表An algorithm for the machine calculation of complex Fourier series之后开始为人所知。但后来发现，实际上这两位作者只是重新发明了 \o 高斯 高斯在 \o 1805年 1805年就已经提出的算法(此算法在历史上数次以各种形式被再次提出)。 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算法联合使用。 设计思想[ \o 编辑段落：设计思想 编辑] 下面，我们用N次单位根来表示。 的性质： 周期性，具有周期，即 对称性：。 若是的约数， 为了简单起见，我们下面设待变