专题进阶 · 信号处理推荐总顺序 · 第 117 / 148 课

把 DFT 按奇偶下标分治,推导蝶形合并与 O(N log N) 成本。

先学会这些,再进入本课 离散傅里叶变换 递归与调用栈
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 信号处理

快速傅里叶变换FFT

利用单位根对称性分治计算 DFT,常见实现复杂度 O(N log N)。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

把 DFT 按奇偶下标分治,推导蝶形合并与 O(N log N) 成本。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

直接 DFT 重复计算很多相关旋转项。N 是 2 的幂时,如何把一个 N 点变换拆成两个 N/2 点变换?

02一步步得到方法

按输入下标奇偶拆分求和

把 x[2m] 与 x[2m+1] 分开。前者得到 N/2 点 DFT E[k],后者得到 O[k],但奇项额外乘旋转因子 W_N^k。于是 X[k]=E[k]+W_N^kO[k]。

利用 W_N^(k+N/2)=−W_N^k,同一对 E、O 还给出 X[k+N/2]=E[k]−W_N^kO[k]。一次乘法和一加一减产生两个输出,这就是蝶形合并。

规模递减与输出索引

继续对偶、奇子序列递归,直到长度 1 原样返回。每层合并总工作 O(N),共 log₂N 层,因此 T(N)=2T(N/2)+O(N)=O(N log N)。

这里实现 radix-2,要求长度是 2 的幂。一般 FFT 库还支持其他分解、混合基数或 Bluestein 算法;不能据此说 FFT 数学上只能处理二次幂长度。

从 DFT 公式拆出两个半长问题

把求和下标分成偶数和奇数,偶数部分成为半长 DFT,奇数部分也是半长 DFT 再乘旋转因子。频率相差 N/2 时旋转因子变号,因此一对加减就产生两个输出。

这个蝶形组合使递推为 T(N)=2T(N/2)+O(N),得到 O(N log N)。FFT 是计算 DFT 的一类快速算法,基2版本要求二次幂长度,其他长度可用不同分解而非宣称不能做傅里叶变换。

03把一个小例子完全算清楚

x=[1,2,3,4]。

步骤计算与状态为什么这样做
偶序列 [1,3]E=[4,−2]2 点 DFT
奇序列 [2,4]O=[6,−2]另一半
k=0X₀=4+6=10,X₂=4−6=−2W⁰=1
k=1X₁=−2+2i,X₃=−2−2iW¹=−i

窄屏可左右滑动表格,阅读完整计算与理由。

同一组子变换被复用,结果与直接 DFT 一致。

04为什么这个方法成立

  1. 奇偶拆分只是把原求和重新分组,没有近似。
  2. 单位根对称性使一对子结果同时贡献两个正确输出。
  3. 子变换递归正确,合并公式保持 DFT 定义,归纳得到全变换。

05把推导翻译成代码

Python · 可独立运行的教学实现

import cmath
from math import pi
def fft(x):
    n = len(x)
    if n == 0: return []
    if n & (n-1): raise ValueError("power-of-two length required")
    if n == 1: return [complex(x[0])]
    even,odd = fft(x[::2]),fft(x[1::2])
    output = [0j]*n
    for k in range(n//2):
        value = cmath.exp(-2j*pi*k/n)*odd[k]
        output[k] = even[k]+value
        output[k+n//2] = even[k]-value
    return output

逐个理解关键决定

fft(x[::2]),fft(x[1::2])
分的是下标奇偶,不是数组前半与后半。
output[k+n//2]
第二个频率利用同一蝶形乘积取负号。

06时间、空间与实现范围

时间 O(N log N),此递归切片教学实现峰值工作存储 O(N),调用深度 O(log N),累计分配量可更大。

高性能版本常用迭代原地布局、预计算旋转因子和向量化,数学结果相同但实现成本不同。

07改变条件,检查哪里会出错

把每层合并也重新做完整 DFT

会丢失分治复用,无法得到快速算法的复杂度。

补零后仍把频率索引当原长度解释

补零改变离散频率网格,不能凭增加点数声称恢复了额外观测信息。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

N=8 有几层非平凡分解?

需要一点提示

8→4→2→1。

查看解析与答案

3 层。

练习 2 · 边界与辨析

长度 6 本代码能运行吗?

需要一点提示

检查二次幂条件。

查看解析与答案

会明确拒绝;可换支持该长度的 FFT 实现,不能无解释地把信号截断。

练习 3 · 变式与迁移

补零到 8 后是否增加真实信号信息?

需要一点提示

新增样本是什么?

查看解析与答案

没有,只改变变换采样网格与计算长度;频谱分辨能力仍受实际观测时长等条件影响。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 科学计算与 FFT 代码

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。