快速傅里叶变换（FFT）：从数学公式到5G信号，揭开数字世界的“频率密码”

快速傅里叶变换（FFT）：从数学公式到5G信号，揭开数字世界的“频率密码”

快速傅里叶变换（FFT）是20世纪最重要的算法之一，它不仅极大地提高了信号处理的效率，更是现代通信、音频处理、图像识别等领域的核心技术。本文将从数学公式到实际应用，为你揭开数字世界的“频率密码”。

在1807年，法国数学家傅里叶提出一个惊人的设想：任何复杂的波形都可以分解为不同频率的正弦波组合。这一理论为后来的信号处理奠定了基础。然而，传统的傅里叶变换计算量巨大，分析1秒音乐需要做N^2次运算（N为采样点数）。直到1965年，库利（Cooley）和图基（Tukey）发明了FFT算法，将计算复杂度降低至NlogN，才使得傅里叶变换在实际应用中成为可能。

一、穿越200年的数学革命：从傅里叶到FFT

连续傅里叶变换的公式为：

但现实中信号是离散的，于是有了离散傅里叶变换（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('你的声音指纹')
plt.show()

运行这段代码，你会看到两个清晰的峰——正是50Hz和80Hz的成分！