FFT 与 DFT 原理及算法解析

快速傅里叶变换 (FFT)

本节介绍几种高效计算离散傅里叶变换（DFT）的方法。鉴于 DFT 在各种数字信号处理应用（如线性滤波、相关分析和频谱分析）中的重要性，其高效计算问题已受到众多数学家、工程师和应用科学家的广泛关注。

从此处开始，符号 $X(k)$ 代表 $x(n)$ 的傅里叶系数。

DFT 定义与计算复杂度

DFT 的计算问题是：根据给定长度为 $N$ 的数据序列 ${x(n)}$，按照以下公式计算 $N$ 个复数值序列 ${X(k)}$：

$$ X(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn}, \quad 0 \leq k \leq N-1 $$

其中 $W_N = e^{-j2\pi/N}$。

通常，数据序列 $x(n)$ 也被假定为复数值。逆离散傅里叶变换（IDFT）为：

$$ x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) W_N^{-nk}, \quad 0 \leq n \leq N-1 $$

由于 DFT 和 IDFT 涉及基本相同的计算类型，对 DFT 高效计算算法的讨论同样适用于 IDFT。

对于每个 $k$ 值，直接计算 $X(k)$ 涉及 $N$ 次复数乘法（$4N$ 次实数乘法）和 $N-1$ 次复数加法。因此，计算 DFT 的全部 $N$ 个值需要 $N^2$ 次复数乘法和 $N^2-N$ 次复数加法。

直接计算 DFT 效率低下，主要是因为它没有利用相位因子 $W_N$ 的对称性和周期性：

• 对称性: $W_N^{k+N/2} = -W_N^k$
• 周期性: $W_N^{k+N} = W_N^k$

基 -2 FFT 算法

按时间抽取算法 (Decimation-in-Time)

考虑用分治法计算 $N=2^v$ 点 DFT。将 $N$ 点数据序列分成两个 $N/2$ 点数据序列 $f_1(n)$ 和 $f_2(n)$，分别对应 $x(n)$ 的偶数编号和奇数编号样本：

$$ f_1(n) = x(2n), \quad f_2(n) = x(2n+1), \quad n = 0, 1, \dots, \frac{N}{2}-1 $$

所得到的 FFT 算法称为按时间抽取算法（decimation-in-time algorithm）。

N 点 DFT 可表示为：

$$ X(k) = F_1(k) + W_N^k F_2(k), \quad k = 0, 1, \dots, N-1 $$

其中 $F_1(k)$ 和 $F_2(k)$ 分别是序列 $f_1(m)$ 和 $f_2(m)$ 的 $N/2$ 点 DFT。

利用周期性 $F_1(k+N/2) = F_1(k)$ 和 $W_N^{k+N/2} = -W_N^k$，方程可表示为：

$$ \begin{aligned} X(k) &= F_1(k) + W_N^k F_2(k), \quad k = 0, 1, \dots, \frac{N}{2}-1 \ X(k+\frac{N}{2}) &= F_1(k) - W_N^k F_2(k), \quad k = 0, 1, \dots, \frac{N}{2}-1 \end{aligned} $$

这第一步将乘法次数从 $N^2$ 减少到 $N^2/2 + N/2$。重复此过程直到序列缩减为单点序列，总复数乘法次数减少到 $(N/2)\log_2 N$，复数加法次数为 $N\log_2 N$。

图 TC.3.1 按时间抽取算法的第一步。

输入数据序列经过多次抽取后会发生混洗（shuffling），具有位反转顺序。

按频率抽取算法 (Decimation-in-Frequency)

另一种重要的基 -2 FFT 算法称为按频率抽取算法。首先将 DFT 公式分成两个求和式，一个涉及前 $N/2$ 个数据点，第二个涉及后 $N/2$ 个数据点。

将 $X(k)$ 分成偶数和奇数编号样本：

$$ \begin{aligned} X(2k) &= \sum_{n=0}^{N/2-1} [x(n) + x(n+\frac{N}{2})] W_{N/2}^{nk} \ X(2k+1) &= \sum_{n=0}^{N/2-1} [x(n) - x(n+\frac{N}{2})] W_N^n W_{N/2}^{nk} \end{aligned} $$