快速傅里叶变换

快速傅里叶变换（FFT）是一种高效的计算离散傅里叶变换（DFT）和其逆变换的方法，由Cooley和Tukey在1965年提出。它极大地减少了计算复杂度，使得处理大规模数据的傅里叶变换成为可能。 在DFT中，对一个有限长的序列X[n]进行变换，得到频域表示X[k]，计算公式为： \[ X[k] = \sum_{n=0}^{N-1} x[n] \cdot W^{-kn} \] 其中，\( W = e^{-\frac{2\pi i}{N}} \) 是单位圆上的N次根复数，i是虚数单位。直接计算DFT的时间复杂度为O(N^2)，因为每个频谱点都需要对所有时间点进行乘法和加法运算。 FFT算法的基本思想是通过分解序列，利用DFT的对称性和周期性，将长序列的计算转化为短序列的计算，从而降低计算量。主要分为时间抽选法（DIT，Decimation-In-Time）和频率抽选法（DIF，Decimation-In-Frequency）。 对于基-2的FFT算法，当序列长度N是2的幂时，可以将序列分为两半，分别进行DFT计算，然后利用DFT的对称性组合结果。例如，对于长度为N的序列x[n]，可以拆分为x_even[n]（偶数下标元素）和x_odd[n]（奇数下标元素），它们的DFT分别为： \[ X_e[k] = \sum_{n=0}^{\frac{N}{2}-1} x_even[n] \cdot W^{-2kn} \] \[ X_o[k] = \sum_{n=0}^{\frac{N}{2}-1} x_odd[n] \cdot W^{-2kn-1} \] 利用DFT的周期性，可以将X[k]完全重构出来。这个过程可以通过递归的方式进行，每次将序列长度减半，直到序列长度为1，从而将计算复杂度降低到O(N log N)。 除了基-2的FFT，还有混合基、分裂基和CZT（Chirp-Z Transform）等变体，它们在特定情况下能够进一步优化计算效率或简化实现。例如，IFFT（Inverse FFT）是FFT的逆变换，用于将频域信号转换回时域信号。 FFT在信号处理、图像处理、通信、音频处理等领域有广泛应用，如滤波、频谱分析、卷积等。线性卷积使用FFT可以大大简化计算，通过将两个序列的零填充和两次FFT计算，然后进行适当的乘法和一次IFFT，即可完成线性卷积。 快速傅里叶变换是数字信号处理中的核心工具，它的高效性和灵活性使其在众多领域都扮演着重要角色。学习和理解FFT的原理、运算流程以及各种变体，对于深入理解信号处理和提高计算效率至关重要。