DFT 与 FFT

1.1 为什么有了 DTFT 还要 DFT

DTFT 给出的是连续频率函数 $X(e^{j\omega})$，理论上很完整，但计算机不能直接保存"连续函数"。实际实验和工程里，我们拿到的是有限长样本块，比如一段语音、一帧图像行信号、一段传感器记录。要分析这段有限数据的频率结构，就必须把连续频率轴离散化。

DFT 做的事情就是：在一个 $2\pi$ 周期内取 $N$ 个等间隔频率点，把频谱变成长度为 $N$ 的复数数组。这样一来，频域分析就能进入矩阵运算和程序实现。FFT 则进一步回答：这些 DFT 频点怎样才能高效算出来。

DFT 的思想并非凭空出现。早在 1805 年，Gauss 就提出了将长度为 $N$ 的 DFT 递归分解为两个 $N/2$ 点 DFT 的算法——用于插值小行星 Pallas 和 Juno 的轨道。但 Gauss 没有分析算法的时间复杂度，且用新拉丁文发表，这个工作长期未被认知。直到 1965 年，Cooley 和 Tukey 在冷战核试验检测的实际需求驱动下重新发明了这个算法，并明确指出对 $N=2^k$ 的复杂度从 $O(N^2)$ 降至 $O(N\log N)$。此后 FFT 迅速普及，恰逢高速 ADC 的问世，直接推动了数字信号处理学科的诞生。

1.2 四大变换形式与时频对偶性

傅氏变换按时间和频率的连续/离散、有限/无限可以分为四种基本形式。它们之间遵守一条简单规律：

下表列出了四种变换及其时频域特征：

表中 DTFT 时域离散、频域连续且周期——这对应了前面对偶性规律：离散化必然导致周期化。DFT 则在两个域上都做了离散化（等效于对 DTFT 的频域采样），所以时空两域都变成离散的有限长序列。

四种变换不是彼此替代的关系——FT 是最通用的数学工具，FS 用于周期连续信号，DTFT 是计算机能处理离散采样后的理论频谱，DFT 才是真正能让机器逐点算出来的有限维变换。

PDF时频域对偶性示意p.6

正在渲染 PDF 第 6 页…

1.3 对偶性证明

上面给出了定性结论：时域离散→频域周期，频域离散→时域周期。现在从数学定义出发，把这两条链各自严格推导一遍。

证明一：时域离散化 → 频域周期化

设时域信号 $x[n]$ 是离散序列（$n$ 取整数），其 DTFT 为

把自变量 $\omega$ 替换为 $\omega+2\pi$：

关键一步：因为 $n$ 是整数，所以

于是

频域以 $2\pi$ 为周期。如果 $n$ 不是整数而是连续变量 $t$，那么 $e^{-j2\pi t}\neq 1$（除非 $t$ 恰好为整数），周期性不成立。所以周期性的根源在于 $n$ 的离散（整数）性。

证明二：频域离散化 → 时域周期化

设频域信号 $X[k]$ 在等间隔频率点上取值（$k$ 取整数），通过 IDFS/IDFT 恢复时域：

把 $n$ 替换为 $n+N$：

计算第二项：

因为 $k$ 是整数，$e^{j2\pi k}=1$。所以

时域以 $N$ 为周期。同样的逻辑：如果 $k$ 不是整数而是连续变量 $\omega$（对应 DTFT 的情况），$e^{j2\pi\omega}\neq 1$，时域就不会周期化。所以时域周期化的根源在于频域采样点 $k$ 的离散（整数）性。

反向命题：连续 → 非周期

• 时域连续 → 频域非周期：如果 $n$ 换成连续变量 $t$，则 $e^{-j2\pi t}$ 一般不等于 1，无法推出 $X(\Omega+2\pi)=X(\Omega)$。连续时间傅氏变换（FT）的频谱不具有周期性。
• 频域连续 → 时域非周期：如果 $k$ 换成连续变量 $\omega$，则 $e^{j2\pi\omega}$ 一般不等于 1，无法推出 $x[n+N]=x[n]$。DTFT 对应的时域序列不具有周期性。

2.1 N 点 DFT 与 IDFT

长度为 $N$ 的序列 $x[0],x[1],\ldots,x[N-1]$ 的 DFT 定义为

令 $W_N=e^{-j2\pi/N}$，也可写成

反变换为 IDFT（逆离散傅里叶变换，Inverse Discrete Fourier Transform）：

$k$ 不是普通编号，而是频率槽位。它对应的角频率为 $\omega_k=2\pi k/N$。当采样频率为 $f_s$ 时，第 $k$ 个频点对应物理频率 $f_k=kf_s/N$，但超过 $N/2$ 的频点通常解释为负频率。

2.2 正交性：为什么 IDFT 能恢复序列

DFT 的核心代数基础是复指数正交性：

如果两个频率槽位不同，它们在一个完整周期里的旋转方向会均匀绕圈，求和相互抵消；如果频率槽位相同，每一项都是 1，求和为 $N$。IDFT 前面的 $1/N$ 正是为了抵消这个归一化因子。

从线性代数角度看，DFT 是把 $x$ 投影到一组正交复指数基上；IDFT 是把这些基按系数加回来。

3.1 DFT 是 DTFT 的等间隔采样

如果把有限长序列看成

它的 DTFT 是

在 $\omega_k=2\pi k/N$ 处采样，就得到

这说明 DFT 不是凭空发明的新变换，而是 DTFT 在有限网格上的采样。但 DFT 的反变换会把这 $N$ 个频点解释成一个长度为 $N$ 的周期序列，因此边界处理和循环结构会自然出现。

3.2 DFS：DFT 的周期延拓根基

严格说，DFT 是周期序列的离散傅里叶级数（DFS）被矩形窗截取一个周期后的结果。DFS 处理周期序列 $\tilde{x}[n]$（周期 $N$），其定义是

$\tilde{X}[k]$ 本身也是周期为 $N$ 的序列。DFS 逆变换恢复周期序列：

DFS 和 DFT 的数学表达式一模一样，唯一的区别是解读方式：DFS 的输入和输出都默认是周期无限的，DFT 的输入和输出都视为有限长的主值区间。两者的关系可以写作

其中 $R_N[\cdot]$ 是矩形窗（主值区间 $0\le n \le N-1$ 内为 1，其余为 0）。

DFS 同样满足一系列性质，其中最有用的几个：

DFS 的性质几乎完全照搬到 DFT，区别只在于 DFT 需要处理索引的模 $N$ 回绕（因为 DFT 把有限长序列当作周期序列的一个周期来对待）。

PDFDFS 定义与性质 · p.12–61p.12–61

正在渲染 PDF 第 12 页…

正在渲染 PDF 第 61 页…

在 DTFT 中，时域线性卷积对应频域乘法。但在 DFT 中，因为序列被默认周期延拓，频域逐点乘法对应的是长度为 $N$ 的循环卷积：

这里的 $\bmod N$ 表示索引超出边界后会绕回前面。普通线性卷积的尾巴如果超过 $N-1$，在循环卷积里就会折叠到开头，这叫时域混叠或循环混叠。

循环卷积和线性卷积之间有一个严谨的数学关系：长度为 $L$ 的循环卷积等于线性卷积的周期延拓再截取。设 $x_1[n]$ 长度为 $L$，$x_2[n]$ 长度为任意长，记线性卷积为 $y_l[n]=x_1[n]*x_2[n]$，则循环卷积

可以展开为

证明的核心步骤是：把 $x_2[(n-m)\bmod L]$ 写成 $\sum_{r=-\infty}^{\infty}x_2[n+rL-m]$（周期延拓的求和），然后交换两个求和顺序。这个关系说明，循环卷积的每个输出点 $\tilde{y}[n]$ 都包含了线性卷积在 $n, n\pm L, n\pm 2L,\ldots$ 处所有值的叠加。因此当 $L$ 小于线性卷积长度时，不同 $r$ 的项会互相重叠——这就是时域混叠。

PDF周期卷积推导p.80

正在渲染 PDF 第 80 页…

实际用 DFT 分析信号时，隐含了两个动作：截取有限窗口、在有限频点上观察频谱。截取窗口相当于时域乘上窗函数，频域会变成原频谱与窗函数频谱的卷积。因此如果信号频率不正好落在 DFT 频点上，能量会扩散到相邻频点，这就是频谱泄漏（spectral leakage）。

频谱泄漏的本质不是信号的问题，而是边界假设的问题。DFT 隐含假设输入是周期信号的单个周期。当信号实际频率 $f_0$ 不等于任何 DFT 分析频率（即 $f_0 \neq k \cdot f_s / N$）时，信号周期延拓在边界处产生不连续性。为了拟合这个尖锐跳变，DFT 被迫在所有频率上分配能量。

不同窗函数的区别在于主瓣宽度与旁瓣衰减之间的 trade-off：

选择窗函数的工程原则：

• 频率是否对齐 DFT bin？若精确对齐，矩形窗即可；否则用 Hann 窗（覆盖 95% 的应用场景）。
• 频率分辨率 vs 动态范围：频率靠得很近 → 用主瓣窄的窗（Hann）；关注弱信号与大信号共存 → 用旁瓣衰减强的窗（Blackman）。
• 通用默认：Hann 窗是大多数情况下的良好默认。

6.1 为什么需要 FFT：DFT 的计算瓶颈

DFT 的定义式为

每个 $X[k]$ 需要 $N$ 次复数乘法，一共 $N$ 个 $k$，所以直接计算 $N$ 点 DFT 需要 $N^2$ 次复乘。当 $N$ 较小时问题不大，但工程中 $N$ 经常很大：

音频 CD 以 $44.1\,\text{kHz}$ 采样，1 秒的数据对应 $N=44100$，直接算 DFT 要 $\sim 2\times 10^9$ 次复乘，实时处理根本不可能。图像处理、雷达、MRI 等场景的 $N$ 更大。如果 DFT 只能 $O(N^2)$ 地算，它在工程中几乎没用。

6.2 Radix-2 DIT 分治推导

最常用的 FFT 变体是 Radix-2 按时间抽取（DIT, Decimation In Time），要求 $N=2^M$。它的思路是：把输入序列按偶数和奇数下标拆成两组，分别做 $N/2$ 点 DFT，再用一层合成得到完整的 $N$ 点 DFT。

对 $N=2M$ 的 DFT，按偶数和奇数样本拆开：

利用 $W_N^2=W_{N/2}$，得到

$E[k]$ 是偶数样本的 $M$ 点 DFT，$O[k]$ 是奇数样本的 $M$ 点 DFT，两者都已经对 $M$ 周期，所以 $E[k+M]=E[k]$、$O[k+M]=O[k]$。再利用 $W_N^{k+M}=-W_N^k$，得

这两个式子就是蝶形运算（butterfly）。一对输入 $(E[k],\,O[k])$ 通过一次复乘 $W_N^k O[k]$ 和两次加减，同时产生两个输出 $X[k]$ 和 $X[k+M]$。上下两支只差一个加减号。

递归拆分到 2 点 DFT 后，整个计算量满足

6.2a N=8 的具体分解过程

以 $N=8$ 为例，展示 FFT 分治的具体操作。

第一步：按偶数/奇数下标拆分

偶数序列 $x_1[r]=x[2r]$：$x_1[0]=x[0]$，$x_1[1]=x[2]$，$x_1[2]=x[4]$，$x_1[3]=x[6]$

奇数序列 $x_2[r]=x[2r+1]$：$x_2[0]=x[1]$，$x_2[1]=x[3]$，$x_2[2]=x[5]$，$x_2[3]=x[7]$

第二步：分别做 4 点 DFT

第三步：蝶形合成

这一层蝶形需要 4 次复乘（$W_8^0,W_8^1,W_8^2,W_8^3$）和 8 次复加。对 $X_1$ 和 $X_2$ 再分别递归拆成两个 2 点 DFT，就完成了整个 8 点 FFT。

PDFN=8 DFT 分解为两个 N/2 点 DFT + 蝶形合成p.16

正在渲染 PDF 第 16 页…

6.3 DIT 与 DIF、Bit-Reversal 与其他算法

Radix-2 有两种对偶形式：按时间抽取（DIT）将输入序列按奇/偶下标分组（上面推导的）；按频率抽取（DIF）将输出频谱按奇/偶 $k$ 分组。两者在计算效率上几乎无差异，都包含 $\log_2 N$ 个阶段，每阶段 $N/2$ 个蝶形运算。

$N$ 点 FFT 的总运算量：

FFT 的原地（in-place）特性意味着所有中间结果直接覆盖原数组位置，无需额外存储空间——$N$ 点 FFT 只需 $O(N)$ 的存储。这也是为什么蝶形图中每条数据路径都直接写入而不经过额外缓冲区。

递归偶奇拆分会导致输出下标是输入下标二进制位反转后的顺序——即 bit-reversal。以 $N=8$ 为例：

输入顺序 $0,1,2,3,4,5,6,7$ 经过 bit-reversal 后变为 $0,4,2,6,1,5,3,7$。由于 bit-reversal 是一个对合（做两次恢复原序），只需做一次交换即可原地恢复正序。

当 $N$ 包含大素因子时 Radix-2 无法高效分解，此时有特殊算法：Rader's algorithm 将素数长度 $N$ 的 DFT 转化为长度 $N-1$ 的循环卷积；Bluestein's algorithm 用 chirp-Z 变换将任意长度 $N$ 的 DFT 转化为 2 的幂长度的卷积。

PDF8 点 FFT 完整蝶形信号流图p.26

正在渲染 PDF 第 26 页…

6.2 频谱分析、滤波与 STFT

FFT 让 DFT 足够快，于是很多滤波和谱估计任务都可以转到频域完成：先 FFT，频域乘以滤波器响应，再 IFFT 回到时域。只要处理好零填充和块边界，就能把长信号卷积变成高效的块处理算法。

Overlap-Add（OLA）和Overlap-Save（OLS）是两种经典的分块快速卷积方法：

• OLA：将输入切成不重叠的块，每块补零后做 FFT → 频域乘法 → IFFT，相邻块的结果在重叠区相加。
• OLS：每一块输入从前一块末尾保留 $M-1$ 个样本（$M$ 为滤波器长度），卷积后丢弃前 $M-1$ 个被循环混叠污染的样本。

两者在数学上等价，计算量相同。OLA = "先补零再卷积，再重叠相加"；OLS = "先重叠输入，卷积后丢弃无效部分"。

FFT 最广泛的应用形式是短时傅里叶变换（STFT）：将长信号切成重叠的短窗，对每个窗做 FFT，得到时-频二维表示：

其中 $w[n]$ 是窗函数，$R$ 是跳距（hop size），$m$ 是帧编号。帧长越大，频率分辨率越高（$\Delta_f = f_s/N$），但时间分辨率越差——这是一条经典的不确定原理 trade-off。

7.1 DFT 做题常用性质

7.2 复习速查表

DFT 只在 $N$ 个离散频点 $\omega_k=2\pi k/N$ 上给出了频谱值。如果想知道两个频点之间的连续频谱是什么——比如想要更高分辨率地观察谱峰——就用到频域内插。

DFT 频点 $X[k]$ 到连续 DTFT 频谱 $X(e^{j\omega})$ 的内插公式为

其中 $\phi(\omega)$ 是内插函数，它是单个矩形窗序列 $R_N[n]$ 的 DTFT：

翻译成自然语言：每个 $X[k]$ 被一个中心在 $\omega_k$ 上的 $\operatorname{dirc}$ 型函数（类似 sinc）加权，相邻频点的旁瓣相互重叠后精确重建了完整的连续频谱。这也意味着，零填充到更长 $N$ 后再做 DFT 得到的并不是新的信息——它只是在相同 DTFT 曲线上更密集地采样。

如果把 DFT 和连续信号连起来看，还有一个重要的关系：设采样周期为 $T$ 的离散序列 $x[n]$ 的 DFT 为 $X[k]$，连续信号 $x(t)$ 的 FT 是 $X(j\Omega)$，则在频率点 $\Omega_k=k\Omega_0=k\cdot 2\pi f_s / N$ 处有

这意味着 DFT 频点值乘上 $T$ 就逼近了原连续信号的频谱采样值。这个关系在工程中用来标定频谱的物理单位。

PDF频域内插与频谱采样 · p.91–95p.91–95

正在渲染 PDF 第 91 页…

正在渲染 PDF 第 95 页…

学完 DFT/FFT 后，频域分析从"能理解"变成"能计算"。下一节 数字滤波器基础与结构 会继续使用这里的思想：滤波器有频率响应，频率响应可以通过 DFT 采样和 FFT 计算，FIR 滤波器也可以通过快速卷积实现。

如果说 DTFT 是理论镜头，DFT 是有限网格，FFT 就是实际相机。没有 FFT，大规模频谱分析和实时数字滤波很难成为工程常规工具。