steve

FFT 与 DFT 原理及算法解析

离散傅里叶变换（DFT）将时域信号转换为频域表示，直接计算复杂度为 O(N^2)。快速傅里叶变换（FFT）利用旋转因子对称性与周期性降低至 O(N log N)。主要算法包括基 -2 按时间/频率抽取、基 -4 及分裂基 FFT。通过蝶形运算实现分治策略，输入输出顺序涉及位反转。DFT 结果具有共轭对称性，有效信息冗余。IDFT 用于恢复时域信号。