‹ 上一章 第4章 下一章 ›

课程章节导航 ×

CHAPTER 4

快速傅里叶变换
（FFT）

Fast Fourier Transform
课　程数字信号处理（DSP）
学　期2026 年 秋季学期
32 学时24 智能医学
学习要求

本章要掌握什么

  • （1）理解提高离散傅里叶变换运算速度的主要方法；
  • （2）了解时间抽选奇偶分解 FFT 算法；
  • （3）了解频率抽选奇偶分解 FFT 算法；
  • （4）理解快速傅里叶逆变换（IFFT）的概念；
  • （5）掌握线性卷积和线性相关的 FFT 算法。
💡 FFT 不是新的变换，而是 DFT 的高效算法——它把运算量从 O(N²) 降到 O(N log₂N)，直接催生了现代数字信号处理产业。
知识地图

本章知识结构

4.1 提高 DFT 运算速度的主要方法

直接计算量分析 · 利用 \(W_{N}^{kn}\) 的对称性与周期性 · 分解算法

4.2 时间抽选（DIT）FFT

库里-图基算法 · 蝶形运算 · 运算量 · 倒位序

4.3 频率抽选（DIF）FFT · 4.4 IFFT

按 k 奇偶分解 · 与时抽的转置关系 · 用 FFT 算 IFFT

4.5 其他快速算法

复合数 FFT · CZT 线性调频 z 变换

4.6 DCT · 4.7 短时傅里叶变换 · 4.8 应用

离散余弦变换及其性质 · STFT 定义与时频分辨率权衡 · 测振幅谱、测相关函数
4.1 一

直接计算 DFT 的运算量

问题提出

设有限长序列 x(n)，非零值长度为 N，对 x(n) 进行一次 DFT 运算，共需多大的运算工作量？

1. 比较 DFT 与 IDFT 之间的运算量

DFT：\(X\)(\(k\)) = \(\sum_{n=0}^{N-1}\) \(x\)(\(n\))\(W_{N}^{kn}\) IDFT：\(x\)(\(n\)) = \(\frac{1}{N}\) \(\sum_{k=0}^{N-1}\) \(X\)(\(k\))\(W_{N}^{-kn}\)
两者运算量完全相同（只差 W 的符号与一个 1/N 系数），所以只分析 DFT 即可。
4.1 一

DFT 的复数运算量

2. 以 DFT 为例计算复数运算量

计算一个 X(k)（一个频率成分）值，当 k = 1 时：
\(N\) 次复数乘法 ＋ (\(N\)−1) 次复数加法
要完成整个 DFT 运算（N 个 k），其计算量为
\(N\)² 次复数相乘 ＋ \(N\)(\(N\)−1) 次复数加法　≈ O(\(N\)²)
⚠ 结论
运算量与 N² 成正比。N 增大一倍，运算量增为 4 倍——这就是必须改进的原因。
4.1 一

运算量增长有多可怕

复数乘法次数

NDFT（N²）FFT
4164
32102480
12816384448
102410485765120
N = 1024 时，直接计算 DFT 需要一百多万次复数乘法，很难满足实时信号处理的要求。
而用 FFT 只需 5120 次 —— 相差约 205 倍。
这正是 1965 年 Cooley-Tukey 论文被称为"20 世纪最重要的数值算法之一"的原因。
直接 DFT：N²FFT：(N/2)log₂N
4.1 二

改善 DFT 运算速度的基本途径

关键：利用 \(W_{N}^{kn}\) 的固有特性

① 对称性：\(W_{N}^{k+N/2}\) = −\(W_{N}^{k}\) ② 周期性：\(W_{N}^{k+N}\) = \(W_{N}^{k}\) ③ 可约性：\(W_{N}^{rk}\) = \(W_{N/r}^{k}\)
此外 \(W_{N}^{0}\)=1、\(W_{N}^{N/2}\)=−1、\(W_{N}^{N/4}\)=−j 等特殊值可免去乘法。

（3）分解算法

把 N 点 DFT 逐步分解成若干个短序列的 DFT，再组合起来。
分解后复数乘法次数 ≈ (N/2)·log₂N，复数加法次数 ≈ N·log₂N。
4.1 二

例：4 点 DFT 的计算量

直接计算

N=4：共 16 次复数乘法 + 12 次复数加法。
X(\(k\)) = \(\sum_{n=0}^{3}\) \(x\)(\(n\))\(W_{4}^{kn}\)，　\(k\)=0,1,2,3　⇒　4×4=16 次复乘

利用对称性后

将其展开，利用 \(W_{4}^{1}\) = −j、\(W_{4}^{2}\) = −1、\(W_{4}^{3}\) = j 以及 \(W_{4}^{(k+2)n}\) 的关系，合并同类项后：
8 次复数加法 ＋ 2 次复数乘法
复乘从 16 降到 2 —— 这就是 FFT 思想的雏形。
4.2

时间抽选奇偶分解FFT 算法

4.2.1 算法原理（库里-图基算法）

设 N = \(2^{M}\)，把 x(n) 按序号 n 的奇偶分成两组：
偶数组：\(x_{1}\)(\(r\)) = \(x\)(2\(r\)) 奇数组：\(x_{2}\)(\(r\)) = \(x\)(2\(r\)+1) \(r\) = 0,1,…,\(N\)/2−1
于是 N 点 DFT 拆成两个 N/2 点 DFT（分别记 \(X_{1}\)(k)、\(X_{2}\)(k)）。
\(X(k) = X_{1}(k) + W_{N}^{k}X_{2}(k)\) \(X(k+N/2) = X_{1}(k) - W_{N}^{k}X_{2}(k)\)
后 N/2 个点无需重新计算，只需改变符号——利用 N/2 点 DFT 隐藏的周期性，运算量立刻减半。
4.2.1

蝶形运算单元

作图要素（从左向右计算）

  • （1）左边两路为输入；
  • （2）右边两路为输出：右上为相加输出、右下为相减输出；
  • （3）线旁数为加权值（旋转因子 \(W_{N}^{k}\)）。
基本蝶形运算需要 1 次复乘 + 2 次复加。
\(X_{上}\) = \(A\) + \(W\)·\(B\)　，　\(X_{下}\) = \(A\) − \(W\)·\(B\)
A B A+WB A−WB W 加权值 输入 输出 实线 = 相加　虚线 = 经 W 加权（下路相减）
4.2.1 演示

N = 8 时间抽选信号流图（分步演算）

第 0 步：倒位序输入
输入 x(n) = [1, 2, 3, 4, 5, 4, 3, 2]　经倒位序重排后，逐級蝶形运算 → 输出 X(k)（自然序）
4.2.1

N = 8 DIT 流图全貌

x(0)x(4)x(2) x(6)x(1)x(5) x(3)x(7) X(0)X(1)X(2) X(3)X(4)X(5) X(6)X(7) 04 26 15 37 W₈⁰W₈⁰W₈⁰W₈⁰ W₈⁰W₈²W₈⁰W₈² W₈⁰W₈¹W₈²W₈³ 第 1 级第 2 级第 3 级 倒位序输入自然序输出
4.2.2

时间抽选 FFT 的运算量估计

每级都由 N/2 个蝶形单元构成。每一级运算都需要 N/2 次复乘和 N 次复加（每个结加减各一次）。
当 N = \(2^{M}\) 时共分 M = log₂N 级，所以 M 级运算总共需要：
复乘次数：\(\frac{N}{2}\) \(log_{2}N\) 复加次数：\(N\) \(log_{2}N\)
直接 DFT
复乘 N²　复加 N(N−1)　→ O(N²)
FFT
复乘 (N/2)log₂N　复加 N log₂N　→ O(N log₂N)
💡 N=1024 时：DFT 需 1048576 次复乘，FFT 只需 5120 次，加速约 205 倍；N 越大优势越显著。
4.2.3

按时间抽取 FFT 的特点

当 x(n) 长为 N = \(2^{M}\) 时，要进行 M 次奇偶分解，分为 M 级计算。设 L 表示级数，它可以为 1 ~ M 中任意一值。
时间抽取奇偶分解 FFT 算法，其输入序列 x(n) 为倒位序，输出序列为自然序列。

倒位序的定义

将序号 n 写成二进制码，然后将二进制码首尾倒置，再将倒置的二进制码译成十进制数的排列顺序。
例：3 → 011 → 倒置 110 → 6，所以倒位序后第 3 号位置放的是原 x(6)。
4.2.3 演示

倒位序对照演示

点击左侧序号查看 n = 0　000 → 000 → 0
规律：二进制首尾倒置——这正是 DIT 反复"奇偶分组"造成的必然结果（不是人为规定）。
4.2.3

即位运算与"群"的概念

可以"即位运算"：将数据存在存储器内，每一级的运算结果都存入相应存储器，直至最终结果输出。—— 节省内存是 FFT 能实用的关键。

结构规律

  • 每一级包括 N/2 个基本蝶形运算；
  • 第 L 级运算包括 N/\(2^{L}\) 个群，群之间的间隔为 \(2^{L}\)；
  • 同一级中各个群的乘数 W 分布相同，各级共有 \(2^{L-1}\) 个乘数。

群内 W 的规律

每一个群中，W 分布自上而下为 \(W_{N}\) 的从零开始的正整数次幂（即 \(W_{N}^{0}\), \(W_{N}^{1}\), \(W_{N}^{2}\) …）。
级数 L群数 N/\(2^{L}\)群间隔 \(2^{L}\)群系数 \(2^{L-1}\)
1421
2242
3184
（N = 8，M = 3）
4.2.3

基本蝶形运算关系

每个基本蝶形运算关系为

\(X_{L}(i) = X_{L-1}(i) + W_{N}^{p} X_{L-1}(j)\) \(X_{L}(j) = X_{L-1}(i) - W_{N}^{p} X_{L-1}(j)\)
其中 i、j 为该级同一蝶形的上、下节点，p 为对应的旋转因子指数。
★ 时抽（DIT）蝶形的要点
时抽算法先乘后加减：旋转因子 W 乘在下支路上，然后与上路相加 / 相减。这与频抽算法（先加减后乘）恰好相反——两者互为转置。
4.3.1

频率抽选奇偶分解FFT 算法

4.3.1 算法原理

与时抽相反：这次把频域序号 k 按奇偶分项（时域按前后半分开）。
\(X(2r) = \sum_{n=0}^{N/2-1} [x(n)+x(n+N/2)] W_{N/2}^{rn}\) \(X(2r+1) = \sum_{n=0}^{N/2-1} [x(n)-x(n+N/2)] W_{N}^{n} W_{N/2}^{rn}\)

DIF 蝶形：先加减，后乘 W

\(A = x(n) + x(n+N/2)\) \(B = [x(n) - x(n+N/2)]\cdot W_{N}^{n}\)
注意：加权 W 出现在下支路的输出端（先算加减，再乘），与时抽相反。
💡 DIF 输入为自然序，输出为倒位序——与时抽恰好对调。
4.3.1

N = 8 DIF 信号流图

W₈⁰W₈¹W₈²W₈³ W₈⁰W₈²W₈⁰ W₈⁰W₈⁰W₈⁰ x(0)x(1)x(2) x(3)x(4)x(5)· X(0)X(4)X(2) X(6)X(1)X(5) 第 1 级第 2 级第 3 级
FFT 具有 M 级、每级 N/2 个蝶形、计算复杂度 N log₂N。　输出 X(0),X(4),X(2),X(6),X(1)… 呈倒位序排列。
4.3.2

按频率抽取 FFT 的特点

当 x(n) 长为 N = \(2^{M}\) 时，要进行 M 次分解，分为 M 级计算。频率抽取奇偶分解 FFT 算法，其输入序列为自然序列，输出序列为倒序列。
每一级包括 N/2 个基本蝶形运算。
第 L 级运算包括 \(2^{L-1}\) 个群，第 L 级群之间的间隔为 N/\(2^{L-1}\)，L = 1,2,…,M。
群：蝶形图中任一级相互交叉在一起的蝶形。群间隔：按从上到下顺序，上下两个群之间对应元素序号的增量。
同一级中各个群的乘数 W 分布相同，各级共有 N/\(2^{L}\) 个乘数；每个群中 W 自上而下为 \(W_{N}\) 的从零开始的正整数次幂。
级数 L群数 \(2^{L-1}\)群间隔 N/\(2^{L-1}\)群系数 N/\(2^{L}\)
1184
2242
3421
（N = 8，M = 3）
4.3.2

DIF 与 DIT 的转置关系

即位运算，第 L 级蝶形输入间隔为 N/\(2^{L}\)，基本蝶形运算关系为（先加减、后乘 W）。
频率抽选算法与时间抽选算法的蝶形流程图之间存在转置关系。
时间抽选 DIT输入倒位序 → 输出自然序 频率抽选 DIF输入自然序 → 输出倒位序 二者运算量相同都是 O(N log₂N) 转置 等价 把 DIT 流图"左右翻转、输入输出对调、箭头反向"即得 DIF 流图 DIT 先乘后加减　｜　DIF 先加减后乘
4.4

IFFT 方法 1——利用 FFT 计算 IFFT

推导

IDFT：\(x\)(\(n\)) = \(\frac{1}{N}\) \(\sum_{k=0}^{N-1}\) \(X\)(\(k\))\(W_{N}^{-kn}\) 两边取共轭：\(x^{*}\)(\(n\)) = \(\frac{1}{N}\) \(\sum_{k=0}^{N-1}\) \(X^{*}\)(\(k\))\(W_{N}^{kn}\)
右边正好是 \(X^{*}\)(k) 的 DFT！于是
\(x(n) = \frac{1}{N} \{ DFT[X^{*}(k)] \}^{*}\)
★ 步骤
① 把 X(k) 取共轭 → \(X^{*}\)(k)；　② 对它做正 FFT；　③ 结果取共轭；　④ 除以 N。
这样不必另写 IFFT 程序，直接复用同一个 FFT 子程序即可。
4.4

IFFT 方法 2——流图直接反转

还可以把 FFT 流图直接反转用作 IFFT，此时旋转因子取 \(W_{N}^{-k}\)，并在最后除以 N。
由于 DIT 与 DIF 互为转置，于是有两组"共用同一程序"的对应关系：
时抽 FFT 频抽 IFFT 频抽 FFT 时抽 IFFT 使用同一程序 （仅 W 指数取反 + 除 N） 工程实现时不必分别编写 FFT / IFFT，一套代码两边通用
4.5

其他快速算法简介

（1）补零法：基 2-FFT

把序列补零到 2 的整数次幂，再使用基 2-FFT。
补零后不影响频谱形状，只是增加频谱抽样点（让谱线更密）。

（2）任意基 FFT 算法

适用于 N 是一个复合数，即它可以分解成一些因子的乘积（如 N = p·q）。
先把 N 点分解成 p 组，每组 q 点（或反过来），逐级分解。

（3）N 为质数时

如果要求准确的 N 点 DFT，而 N 又是质数，则只能采用直接 DFT 方法，或者用后面将要介绍的 CZT（Chirp z 变换）方法。
4.5.1

复合数FFT 算法

思路

设 N = p · q（复合数）。把 N 点序列先分成 p 组，每组长 q；
对每组做 q 点 DFT，再对组间做 p 点 DFT，中间穿插旋转因子校正。
\( X(k) = \sum_{n_{0}=0}^{q-1} W_{N}^{n_{0}k_{0}} \cdot W_{q}^{n_{0}k_{1}} \cdot \{ \sum_{n_{1}=0}^{p-1} x(n_{1},n_{0}) W_{p}^{n_{1}k_{0}} \}\)
例：N = 18 = 3 × 6，可分为 p = 3 组、每组长 q = 6。
★ 价值
当 N 不是 2 的幂、但可以因式分解时（如 N = 12 = 3×4、N = 18 = 3×6），仍可用 FFT 思想大幅提速，不必退回 O(N²)。
4.5.2

线性调频 z 变换CZT

定义

沿着螺旋线取样计算 z 变换，称其为线性调频 z 变换或 Chirp Z 变换。
沿螺旋线等分角取样，取样点值为
\(z_{k}\) = \(A\)·\(W^{-k}\)，　\(k\) = 0,1,…,\(M\)−1
其中，M 为所要分析复频点的点数；W 和 A 为任意复数。
z 平面上的螺旋取样路径 单位圆 起点 A₀，按 W 等角、等比螺旋前进 CZT 的自由度：起点 A₀、角步长 φ₀、半径比 W₀ 均可任意指定 ⇒ 可只算感兴趣的频段，且频点数 M 不必等于 N DFT 只是 CZT 的特例：A=1、W=e−j2π/N、M=N（单位圆上均匀取样） N 为质数时仍可用 CZT 高效求解
4.5.2

CZT 的计算流程

利用 kn = (k² + n² − (k−n)²)/2 的恒等变形，把 \(z_{k}^{n}\) 拆成两个"线性调频"与一个卷积，从而用 FFT 实现：
x(n) 加权× A−n Wn²/2 FFT 与 h(n) 频域相乘h(n)=W−n²/2 IFFT 再乘 Wk²/2得 X(zk) 核心：把"变步长的复指数求和"化为"卷积"，再用 FFT 计算 → 复杂度 O((N+M)log(N+M))
4.6.1

离散余弦变换DCT

定义

\(X\)(\(k\)) = \(c\)(\(k\)) \(\sum_{n=0}^{N-1}\) \(x\)(\(n\)) cos \(\frac{(2n+1)k\pi}{2N}\)，　\(k\)=0,…,\(N\)−1
其中 c(0) = √(1/N)，c(k) = √(2/N)（k≠0），保证变换矩阵正交归一。
若 x(n) 为实数，DCT 也是实数——这正是它优于 DFT 的地方。
★ 矩阵形式
X = \(C_{N}\) · x　，　\(C_{N}\) 称为归一化正交矩阵
\(C_{N}\) 的行、列之间是正交关系，因此 \(C_{N}^{-1}\) = \(C_{N}^{T}\)，反变换非常简洁。
4.6.1

DCT 反变换IDCT

IDCT 定义

\( x(n) = \sum_{k=0}^{N-1} c(k) X(k) cos \frac{(2n+1)k\pi}{2N} \)
形式上与正变换对称——因为 \(C_{N}\) 是正交矩阵，反变换就是转置。
★ 为什么要用 DCT？
能量集中能力极强：对大多数自然信号（语音、图像），DCT 能把能量压缩到少数低频系数，
且变换结果全为实数——因此成为 JPEG、MPEG、H.26x 等图像/视频压缩标准的核心。
4.6.2

DCT 的性质

1. 线性性质

\(DCT[ax(n) + by(n)] = a\cdot DCT[x(n)] + b\cdot DCT[y(n)]\)

2. 对称性质

DCT 等价于对偶对称延拓后的 2N 点序列做 DFT 再取余弦项，因而具有良好的对称结构。

3. 能量保留定理（帕塞瓦尔）

\(\sum_{n=0}^{N-1} |x(n)|^{2} = \sum_{k=0}^{N-1} |X(k)|^{2}\)
正交变换保持能量不变——所以"丢掉小系数"造成的误差可直接用系数能量度量，便于率失真控制。
4.7.1

短时傅里叶变换STFT

为什么要 STFT？

普通 DFT/FT 只能告诉我们"有哪些频率"，却无法告诉我们这些频率出现在什么时刻。
对于非平稳信号（语音、心电、地震波），这远远不够 —— 需要时频联合分析。

基本思想：加窗 + 滑动

用一个短窗 w(n) 截取信号的一小段，对该段做傅里叶变换；然后沿时间移动窗，重复此过程。
得到的就是随时间变化的频谱——即时频分布。
短时傅里叶变换的定义有两种形式（定义 1 与定义 2），二者等价但解释角度不同。
4.7.1

STFT 的两种定义

定义 1（时域窗移）

\( STFT_{x}(n, \omega) = \sum_{m=-\infty}^{\infty} x(m) w^{*}(m-n) e^{-j\omega m} \)
把窗函数沿时间平移到 n 处，再对加窗后的信号做傅里叶变换。

定义 2（频域调制）

\( STFT_{x}(n, \omega) = e^{-j\omega n} \sum_{m=-\infty}^{\infty} x(m) w^{*}(m-n) e^{j\omega(m-n)} \)
等价地：先把信号解调（搬频）到零频，再与窗做卷积——对应滤波器组解释。
💡 两种定义对应两种物理实现：定义 1 → 逐段做 FFT；定义 2 → 一组带通滤波器并行工作。
4.7.1 演示

窗函数滑动与时频分辨率

窗长 窗长 = 48
窗越短 → 时间分辨率高、频率分辨率低；窗越长 → 频率分辨率高、时间分辨率低。二者相互制约（不确定性原理）。
4.7.1

STFT 的物理解释

定义 1 的物理解释

把信号分段截取，每一段视为"短时平稳"，逐段做傅里叶变换。
直观对应：滑动窗口 + FFT。
输出 = （时间 n，频率 ω）二维函数。

定义 2 的物理解释

对每个频率 ω，先用 \(e^{-j\omega n}\) 把该频带搬移到零频，再与窗函数做低通卷积。
直观对应：带通滤波器组。
每个 ω 对应一个通道，输出即该通道的复包络。
x(n) × w(m−n) 加窗 FFT / DFT X(n, ω) 时频谱 定义 1 的实现：滑动加窗 → 逐帧 FFT → 拼成时频谱（语谱图的原理）
4.7.2

STFT 的性质

1. 线性性质

STFT 是线性变换：
STFT[a·x + b·y] = a·STFT[x] + b·STFT[y]。

2. 频移性质（调制特性）

若 y(n) = x(n)·\(e^{j\omega₀n}\)（频谱搬移），则
\(STFT_{y}\)(n, ω) = \(STFT_{x}\)(n, ω − ω₀)。
时频图沿频率轴整体平移。

3. 时移特性

若 y(n) = x(n − n₀)，则
\(STFT_{y}\)(n, ω) = \(e^{-j\omega n₀}\)·\(STFT_{x}\)(n − n₀, ω)。
时频图沿时间轴平移，并附加线性相位。

4. 共轭对称性

当信号是实信号时，
STFT(n, ω) = \(STFT^{*}\)(n, −ω)。
与时域实信号的傅里叶变换共轭对称一致，只需画 ω ≥ 0 半平面。

5. 由 STFT 恢复信号（完全重构）

在窗函数满足一定条件（如 Σ|w|²≠0）时，可由 STFT完全恢复原信号 x(n)。这保证了时频分析不丢失信息，是滤波器组综合的理论基础。
4.7.3

时间分辨率vs 频率分辨率

第一种极端情况：窗无限长

STFT 退化为信号的傅里叶变换：没有任何时间分辨率，却有最好的频域分辨率。
窗宽 → ∞ 时，加窗等于没加窗，只剩全局频谱。

第二种极端情况：窗无限短（趋近冲激）

STFT 退化为信号本身：有理想的时间分辨率，但不提供任何频率分辨率。
窗宽 → 0 时，每一"段"只剩一个样点，无从谈频率。
⚠ 核心矛盾
时间分辨率取决于窗函数的长度——希望 w(n) 愈短愈好；
频域分辨率取决于窗频谱的宽度——希望窗口尽量宽。
时域分辨率和频域分辨率相互制约，不可兼得。
4.7.4

STFT 的实现方法

1. 用 FFT 计算 STFT

\( X(n, k) = \sum_{m=0}^{N-1} x(m+n) w(m) e^{-j\frac{2\pi}{N}km} \)
式中：n 为帧（时间）序号，k 为频率序号，N 为 FFT 点数。
做法：分帧 → 加窗 → 每帧做 N 点 FFT → 拼接。这就是语谱图的标准生成流程。

2. 用滤波器组法实现 STFT

假设在频率域采样 M 点，采样点的频率为 ω\(_{k}\) = 2πk/M。
则每个 ω\(_{k}\) 对应一个带通滤波器通道：调制 → 与窗卷积（低通）→ 输出复包络。
M 个通道并行，即构成均匀滤波器组。
STFT 一个通道的原理框图（对应频点 ωk） x(n) × e−jωkn 与 w(n) 卷积（低通） 抽取 / 降采样 X(n, ωk) M 个这样的通道并联 即构成完整 STFT 滤波器组
4.8

FFT 实际应用举例

4.8.1 测量系统的振幅谱

对系统输入自功率谱与输入-输出互功率谱做估计，两者相除即得系统频率响应。
|\(H\)(\(e^{j\omega}\))| = \(\frac{|S_{xy}(\omega)|}{S_{xx}(\omega)}\)　（互谱 ÷ 自谱）
其中功率谱用 FFT 快速估计：\(S_{xx}\)(ω) ≈ |X(k)|²（周期图法）。

4.8.2 测量相关函数（相关谱）

利用"相关 ⇔ 频域共轭相乘"，用 FFT 快速算相关：
\(r_{12}(m) = IFFT[X_{1}(k)\cdot X_{2}^{*}(k)]\)
用途：雷达/声纳测距、回声消除、模板匹配、信号时延估计。
小结

第4章核心回顾

为什么需要 FFT

  • 直接 DFT：O(N²) —— N=1024 需百万次复乘
  • 利用 \(W_{N}\) 的对称性、周期性分解
  • FFT：O(N log₂N)，加速数百倍

DIT 与 DIF

  • DIT：输入倒位序、输出自然序；先乘后加减
  • DIF：输入自然序、输出倒位序；先加减后乘
  • 二者互为转置，运算量相同

其他算法

  • IFFT：取共轭 → FFT → 取共轭 → 除 N
  • 复合数 FFT、CZT（螺旋取样，N 可为质数）
  • DCT：实变换、能量集中，JPEG/MPEG 核心

STFT

  • 加窗 + 滑动 → 时频谱
  • 定义 1 → 分帧 FFT；定义 2 → 滤波器组
  • 时域与频域分辨率相互制约
🎯 一句话：FFT 把 DFT 从"算不动"变成"实时可算"；蝶形、倒位序、N log₂N 是它的三个关键词。
演示

理想滤波器 vs 加窗实际（吉布斯）

理想低通是矩形；截断成有限长必加窗，导致通带/阻带波纹（吉布斯现象）。汉宁窗压低旁瓣但加宽主瓣。
N = 21
演示

群延迟：线性相位 vs 非线性相位

群延迟 τ_g(ω)=−dφ/dω。线性相位 FIR 的 τ_g 为常数（无相位失真）；IIR 通常随频率变化。
习题

本章习题

  • 给定差分方程 \(y(n)=0.5y(n-1)+x(n)\)，求系统函数 \(H(z)\) 并判断系统是否稳定。
  • 一阶系统 \(y(n)=x(n)-x(n-1)+\alpha y(n-1)\)，讨论 \(\alpha\) 对幅频特性的影响。
  • 什么是频率采样法？它直接对什么进行采样来设计 FIR 滤波器？
☰大纲
本课大纲 «
← → 翻页 · 空格 下一步 · M 章节 · F 全屏