你是否想过，为什么手机能瞬间解码WiFi信号？为什么音乐APP能一键分离人声和伴奏？答案就藏在快速傅里叶变换（FFT）这个“数字魔法”中。它不仅是20世纪十大算法之一，更是现代通信、音频处理、图像识别的核心引擎。
今天，我们详细介绍一下FFT。
一、穿越200年的数学革命：从傅里叶到FFT
1807年，法国数学家傅里叶提出一个疯狂设想：任何复杂波形都能分解为不同频率的正弦波组合。
连续傅里叶变换的公式为：
但现实中信号是离散的，于是有了离散傅里叶变换（DFT）：
但传统傅里叶变换计算量惊人——分析1秒音乐需要做N^2次运算（N=采样点数）。
1965年，库利（Cooley）和图基（Tukey）发明FFT算法，将计算复杂度暴降至 NlogN。
举个栗子：处理100万点数据，传统方法需1万亿次运算，FFT仅需2000万次！
二、3分钟搞懂FFT核心原理
1、时空穿梭术：时域与频域
时域：我们看到的声音波形、心电图都是时间维度的信号。
频域：隐藏着构成这个信号的所有频率成分，就像光的棱镜分色 。
DFT和FFT就是连接两个世界的「任意门」。
2、分而治之的魔法
FFT的核心是库利-图基算法，它将DFT分解为奇偶序列的递归计算，利用旋转因子
的对称性
可大幅减少重复计算。
（1）分治：将大问题拆解为小问题
假设N=2^m，将序列x(n)分为偶数项和奇数项：
递归分解后，最终只需计算长度为1的DFT（即自身）。
（2）蝶形运算：高效合并结果
每一层递归的合并通过蝶形运算完成：
这一操作将计算量从N^2降为N log2 N。例如，N=1024时，计算量减少约100倍！
这种递归策略让计算量呈指数级下降，过程宛如乐高积木的精妙拼接，以8点FFT为例。
3、8点FFT计算示例
输入序列：假设输入为实数序列 x(n) = [x0, x1, x2, x3, x4, x5, x6, x7]，例如取x(n) = [0, 1, 2, 3, 4, 5, 6, 7]。
步骤1：比特反转重排
将索引二进制位反转后重排输入序列：
原索引：
0(000),1(001),2(010),3(011),4(100),5(101),6(110),7(111)
码位倒置后：
0(000),4(100),2(010),6(110),1(001),5(101),3(011),7(111)
倒置后序列：
x(n)' = [0, 4, 2, 6, 1, 5, 3, 7]
步骤2：分阶段蝶形运算
8点FFT需3个阶段，每阶段包含4次蝶形运算。
三、Python实战：用10行代码绘制频谱图
import numpy as np
import matplotlib.pyplot as plt
# 生成混合信号（50Hz+80Hz）
t = np.linspace(0, 1, 1024)
x = np.sin(2*np.pi*50*t) + 0.5*np.sin(2*np.pi*80*t)
# FFT一键转换
X = np.fft.fft(x)
freq = np.fft.fftfreq(1024, t[1]-t[0])
# 绘制频谱图
plt.plot(freq[:512], np.abs(X[:512])) # 只取前一半（对称）
plt.xlabel('频率(Hz)'); plt.ylabel('强度'); plt.title('你的声音指纹')
运行这段代码，你会看到两个清晰的峰——正是50Hz和80Hz的成分！
