FFT原理

FFT原理

FFT（快速傅立叶变换）是离散傅立叶变换（DFT）的高效算法，其核心原理是通过分治策略将计算复杂度从DFT的O(N2)降低至O(N log?N)。以下是其原理的详细阐述：

DFT的数学定义为：$$ X(k) = sum_{n=0}^{N-1} x(n) cdot W_N^{kn} quad (k=0,1,dots,N-1) $$其中，旋转因子 $ W_N = e^{-j2pi/N} $，具有周期性和对称性。直接计算DFT需N2次复数乘法和N(N-1)次复数加法，当N较大时（如N=1024），计算量达百万级，难以实时处理。

FFT通过以下步骤优化计算：

分解：将N点DFT拆分为两个N/2点DFT。

偶数点序列 $ x(2r) $ 和奇数点序列 $ x(2r+1) $ 分别计算DFT，得到 $ X_{text{even}}(k) $ 和 $ X_{text{odd}}(k) $。

利用旋转因子的周期性（$ W_N^{k+N/2} = -W_N^k $），合并结果：$$ X(k) = X_{text{even}}(k) + W_N^k X_{text{odd}}(k) $$$$ X(k+N/2) = X_{text{even}}(k) - W_N^k X_{text{odd}}(k) $$

递归：对N/2点DFT重复分解，直至2点DFT（基2-FFT）。

2点DFT仅需1次乘法和2次加法，计算量极小。

每次分解使计算量减半，总复杂度降至O(N log?N)。

旋转因子的性质：

周期性：$ W_N^{k+N} = W_N^k $

对称性：$ W_N^{N/2+k} = -W_N^k $

可约性：$ W_{mN}^{mk} = W_N^k $这些性质允许FFT通过合并同类项减少重复计算。

复数运算优化：

复数乘法可通过三角函数展开为实部与虚部的组合，但FFT利用旋转因子的对称性避免冗余计算。

例如，计算 $ W_N^k cdot X_{text{odd}}(k) $ 时，可复用前一步的中间结果。

FFT的结果为频域的复数序列，包含幅度和相位信息：

FFT点数N的选择需权衡以下因素：

频率分辨率：

分辨率 $ Delta f = frac{f_s}{N} $，其中 $ f_s $ 为采样率。

N越大，分辨率越高，但计算量增加。例如，分析50Hz信号需 $ N geq frac{f_s}{50} $。

频谱泄漏：

若信号频率非FFT频点的整数倍，能量会扩散至相邻频点（泄漏）。

解决方法：增加N或使用窗函数（如汉宁窗）抑制泄漏。

计算效率：

基2-FFT要求N为2的幂次（如256、1024），非2的幂次时需补零至最近幂次，但可能引入虚假频率成分。

FFT通过分治策略将DFT的复杂度从O(N2)降至O(N log?N)，其核心是利用旋转因子的周期性和对称性递归分解问题。输出结果为复数频谱，需通过模值和相位解析信号特征。选择FFT点数时需平衡分辨率、泄漏和计算效率，实际应用中需根据信号特性优化参数。