傅里叶变换：FFT 与 DFT 原理及算法详解

离散傅里叶变换（DFT）基础

连续时间傅里叶变换的定义为：

$$X(f) = \int_{-\infty}^{+\infty} x(t) e^{-j2\pi f t} dt$$

离散傅里叶变换（DFT）由连续傅里叶变换离散化得到，是数字信号处理中的核心工具。其定义为：

$$X(m) = \sum_{n=0}^{N-1} x(n) e^{-j\frac{2\pi m n}{N}}$$

式中：

$N$：时域离散信号的点数
$n$：时域离散信号序号，满足 $n \in {0, 1, \dots, N-1}$
$m$：频域信号序号，满足 $m \in {0, 1, \dots, N-1}$

DFT 输入为 $N$ 个时域离散样本，输出为 $N$ 个复数值频域样本。利用欧拉公式 $e^{-j\omega} = \cos\omega - j\sin\omega$，DFT 可展开为实部虚部形式：

$$X(m) = \sum_{n=0}^{N-1} x(n) \left[ \cos\left(\frac{2\pi m n}{N}\right) - j\sin\left(\frac{2\pi m n}{N}\right) \right]$$

实例分析

设时域连续信号为： $$x(t) = \sin(2\pi \cdot 1000 \cdot t) + 0.5\sin\left(2\pi \cdot 2000 \cdot t + \frac{3\pi}{4}\right)$$

以采样频率 $f_s = 8000 \text{ Hz}$ 采样，采样周期 $T_s = 1/8000 \text{ s}$，得到离散信号： $$x(n) = \sin\left(\frac{2\pi n}{8}\right) + 0.5\sin\left(\frac{4\pi n}{8} + \frac{3\pi}{4}\right)$$

取 $N=8$，即 $n=0, 1, \dots, 7$，得到离散样本： $$x(0)=0.3535, \quad x(1)=0.3535, \quad x(2)=0.6464, \quad x(3)=1.0607,$$ $$x(4)=0.3535, \quad x(5)=-1.0607, \quad x(6)=-1.3535, \quad x(7)=-0.3535$$

图 1 输入信号

对固定序号 $m=i$，计算 $X(i)$ 的实部与虚部，本质上是 $x(n)$ 分别与余弦基函数和正弦基函数做点积。

本例 DFT 计算结果如下： $$X(0)=0.0-j0.0, \quad X(1)=0.0-j4.0, \quad X(2)=1.414+j1.414, \quad X(3)=0.0+j0.0,$$ $$X(4)=0.0-j0.0, \quad X(5)=0.0-j0.0, \quad X(6)=1.414-j1.414, \quad X(7)=0.0+j4.0$$

分别绘制实部、虚部、幅值、相位可直观观察频谱分布。

DFT 的性质

共轭对称性

由计算结果可观察到： $$|X(5)| = |X(3)|, \quad |X(6)| = |X(2)|, \quad |X(7)| = |X(1)|$$ $$\operatorname{Re}{X(5)} = \operatorname{Re}{X(3)}, \quad \operatorname{Re}{X(6)} = \operatorname{Re}{X(2)}, \quad \operatorname{Re}{X(7)} = \operatorname{Re}{X(1)}$$ $$\operatorname{Im}{X(5)} = -\operatorname{Im}{X(3)}, \quad \operatorname{Im}{X(6)} = -\operatorname{Im}{X(2)}, \quad \operatorname{Im}{X(7)} = -\operatorname{Im}{X(1)}$$ 上述关系对应 DFT 的共轭对称性：$X(m) = X^*(N-m)$。受此约束，后 $N/2-1$ 个样本存在信息冗余，有效输出可视为 $N/2+1$ 个独立复数。

物理含义

在 $N$ 点 DFT 中，序号 $m$ 对应信号在 $N$ 个点内包含 $m$ 个周期。对采样频率 $f_s$，第 $m$ 根谱线对应的频率为： $$f_m = m \cdot \frac{f_s}{N}$$ 本例中：$m=1 \Rightarrow f_1 = 1000 \text{ Hz}$，$m=2 \Rightarrow f_2 = 2000 \text{ Hz}$。

傅里叶变换：FFT 与 DFT 原理及算法详解