快速傅里叶变换(Fast Fourier Transform,FFT)是一类高效计算离散傅里叶变换(DFT)及其逆变换的算法。它把有限长度序列从原始域转换为频域表示,原始域通常是时间域或空间域;逆变换则把频域数据还原到原始域。FFT并不是一种不同于DFT的新变换,而是利用DFT结构特征减少运算量的方法,因此其计算结果与直接依照DFT定义求值相同。
对于长度为N的复数序列,DFT需要计算N个频率输出,每个输出包含N项求和。直接计算通常需要O(N²)次运算,而FFT通过分解变换矩阵或递归拆分序列,把运算复杂度降至O(N log N)。当数据规模增加时,这种复杂度差异会明显影响计算时间。
最常见的FFT方法是库利-图基算法。它采用分治策略,把长度N=N₁N₂的DFT拆成多组较短的DFT,再通过旋转因子完成组合。基2 FFT适用于长度为2的幂的序列:算法先把输入按偶数编号与奇数编号分成两个长度为N/2的子序列,分别计算子序列变换,再利用N次单位根的周期性与对称性合并结果。
合并过程通常以“蝶形运算”表示。若偶数部分和奇数部分的变换结果分别为E(k)与O(k),旋转因子为WNk,则一组输出可写成E(k)+WNkO(k),与其相隔N/2的另一组输出则为E(k)−WNkO(k)。每次分解都会把问题规模减半,直至形成可直接处理的小型变换。N点基2 FFT共有log₂N层,每层处理N个数据点,因此形成O(N log N)的总体复杂度。
典型FFT实现由输入序列、旋转因子、蝶形运算单元、分级运算网络、数据重排和输出序列组成。迭代式基2实现常使用位反转排序:先以二进制标记输入位置,再将编号的位序倒置。例如,8点序列的重排次序为0、4、2、6、1、5、3、7,随后数据逐层进入蝶形网络,并在相应阶段乘以旋转因子。
库利-图基算法也可处理具有其他因数分解形式的序列,形成混合基或分裂基等变种。对于互质长度、质数长度或特定数据结构,还可采用互质因子算法、Rader算法、chirp-Z算法、Winograd算法及其他快速方法。纯实数输入的DFT结果具有共轭对称性,专用实现可利用这种对称关系减少不必要的运算与存储;偶对称或奇对称数据也可结合离散余弦变换或离散正弦变换处理。
FFT广泛用于工程、科学与数学计算,主要承担频谱分析和卷积运算。频谱分析利用它把时间或空间序列转换到频域,以观察不同频率成分;卷积运算则可借助DFT与逆变换在频域完成。FFT也可实现为管线式硬件处理器。单一路径延迟反馈架构以蝶形单元、移位暂存器或随机存取存储器保存中间结果,数据沿单一路径逐级处理;这种结构着重控制硬件与存储资源,但吞吐量低于多路径延迟交换架构。
FFT的基本思想早在1805年已由高斯推导,但直到1965年J. W. Cooley与J. W. Tukey发表用于机器计算复数傅里叶级数的算法后才广为人知。此后,FFT发展出针对不同序列长度、算术运算量、数值稳定性、存储需求及硬件结构的多种实现方式。