快速傅里叶变更（FFT）：从数学公式到5G信号，揭开数字天下的“频率密码”
你是否想过，为什么手性能刹时解码WiFi信号？为什么音乐APP能一键分离人声和伴奏？答案就藏在快速傅里叶变更（FFT）这个“数字魔法”中。它不但是20世纪十大算法之一，更是现代通信、音频处置惩罚、图像识别的核心引擎。今天，我们详细介绍一下FFT。
一、穿越200年的数学革命：从傅里叶到FFT
1807年，法国数学家傅里叶提出一个疯狂设想：任何复杂波形都能分解为不同频率的正弦波组合。
连续傅里叶变更的公式为：
https://i-blog.csdnimg.cn/direct/d555d1fa735c4a3099a2244a7671528b.jpg
但现实中信号是离散的，于是有了离散傅里叶变更（DFT）：
https://i-blog.csdnimg.cn/direct/09a25e0740ea4afc8d522b1132e1887d.jpg
但传统傅里叶变更计算量惊人——分析1秒音乐需要做N^2次运算（N=采样点数）。
1965年，库利（Cooley）和图基（Tukey）发明FFT算法，将计算复杂度暴降至 NlogN。
举个栗子：处置惩罚100万点数据，传统方法需1万亿次运算，FFT仅需2000万次！
二、3分钟搞懂FFT核心原理
1、时空穿梭术：时域与频域
时域：我们看到的声音波形、心电图都是时间维度的信号。
频域：隐蔽着构成这个信号的所有频率成分，就像光的棱镜分色 。
DFT和FFT就是连接两个天下的「任意门」。
2、分而治之的魔法
FFT的核心是库利-图基算法，它将DFT分解为奇偶序列的递归计算，利用旋转因子
https://i-blog.csdnimg.cn/20230724024159.png?be=1&origin_url=https://mmbiz.qpic.cn/sz_mmbiz_png/KCchXsd1ZzTvInjmygqqdVI1bGjOpmSC1KkTKnJlFv90mjP0ELeouQUdtgiaR6rMkdKXl2SLQojbsicaU15KqvNg/640?wx_fmt=png&tp=wxpic&wxfrom=5&wx_lazy=1&wx_co=1
的对称性
https://i-blog.csdnimg.cn/20230724024159.png?be=1&origin_url=https://mmbiz.qpic.cn/sz_mmbiz_png/KCchXsd1ZzTvInjmygqqdVI1bGjOpmSCa08wHt6AIib6Xviap6tvibu2vF9J1p3icBD19w3Q1LcX4prhXdGicvNHBVg/640?wx_fmt=png&tp=wxpic&wxfrom=5&wx_lazy=1&wx_co=1
可大幅淘汰重复计算。
（1）分治：将大问题拆解为小问题
假设N=2^m，将序列x(n)分为偶数项和奇数项：
https://i-blog.csdnimg.cn/direct/6aaa1fbbd2a941bd81b9210975c09e3c.jpg
递归分解后，最终只需计算长度为1的DFT（即自身）。
（2）蝶形运算：高效合并结果
每一层递归的合并通过蝶形运算完成：
https://i-blog.csdnimg.cn/direct/20136588d4ca4e83bbf11dcedf8e69b4.jpg
这一操纵将计算量从N^2降为N log2 N。例如，N=1024时，计算量淘汰约100倍！
这种递归策略让计算量呈指数级降落，过程宛如乐高积木的精妙拼接，以8点FFT为例。
https://i-blog.csdnimg.cn/direct/cd93d043efe4417dabdb7ca80776898d.jpg
3、8点FFT计算示例
输入序列：假设输入为实数序列 x(n) = ，例如取x(n) = 。
步调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)' =
步调2：分阶段蝶形运算
8点FFT需3个阶段，每阶段包含4次蝶形运算。
https://i-blog.csdnimg.cn/direct/51e5bf5f5c624845ae545a31d4371e66.jpg
https://i-blog.csdnimg.cn/direct/9f8af6125454402ab469849fc09fd077.jpg
https://i-blog.csdnimg.cn/direct/df78a37ab16c4cd3869f09135ad4b088.jpg
三、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-t)
# 绘制频谱图
plt.plot(freq[:512], np.abs(X[:512])) # 只取前一半（对称）
plt.xlabel('频率(Hz)'); plt.ylabel('强度'); plt.title('你的声音指纹')
运行这段代码，你会看到两个清楚的峰——正是50Hz和80Hz的成分！
https://i-blog.csdnimg.cn/direct/5312bbe0c08c4ea4b4e5011726b94729.jpg
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]