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=0 | X₀=4+6=10,X₂=4−6=−2 | W⁰=1 |
| k=1 | X₁=−2+2i,X₃=−2−2i | W¹=−i |
窄屏可左右滑动表格,阅读完整计算与理由。
同一组子变换被复用,结果与直接 DFT 一致。
04为什么这个方法成立
- 奇偶拆分只是把原求和重新分组,没有近似。
- 单位根对称性使一对子结果同时贡献两个正确输出。
- 子变换递归正确,合并公式保持 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
N=8 有几层非平凡分解?
需要一点提示
8→4→2→1。
查看解析与答案
3 层。
长度 6 本代码能运行吗?
需要一点提示
检查二次幂条件。
查看解析与答案
会明确拒绝;可换支持该长度的 FFT 实现,不能无解释地把信号截断。
补零到 8 后是否增加真实信号信息?
需要一点提示
新增样本是什么?
查看解析与答案
没有,只改变变换采样网格与计算长度;频谱分辨能力仍受实际观测时长等条件影响。