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 是把这些基按系数加回来。

2.3 周期延拓：DFT 的隐含假设

DFT 公式看起来只是一个有限求和，但它背后隐含了一个至关重要的假设：你输入的 $N$ 点序列不是一个"有始有终"的有限信号，而是一个无限周期信号的一个周期。

这个隐含假设叫周期延拓（periodic extension）：

也就是说，DFT 在数学上处理的不是 $x[n]$，而是把 $x[0],x[1],\ldots,x[N-1]$ 首尾相接无限重复后得到的周期序列 $\tilde{x}[n]$。DFT 系数 $X[k]$ 本质上是这个周期序列的傅里叶级数系数。

为什么这个假设如此重要？因为周期延拓会改变信号的物理含义。同一个有限长序列，用不同的 $N$ 做 DFT，意味着不同的周期延拓方式，从而对应完全不同的周期信号。具体例子见本章末尾例题区。

2.4 周期 $N$ 与序列长度 $L$ 的关系

设原始序列 $x[n]$ 的实际长度为 $L$（即 $x[n]$ 在 $0\le n\le L-1$ 之外全为零），DFT 点数为 $N$。$N$ 与 $L$ 的相对大小直接决定了周期延拓后信号的物理含义：

核心原则：

• 补零（$N>L$）改变的是频域采样密度，不改变 DTFT 本身。它让栅栏更密，看到更多细节，但主瓣宽度（真实频率分辨率）由原始数据长度 $L$ 决定，补零无法缩窄主瓣。
• 截断（$N<L$）是真正的信息丢失。被丢弃的 $L-N$ 个样本永远消失了，频谱会产生额外的泄漏和失真。
• 周期延拓的"边界效应"取决于 $N$ 与信号实际周期的关系。如果信号本身是周期性的且 $N$ 恰好是整数个周期，边界处连续，频谱干净；否则边界不连续会产生频谱泄漏。

周期延拓的三个直接后果：

1. 循环移位：DFT 中的"移位"不是普通平移，而是循环移位——从右边移出的元素会从左边绕回来。因为周期延拓后没有"边界"，$x[N]=x[0]$。
2. 循环卷积：DFT 域乘法对应的是循环卷积而非线性卷积。线性卷积的"尾巴"会在周期边界处折回，产生混叠。
3. 频谱泄漏与栅栏效应：周期延拓在边界处可能产生不连续（除非信号恰好是整数个周期），这种不连续在频域表现为频谱泄漏。同时 DFT 只在离散频点采样，可能"漏掉"重要的频谱特征。

2.5 综合例题：矩形序列 $R_4(n)$ 的 DFT 与幅频特性

题目：设 $x(n)=R_4(n)=[1,1,1,1]$，分别求 4 点 DFT 和 8 点 DFT，并分析它们与 DTFT 幅频曲线的关系。

目标：理解 DFT 是 DTFT 的频域采样，不同点数对应不同采样密度，揭示栅栏效应与周期延拓的影响。

Step 0: DTFT 幅频特性。

$R_4(n)$ 的 DTFT 为

幅度响应为经典的Dirichlet 核（数字 sinc）形状：

在 $\omega=0$ 处主瓣峰值为 $4$，零点位于 $\omega=\pi/2,\;\pi,\;3\pi/2$，零点之间有旁瓣。

---

Step 1: 4 点 DFT。

$N=4$，$W_4=e^{-j2\pi/4}=-j$，采样频率 $\omega_k=2\pi k/4$：

• $k=0$：$X_4(0)=1+1+1+1=4$
• $k=1$：$X_4(1)=1+(-j)+(-1)+j=0$
• $k=2$：$X_4(2)=1+(-1)+1+(-1)=0$
• $k=3$：$X_4(3)=1+j+(-1)+(-j)=0$

4 点采样位置与 DTFT 的对应：

4 点 DFT 的采样间隔 $\Delta\omega=\pi/2$ 恰好等于 DTFT 零点间距，所有采样点恰好落在零点或主瓣峰值上，旁瓣完全被"漏掉"。

---

Step 2: 8 点 DFT（末尾补 4 个零）。

$y(n)=[1,1,1,1,0,0,0,0]$，$N=8$，$W_8=e^{-j2\pi/8}=e^{-j\pi/4}$，采样频率 $\omega_k=2\pi k/8=\pi k/4$：

用几何级数公式 $X_8(k)=\dfrac{1-e^{-j\pi k}}{1-e^{-j\pi k/4}}$：

• $k=0$：$X_8(0)=4$
• $k=1$：$X_8(1)=\dfrac{2}{1-e^{-j\pi/4}}$，$|X_8(1)|=\sqrt{4+2\sqrt{2}}\approx 2.613$
• $k=2$：$X_8(2)=1+(-j)+(-1)+j=0$（恰好落在 DTFT 零点 $\omega=\pi/2$）
• $k=3$：$X_8(3)=\dfrac{2}{1-e^{-j3\pi/4}}$，$|X_8(3)|=\sqrt{4-2\sqrt{2}}\approx 1.082$
• $k=4$：$X_8(4)=0$（落在 DTFT 零点 $\omega=\pi$）
• $k=5$：共轭对称，$|X_8(5)|=|X_8(3)|\approx 1.082$
• $k=6$：$X_8(6)=0$（落在 DTFT 零点 $\omega=3\pi/2$）
• $k=7$：共轭对称，$|X_8(7)|=|X_8(1)|\approx 2.613$

8 点采样位置与 DTFT 的对应：

---

Step 3: 4 点 vs 8 点 DFT 的核心区别。

Step 4: 周期延拓视角。为什么 4 点和 8 点 DFT 结果不同？回顾本节 2.3 和 2.4 的讨论：DFT 在数学上等价于先把有限长序列周期延拓成周期序列，再求 DFS 系数。4 点延拓得到全 1 常数序列（只有 DC），8 点延拓得到周期方波（含奇次谐波）。同一个 $[1,1,1,1]$，延拓周期不同，频谱自然不同。

例题区

DFT 的所有性质都根源于一个事实：DFT 隐含了周期延拓假设（见 Part 2 的 2.3 节）。理解了这一点，下面的每条性质都变得自然。

3.1 线性性质

DFT 是线性变换，满足叠加原理：

这是 DFT 定义中求和运算线性的直接结果。做题时常用它把复杂序列拆成简单序列分别求 DFT 再叠加。

3.2 循环移位性质

时域循环移位：

时域循环移位 $m$ 位，频域只产生相位旋转，幅度谱不变。注意这里的移位是循环移位——从右边移出的元素会从左边绕回来，因为周期延拓后没有"边界"。

频域循环移位（对偶性质）：

时域乘以复指数 $e^{j2\pi ln/N}$，频域循环移位 $l$ 位。这是频谱搬移的数学基础。

3.3 循环卷积定理

在 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 页…

对偶性质（时域相乘）：

时域相乘对应频域循环卷积（带 $1/N$ 归一化）。这是加窗分析的数学基础——时域加窗等于频域与窗函数频谱做循环卷积，导致频谱泄漏。

3.4 复共轭与共轭对称性

复共轭的 DFT：

推导：$\sum_{n=0}^{N-1} x^*[n] W_N^{kn} = \left(\sum_{n=0}^{N-1} x[n] W_N^{-kn}\right)^* = X^*[-k]$。注意 $-k \bmod N = N-k$（$k \ne 0$ 时）。

实序列的共轭对称性：当 $x[n]$ 为实序列时，

证明：因为 $x[n]$ 是实序列，$x^*[n]=x[n]$，所以 $\text{DFT}\{x^*[n]\}=\text{DFT}\{x[n]\}=X[k]$。另一方面，由复共轭性质 $\text{DFT}\{x^*[n]\}=X^*[N-k]$，因此

两边取共轭即得 $X[N-k]=X^*[k]$。

直接推导：也可以从 DFT 定义直接验证。由

而 $W_N^{Nn}=e^{-j\frac{2\pi}{N}Nn}=e^{-j2\pi n}=1$，所以

这意味着：

• 幅度谱偶对称：$|X[N-k]| = |X[k]|$
• 相位谱奇对称：$\arg X[N-k] = -\arg X[k]$
• 实部偶对称，虚部奇对称

特殊点：$X[0]$ 和 $X[N/2]$（$N$ 为偶数时）必为实数。

3.5 Parseval 定理

时域能量等于频域能量（差归一化因子）：

证明：从左边出发，将 $|x[n]|^2$ 拆为 $x[n]\,x^*[n]$：

将 IDFT 公式代入其中一个 $x[n]$：

得：

考察 (*) 项：

代回原式：

证毕。

核心思路：把 $|x[n]|^2$ 拆成 $x[n]x^*[n]$，用 IDFT 替换其中一个 $x[n]$，交换求和顺序后，内层求和恰好是 $X^*(k)$。物理意义是能量守恒在离散频域中的体现。

3.6 频谱泄漏与窗函数

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

从数学上看，对无限长信号做 $N$ 点 DFT 等价于先加矩形窗截断再做 DFT。时域相乘对应频域循环卷积，矩形窗的频谱（Dirichlet 核）与信号真实频谱卷积后，能量从主瓣"泄漏"到旁瓣。

减少泄漏的方法是使用非矩形窗（Hamming、Hanning、Blackman 等），它们以加宽主瓣为代价压低旁瓣：

3.7 性质速查表

3.8 Parseval 定理例题

Parseval 定理的证明细节见本章末尾例题区。配套的工程实例：

3.9 复习速查表

例题区

4.1 DFT 是 DTFT 的等间隔采样

如果把有限长序列看成

它的 DTFT 是

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

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

4.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 页…

4.3 频域采样定理

时域采样定理告诉我们：对带限信号以足够高的频率采样，可以无失真地恢复原信号。频域采样定理是其对偶：对有限长序列的频谱（DTFT）在频域采样足够多的点，可以无失真地恢复原序列。

问题提出：设 $x[n]$ 是长度为 $M$ 的有限长序列（$x[n]=0$，$n$ 在 $[0, M-1]$ 之外），其 DTFT 为 $X(e^{j\omega})$。在 $N$ 个等间隔频点 $\omega_k=2\pi k/N$ 上对 $X(e^{j\omega})$ 采样，得到 $X[k]=X(e^{j2\pi k/N})$。问：$N$ 至少取多少，才能从 $X[k]$ 无失真地恢复 $x[n]$？

定理内容：当频域采样点数 $N \ge M$ 时，IDFT 可以精确恢复原序列：

当 $N < M$ 时，恢复出的序列发生时域混叠（aliasing），无法无失真恢复。

推导：对 DTFT 做频域采样得到 $X[k]$，再做 IDFT，得到的序列 $x_N[n]$ 是原序列 $x[n]$ 的周期延拓再取主值：

其中 $R_N[n]$ 是长度为 $N$ 的矩形窗。当 $N \ge M$ 时，平移后的副本 $x[n+rN]$（$r \ne 0$）完全落在窗外，不与主值区间重叠，因此 $x_N[n] = x[n]$，无混叠。当 $N < M$ 时，相邻周期的序列尾部会折叠进主值区间，产生时域混叠。

频域采样定理的工程意义：

• DFT 的本质就是频域采样：$N$ 点 DFT 就是对 DTFT 在 $N$ 个等间隔频点上采样。只要 $N \ge M$，DFT 包含了原序列的全部信息，IDFT 可以完美重建。
• 补零不增加信息：$N > M$ 时（末尾补零），频域采样更密，但重建出的序列只是原序列后面加了零，没有新的时域信息。
• 截断会丢失信息：$N < M$ 时，频域采样不够密，IDFT 恢复的序列发生时域混叠，是原序列的失真版本。具体例子见本章末尾例题区。

4.4 频域内插：DFT 频点之间是什么？

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 页…

4.5 Z 域内插：从 DFT 重建完整 Z 变换

4.4 节给出的是单位圆上的内插——用 $N$ 个 $X[k]$ 重建 $X(e^{j\omega})$。如果把 $z$ 放到整个 Z 平面，DFT 同样可以重建完整的 Z 变换 $X(z)$。这就是 Z 域内插公式，有时也叫DFT 的 Z 域重建公式。

推导：从 IDFT $x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]W_N^{-kn}$ 出发，代入 Z 变换：

对有限项几何级数求和，利用 $W_N^{-kN}=e^{j2\pi k}=1$：

由于分子 $1-z^{-N}$ 与 $k$ 无关，可以提到求和号外，即得 Z 域内插公式。

与频域内插公式的关系：令 $z=e^{j\omega}$，分子变为 $1-e^{-jN\omega}$，分母变为 $1-W_N^{-k}e^{-j\omega}=1-e^{-j(\omega-2\pi k/N)}$。整理后正是 4.4 节的频域内插函数 $\phi(\omega)$。所以 Z 域内插公式是频域内插公式的 Z 平面推广，后者只是前者在单位圆上的特例。

例题区

5.1 直接计算 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)$ 地算，它在工程中几乎没用。

5.2 减少运算量的途径

直接计算 DFT 之所以慢，是因为每一个 $X[k]$ 都独立地遍历所有 $N$ 个 $x[n]$，各 $X[k]$ 之间没有共享任何中间结果。FFT 的核心突破就是：利用旋转因子 $W_N$ 的性质，让不同的 $X[k]$ 共享计算。

旋转因子 $W_N=e^{-j2\pi/N}$ 有两个关键性质：

这意味着：如果我们把 $N$ 点 DFT 拆成两个 $N/2$ 点 DFT，它们的旋转因子从 $W_N$ 变成 $W_{N/2}$，恰好可以利用 $W_N^2=W_{N/2}$ 复用已有计算。这就是分治的起点。

FFT 的两条路线：DIT 与 DIF

分治的关键问题是："拆什么？" DFT 有输入端（时域 $x[n]$）和输出端（频域 $X[k]$），两侧都可以拆。

两者运算量完全相同（$\frac{N}{2}\log_2 N$ 次复乘），只是分解视角不同。下面先讲 DIT（教材主线），再讲 DIF（对偶形式）。

5.3 按时间抽取（DIT）基 2 FFT

5.3.1 分解推导

要求 $N=2^M$。思路：把输入序列按偶数和奇数下标拆成两组，分别做 $N/2$ 点 DFT，再用一层合成得到完整的 $N$ 点 DFT。

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

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

$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$，得

5.3.2 蝶形运算

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

$O[k] \xrightarrow{\times W_N^k} W_N^k O[k] \longrightarrow \begin{cases} E[k]+W_N^k O[k] = X[k] \\ E[k]-W_N^k O[k] = X[k{+}M] \end{cases}$

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

PDF计算工作量分析：一次分解使计算量减半p.13

正在渲染 PDF 第 13 页…

5.3.3 $N=8$ DIT 的完整分解过程

以 $N=8$ 为例，展示 DIT FFT 的三层分解。

PDFN=8 DFT 分解为两个 N/4=4 点 DFTp.14

正在渲染 PDF 第 14 页…

第一层：$8\to 4+4$

偶数序列 $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\to 2+2$（对 $X_1$ 和 $X_2$ 各做一次）

对 $X_1$：偶偶序列 $x[0],x[4]$ 做 2 点 DFT，偶奇序列 $x[2],x[6]$ 做 2 点 DFT，用 $W_4$ 合成。

对 $X_2$：奇偶序列 $x[1],x[5]$ 做 2 点 DFT，奇奇序列 $x[3],x[7]$ 做 2 点 DFT，用 $W_4$ 合成。

第三层：$2\to 1+1$，2 点 DFT 就是一个无旋转因子的蝶形：$X[0]=a+b$，$X[1]=a-b$。

PDF蝶形合成公式p.15

正在渲染 PDF 第 15 页…

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

正在渲染 PDF 第 16 页…

5.3.4 码位倒读（Bit-Reversal）：为什么会这样？

逐层追踪 $N=8$ 的输入重排

原始输入：$x[0],x[1],x[2],x[3],x[4],x[5],x[6],x[7]$，下标二进制：$000,001,010,011,100,101,110,111$。

第一层拆分——按最低位（LSB）分组：

• 偶数（LSB=0）：$x[0]_{000},\,x[2]_{010},\,x[4]_{100},\,x[6]_{110}$
• 奇数（LSB=1）：$x[1]_{001},\,x[3]_{011},\,x[5]_{101},\,x[7]_{111}$

第二层拆分——在每组内按次低位分组：

• 偶偶（最低两位=00）：$x[0]_{000},\,x[4]_{100}$
• 偶奇（最低两位=10）：$x[2]_{010},\,x[6]_{110}$
• 奇偶（最低两位=01）：$x[1]_{001},\,x[5]_{101}$
• 奇奇（最低两位=11）：$x[3]_{011},\,x[7]_{111}$

最终排列（从上到下）：

结论：第一层拆分按最低位分，第二层按次低位分，第三层按最高位分。最终排列顺序恰好是把原始下标的二进制位从右到左读，即码位倒读（Bit-Reversal）。

Bit-reversal 的对合性：位反转操作做两次就回到原序（$(i^R)^R = i$），所以只需交换每一对 $(i,\,i^R)$ 即可原地完成重排，不需要额外数组。

5.3.5 原位计算（In-Place Computation）

FFT 的原地特性意味着所有中间结果直接覆盖原数组位置，无需额外存储空间——$N$ 点 FFT 只需 $O(N)$ 的存储。这是因为每一级蝶形运算的输出对 $(X[k],X[k+M])$ 恰好写入输入对 $(E[k],O[k])$ 原来的位置，不会影响其他蝶形的输入。

PDF原位运算与可并行性p.29

正在渲染 PDF 第 29 页…

5.4 按频率抽取（DIF）基 2 FFT

DIF 是 DIT 的对偶形式。DIT 对输入按 $n$ 的奇偶分组（拆时间端），DIF 对输出按 $k$ 的奇偶分组（拆频率端）。两者殊途同归，算出来的 $X[k]$ 完全一样。

5.4.1 分解推导

将 $N$ 点 DFT 的求和拆成前半段和后半段：

利用 $W_N^{kN/2}=(-1)^k$，分 $k$ 的奇偶讨论：

偶数频点 $k=2r$：此时 $(-1)^k=1$：

这正是 $N/2$ 点 DFT，输入是前半段与后半段之和 $a[n]=x[n]+x[n+N/2]$。

奇数频点 $k=2r+1$：此时 $(-1)^k=-1$：

这也是 $N/2$ 点 DFT，输入是差值乘旋转因子 $b[n]=(x[n]-x[n+N/2])W_N^n$。

5.4.2 DIF 蝶形与信号流图

DIF 的蝶形与 DIT 不同：先加减，后乘旋转因子。

递归分解到 2 点 DFT 后，$X[k]$ 按码位倒读顺序排列——这次不是输入端，而是输出端需要 bit-reversal 重排。

PDFDIF-FFT 分解推导 · p.31–32p.31–32

正在渲染 PDF 第 31 页…

正在渲染 PDF 第 32 页…

PDF8 点 DIF-FFT 完整信号流图p.49

正在渲染 PDF 第 49 页…

5.5 DIT 与 DIF 的完整对比

5.6 运算量与存储

5.7 IFFT：用 FFT 算逆变换

IDFT 的定义是 $x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]\,W_N^{-kn}$。与 DFT 相比只差两点：旋转因子取共轭 $W_N^{-kn}$，结果除以 $N$。因此可以用同一个 FFT 硬件/程序实现 IFFT：

步骤：输入取共轭 → 做 FFT → 输出取共轭 → 除以 $N$。这种"共轭 Trick"让所有 FFT 的优化技术自动适用于 IFFT。

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

正在渲染 PDF 第 26 页…

PDF进一步分解到 N/4 点 DFTp.19

正在渲染 PDF 第 19 页…

5.8 其他 FFT 算法（了解）

当 $N$ 不是 2 的幂时，Radix-2 无法直接使用。但分治思想仍然适用：

• Mixed Radix：若 $N$ 可以分解为多个小素因子（如 $N=2^a\times 3^b\times 5^c$），可以用多基 Cooley-Tukey 分解。
• Rader's algorithm：将素数长度 $N$ 的 DFT 转化为长度 $N-1$ 的循环卷积，再用 FFT 计算。
• Bluestein's algorithm（chirp-Z 变换）：将任意长度 $N$ 的 DFT 转化为 2 的幂长度的卷积。

5.9 频谱分析、滤波与 STFT

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

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

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

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

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

例题区

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

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