第 7 章离散傅里叶变换 / Discrete Fourier Transform (DFT)

7.1 从 DTFT 到 DFT：为什么要"再离散一次"？

在第 6 章中，我们学习了离散时间傅里叶变换（DTFT, Discrete-Time Fourier Transform）。DTFT 将离散时域序列 $x[n]$ 映射到连续频率变量 $\omega$ 上的频谱 $X(e^{j\omega})$。这带来了一个根本性问题：

计算机只能存储和处理有限个数的数据点。

DTFT 的频谱 $X(e^{j\omega})$ 是 $\omega$ 的连续函数——意味着它在 $[0, 2\pi)$ 上有无穷多个值，计算机无法逐一计算和存储。同样地，实际信号也只在有限时间窗口内被采集，即 $x[n]$ 只有 $N$ 个非零样本。

因此，我们需要一种变换，在时域和频域都是离散且有限长的——这就是离散傅里叶变换（DFT, Discrete Fourier Transform）。

graph LR
    A["连续信号 x(t)"] -->|采样| B["离散序列 x[n]"]
    B -->|DTFT| C["连续频谱 X(e^jω)"]
    C -->|频域采样| D["离散频谱 X[k]"]
    B -->|DFT| D
    style A fill:#2d2d2d,color:#fff
    style B fill:#2d2d2d,color:#fff
    style C fill:#2d2d2d,color:#fff
    style D fill:#2d2d2d,color:#fff

核心思想：对长度为 $N$ 的序列 $x[n]$，在频域等间隔取 $N$ 个采样点，得到 $N$ 个离散频谱值 $X[k]$。DFT 本质上是对 DTFT 在 $N$ 个等间隔频率点上的采样。

7.2 数学背景

7.2.1 欧拉公式与复指数

DFT 的核心运算单元是复指数 $e^{-j\frac{2\pi}{N}kn}$。由欧拉公式（Euler’s Formula）：

$$e^{j\theta} = \cos\theta + j\sin\theta$$

复指数是单位圆上的旋转操作。DFT 中，$e^{-j\frac{2\pi}{N}kn}$ 表示在第 $k$ 个频率分量上，对第 $n$ 个时域样本进行相位旋转。这些复指数构成一组正交基函数，使得任意有限长序列都能被分解为不同频率分量的加权叠加。

7.2.2 周期延拓

有限长序列 $x[n]$（$n = 0, 1, \ldots, N-1$）可以看作其以 $N$ 为周期的周期延拓序列 $\tilde{x}[n]$ 的一个周期：

$$\tilde{x}[n] = x[n \mod N]$$

这一概念在理解 DFT 的圆周性质（圆周移位、圆周卷积）时至关重要。

7.2.3 矩阵表示

DFT 可以表示为矩阵乘法 $\mathbf{X} = \mathbf{W}_N \mathbf{x}$，其中 $\mathbf{W}_N$ 是 $N \times N$ 的 DFT 矩阵，元素为：

$$[\mathbf{W}N]{k,n} = e^{-j\frac{2\pi}{N}kn}, \quad k,n = 0, 1, \ldots, N-1$$

这一表示说明 DFT 是线性变换，可用线性代数工具分析。

验证工具：Python 中 numpy.fft.fft(x) 可直接计算 DFT，numpy.linalg.dft(N) 可生成 DFT 矩阵（部分版本）。也可手动构造 $W_N$ 矩阵与 numpy.fft.fft 结果对比验证。

7.3 DFT 的定义

7.3.1 正变换（DFT）

设 $x[n]$ 为长度为 $N$ 的有限长序列，其 $N$ 点 DFT 定义为：

$$X[k] = \sum_{n=0}^{N-1} x[n] , e^{-j\frac{2\pi}{N}kn}, \quad k = 0, 1, \ldots, N-1$$

其中 $e^{-j\frac{2\pi}{N}kn} = W_N^{kn}$，$W_N = e^{-j\frac{2\pi}{N}}$ 称为旋转因子（Twiddle Factor）。

7.3.2 反变换（IDFT）

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] , e^{j\frac{2\pi}{N}kn}, \quad n = 0, 1, \ldots, N-1$$

IDFT 将频域的 $N$ 个离散值 $X[k]$ 重建为时域序列 $x[n]$。正变换与反变换构成一一对应关系，信息无损失。

物理含义：$X[0]$ 对应直流分量（DC），$X[k]$ 对应第 $k$ 个频率分量的幅度和相位。若采样率为 $f_s$，则第 $k$ 个频率点对应物理频率：

$$f_k = \frac{k \cdot f_s}{N}, \quad k = 0, 1, \ldots, N-1$$

7.4 DFT 的性质

7.4.1 线性性（Linearity）

若 $x_1[n] \overset{\text{DFT}}{\longleftrightarrow} X_1[k]$，$x_2[n] \overset{\text{DFT}}{\longleftrightarrow} X_2[k]$，则：

$$a \cdot x_1[n] + b \cdot x_2[n] \overset{\text{DFT}}{\longleftrightarrow} a \cdot X_1[k] + b \cdot X_2[k]$$

这是 DFT 作为线性变换的直接推论。

7.4.2 圆周移位（Circular Shift）

在 DTFT 中我们讨论线性移位，但在 DFT 中由于隐含的周期性，移位变为圆周移位：

$$x[(n - m)_N] \overset{\text{DFT}}{\longleftrightarrow} W_N^{km} \cdot X[k]$$

其中 $(n-m)_N$ 表示 $(n-m) \mod N$。序列超出 $[0, N-1]$ 范围的部分会"绕回"到另一端，这正是周期延拓的体现。

7.4.3 圆周卷积（Circular Convolution）

两个 $N$ 点序列的圆周卷积定义为：

$$y[n] = \sum_{m=0}^{N-1} x_1[m] , x_2[(n-m)_N], \quad n = 0, 1, \ldots, N-1$$

时域圆周卷积对应频域乘积：

$$x_1[n] \circledast x_2[n] \overset{\text{DFT}}{\longleftrightarrow} X_1[k] \cdot X_2[k]$$

其中 $\circledast$ 表示圆周卷积。这是 DFT 最重要的性质之一，是频域滤波的理论基础。

7.4.4 频域采样与时域周期延拓

DFT 是对 DTFT 的频域采样。频域以 $N$ 点等间隔采样，等价于时域以 $N$ 为周期进行延拓。如果原序列长度恰好为 $N$（或更短），则周期延拓不会发生混叠（Aliasing），从 DFT 可以完美恢复原序列。

7.4.5 Parseval 定理

$$\sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2$$

时域能量等于频域能量（注意频域侧的 $1/N$ 因子）。这一定理可用于验证 DFT/IDFT 实现的正确性。

7.5 频谱泄漏（Spectral Leakage）

7.5.1 问题本质

DFT 隐含假设 $x[n]$ 是以 $N$ 为周期的周期序列。当我们截取一段有限长数据做 DFT 时，若信号频率不恰好落在某个 DFT 频率点上（即不是 $\Delta f$ 的整数倍），则周期延拓后在边界处会出现不连续跳变。

这种不连续在频域表现为：原本应该集中在单一频率点的能量"泄漏"到相邻频率点上，这就是频谱泄漏（Spectral Leakage）。

7.5.2 窗函数（Window Function）

为抑制泄漏，可在 DFT 前对信号加窗。常用窗函数包括：

窗函数	主瓣宽度	旁瓣衰减	适用场景
矩形窗（Rectangular）	最窄	最差（~13 dB）	频率完全对齐时
汉宁窗（Hanning）	2 倍	~31 dB	通用频谱分析
汉明窗（Hamming）	2 倍	~41 dB	语音处理
布莱克曼窗（Blackman）	3 倍	~57 dB	需要高动态范围

设计权衡：主瓣越窄，频率分辨率越高；旁瓣越低，泄漏抑制越好。两者不可兼得。

7.6 频率分辨率

DFT 的频率分辨率（Frequency Resolution）为：

$$\Delta f = \frac{f_s}{N}$$

其中 $f_s$ 为采样率，$N$ 为 DFT 点数。$\Delta f$ 是相邻频率点之间的间距。

要提高频率分辨率，有两种途径：

增加观察时间 $T = N/f_s$（增大 $N$，保持 $f_s$ 不变）
降低采样率 $f_s$（需注意满足奈奎斯特条件以避免混叠）

补零（Zero Padding） 不能提高真正的频率分辨率，但可以在频域插入更多点使谱线更平滑，便于观察谱的形状。补零后的 DFT 等效于对 DTFT 进行更密的采样。

7.7 DFT 与卷积：圆周卷积 vs 线性卷积

线性卷积（Linear Convolution）是信号处理中常见的操作。设 $x_1[n]$ 长度为 $L_1$，$x_2[n]$ 长度为 $L_2$，则线性卷积结果长度为 $L_1 + L_2 - 1$。

但 DFT 的乘积对应圆周卷积，结果长度仍为 $N$。要用 DFT 计算线性卷积，需满足：

$$N \geq L_1 + L_2 - 1$$

具体方法：将两个序列补零至长度 $N \geq L_1 + L_2 - 1$，然后做 $N$ 点 DFT → 频域相乘 → IDFT。这就是快速卷积（Fast Convolution），利用 FFT 将卷积运算复杂度从 $O(N^2)$ 降至 $O(N \log N)$。

flowchart LR
    A["x1[n] 补零至 N 点"] --> B["DFT → X1[k]"]
    C["x2[n] 补零至 N 点"] --> D["DFT → X2[k]"]
    B --> E["Y[k] = X1[k] · X2[k]"]
    D --> E
    E --> F["IDFT → y[n]"]
    F --> G["y[n] = x1[n] * x2[n]"]
    style A fill:#2d2d2d,color:#fff
    style B fill:#2d2d2d,color:#fff
    style C fill:#2d2d2d,color:#fff
    style D fill:#2d2d2d,color:#fff
    style E fill:#3a3a5c,color:#fff
    style F fill:#2d2d2d,color:#fff
    style G fill:#2d2d2d,color:#fff

7.8 DFT 的工程应用

7.8.1 频谱分析（Spectrum Analysis）

DFT 是最基础的频谱分析工具。对采集到的信号 $x[n]$ 做 DFT，取 $|X[k]|$ 得到幅度谱（Magnitude Spectrum），取 $\arg(X[k])$ 得到相位谱（Phase Spectrum）。

实际应用中的标准流程：

采集 $N$ 个样本（采样率 $f_s$）
乘以窗函数 $w[n]$（抑制泄漏）
计算 $N$ 点 DFT
取幅度谱并转换为 dB：$20\log_{10}(|X[k]|)$

7.8.2 频域滤波（Frequency-Domain Filtering）

利用圆周卷积定理，滤波可以在频域实现：

对输入信号做 DFT
设计频域滤波器 $H[k]$（低通、高通、带通等），在频域相乘：$Y[k] = X[k] \cdot H[k]$
做 IDFT 得到滤波后的时域信号

对于长序列，常用**重叠相加法（Overlap-Add）或重叠保留法（Overlap-Save）**进行分段处理。

7.8.3 OFDM 中的核心运算

正交频分复用（OFDM, Orthogonal Frequency Division Multiplexing）是 4G/5G 移动通信和 Wi-Fi 的核心技术。OFDM 的调制和解调分别通过 IDFT 和 DFT 实现：

发射端：将数据映射到 $N$ 个子载波上作为 $X[k]$，通过 IDFT 得到时域信号 $x[n]$
接收端：对接收信号做 DFT，恢复各子载波上的数据

DFT 保证了各子载波之间的正交性，使频谱利用率最大化。实际系统中使用 FFT（快速傅里叶变换）实现高效计算。

7.9 DFT 计算的伪代码

7.9.1 朴素 DFT 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function DFT(x, N):
    输入: x[0..N-1] 为长度 N 的复数序列
    输出: X[0..N-1] 为 DFT 结果

    for k = 0 to N-1:
        X[k] = 0
        for n = 0 to N-1:
            angle = -2π × k × n / N
            X[k] = X[k] + x[n] × (cos(angle) + j×sin(angle))
    return X

7.9.2 朴素 IDFT 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function IDFT(X, N):
    输入: X[0..N-1] 为频域复数序列
    输出: x[0..N-1] 为时域序列

    for n = 0 to N-1:
        x[n] = 0
        for k = 0 to N-1:
            angle = 2π × k × n / N
            x[n] = x[n] + X[k] × (cos(angle) + j×sin(angle))
        x[n] = x[n] / N
    return x

朴素实现的复杂度为 $O(N^2)$。实际工程中，采用 FFT（Fast Fourier Transform）算法将复杂度降至 $O(N \log N)$，将在下一章详细介绍。

7.9.3 Python 验证示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np

# 生成测试信号：1 kHz 正弦波 + 3 kHz 正弦波
fs = 10000        # 采样率 10 kHz
N = 1024          # DFT 点数
t = np.arange(N) / fs
x = np.sin(2 * np.pi * 1000 * t) + 0.5 * np.sin(2 * np.pi * 3000 * t)

# 计算 DFT
X = np.fft.fft(x)

# 频率轴
freq = np.arange(N) * fs / N

# 幅度谱（归一化）
magnitude = np.abs(X) / N

# 验证 Parseval 定理
time_energy = np.sum(np.abs(x)**2)
freq_energy = np.sum(np.abs(X)**2) / N
print(f"时域能量: {time_energy:.6f}")
print(f"频域能量: {freq_energy:.6f}")
print(f"Parseval 误差: {abs(time_energy - freq_energy):.2e}")

7.10 本章小结

概念	要点
DFT 本质	对 DTFT 的 $N$ 点等间隔采样，时域频域均离散有限长
正变换	$X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}$
反变换	$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-kn}$
频率分辨率	$\Delta f = f_s / N$，由观察时间决定
频谱泄漏	截断导致边界不连续，可用窗函数抑制
圆周卷积	时域圆周卷积 ↔ 频域乘积；补零后可实现线性卷积
典型应用	频谱分析、频域滤波、OFDM 调制解调
计算复杂度	朴素 $O(N^2)$，FFT 优化至 $O(N \log N)$

DFT 是连接理论分析与工程实现的桥梁。它将连续频谱离散化，使得傅里叶分析可以在数字计算机上高效执行。理解 DFT 的周期延拓本质和频谱泄漏机制，是正确使用频谱分析工具的前提。下一章将介绍 FFT 算法，揭示如何高效计算 DFT。

第 7 章 离散傅里叶变换 / Discrete Fourier Transform (DFT)#

7.1 从 DTFT 到 DFT：为什么要"再离散一次"？#

7.2 数学背景#

7.2.1 欧拉公式与复指数#

7.2.2 周期延拓#

7.2.3 矩阵表示#

7.3 DFT 的定义#

7.3.1 正变换（DFT）#

7.3.2 反变换（IDFT）#

7.4 DFT 的性质#

7.4.1 线性性（Linearity）#

7.4.2 圆周移位（Circular Shift）#

7.4.3 圆周卷积（Circular Convolution）#

7.4.4 频域采样与时域周期延拓#

7.4.5 Parseval 定理#

7.5 频谱泄漏（Spectral Leakage）#

7.5.1 问题本质#

7.5.2 窗函数（Window Function）#

7.6 频率分辨率#

7.7 DFT 与卷积：圆周卷积 vs 线性卷积#

7.8 DFT 的工程应用#

7.8.1 频谱分析（Spectrum Analysis）#

7.8.2 频域滤波（Frequency-Domain Filtering）#

7.8.3 OFDM 中的核心运算#

7.9 DFT 计算的伪代码#

7.9.1 朴素 DFT 实现#

7.9.2 朴素 IDFT 实现#

7.9.3 Python 验证示例#

7.10 本章小结#