快速傅里叶变换 (FFT)

快速傅里叶变换 (FFT)

快速傅里叶变换 (FFT)

快速傅里叶变换（Fast Fourier Transform, FFT）是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法，通过分治法将计算复杂度从 $O(N^2)$ 降低到 $O(N\log N)$，被IEEE评为20世纪十大算法之一。

历史

  • 1805年：高斯为插值小行星轨道提出分治思想，手稿以新拉丁文撰写，生前未发表
  • 1965年：Cooley和Tukey发表划时代论文，普及了FFT算法，其动机源于冷战核爆监测需求
  • 现代：FFTW、cuFFT等软件库持续优化实现

核心原理

  • 分治法：将长度为N的序列拆分为两个长度为N/2的子序列，递归处理
  • 蝶形运算：通过交叉乘法和加法同时得到两个频率点的结果，大幅降低计算量
  • 位反转：原地计算中数据重排的巧妙技术，节省内存空间

性能对比

当N=1024时，传统DFT需要超过1,000,000次运算，而FFT仅需约10,000次运算。

关键应用

  • 通信：OFDM（4G/5G/Wi-Fi）的物理层基础
  • 多媒体压缩：DCT（JPEG/MP3）的数学基础
  • 大整数乘法：Schönhage-Strassen算法
  • 科学计算：谱方法、湍流模拟、分子动力学
  • 工业检测：超声检测、振动分析、模态分析
  • 地质勘探：地震波反演、核爆监测

现代实现

  • FFTW：MIT开发的自适应FFT库
  • Intel MKL：针对Intel处理器深度优化的实现
  • cuFFT：NVIDIA GPU加速库
  • FPGA/ASIC：硬件级流水线实现
  • 量子计算：量子傅里叶变换（QFT）是Shor算法的基础
分享到