如果说有哪个算法真正改变了数字信号处理的面貌，快速傅里叶变换（FFT）绝对排在前列。它不只是一个数学工具，更是现代通信、音频、图像、控制系统等领域背后的核心引擎。下面，我们从理论到应用，一层层把它讲透。
理论介绍 & 工程应用
理论介绍
1. 傅里叶变换与离散傅里叶变换
傅里叶变换的原始公式建立在连续函数之上，但计算机只能处理离散数据。所以必须将傅里叶变换离散化，这才有了离散傅里叶变换（DFT）。换句话说，DFT是让傅里叶变换走进数字世界的桥梁。
2. 快速傅里叶变换
快速傅里叶变换（FFT）不是什么新理论——它只是DFT的一种快速算法。数学家们利用DFT的奇偶、虚实等特性，将运算量大幅压了下来。对于计算机系统或数字系统来说，这相当于给DFT装上了涡轮增压器。
举个例子：当采样点数 N = 65536（216）时，直接计算DFT的运算量大约是FFT的4096倍。差距就是这么大。FFT典型的时域二分裂算法如下图所示：
3. 物理意义
任何连续测量的时序信号，都可以看作不同频率正弦波的无限叠加。有些信号在时域上根本看不出什么特征，但变换到频域后，特征一目了然——这也是为什么那么多信号分析非要用FFT不可。
实际中，对一个时域信号采样后，FFT运算得到的就是它的频谱图（频率及对应幅值）。基于这张图，我们可以设计特定的滤波器来滤除噪声频率。比如在飞控设计中，对陀螺仪/加速度信号做频谱分析，滤除机架振动的干扰频率，就能显著降低振动对姿态解算和飞行控制的影响。
工程应用
编程原理
FFT之所以快，说白了就是数学家利用旋转因子W的周期性和对称性，把公式化简再化简。在编程实现中，核心思想是“旧点算新点”——不断用已经算过的结果来推导新的结果。
FFT的采样序列经过拆分抽取，变成一个个蝶形图。以N=8的时间抽取为例：
这个拆分过程也叫码位倒序。倒序后的序列就是蝶形计算的初始序列，如下图左边一列：
把上面的大蝶形拆开看，其实是由一个个小蝶形串并联组成的。单个蝶形的计算过程如下：
后面的蝶形直接使用前面蝶形计算出的节点值，这样一层层循环下去，最终得到完整的频谱数列。至于码位倒序和蝶形图的具体编程实现，网上不乏优质讲解（比如常见的C语言版本），这里就不赘述了。
结果分析
很多人知道FFT能做什么、怎么做，但做完之后结果到底什么意思？该用多少点来做FFT？这两个问题才真正考验理解深度。
从DFT公式出发，输入的是ADC采样值（采样定理要求采样频率 ≥ 2倍信号频率），采样点数N决定了计算规模。N个采样点，FFT之后得到N个点的结果。为了方便计算，N通常取2的整数次幂。计算量是 N·log₂N。
变换后的频谱输出也是N个点，但其中一半是冗余的——真正有用的只有 N/2 + 1 个点（依据采样定理）。
工程应用分析
假设采样频率为 Fs，信号频率为 F，采样点数为 N。FFT的结果是一个N点的复数序列，每个点对应一个频率点，该点的模值就是该频率下的幅度特性。
纵坐标——幅值
设原始信号的峰值为 A，那么FFT结果中除了第一个点（直流分量）外，每个点的模值都是 A 的 N/2 倍。第一个点（直流）的模值是 A 的 N 倍。而每个点的相位，就是该频率分量的初始相位。
横坐标——频率
第一个点代表直流（0 Hz），最后一个点 N 再下一个点代表采样频率 Fs。中间被 N-1 个点均分成 N 等份，每个点的频率依次递增。例如第 n 个点对应的频率为：
Fn = (n-1) × Fs / N
从这个公式能看出来，频率分辨率 = Fs / N。假设采样频率 1024 Hz，采样点数 1024，那么分辨率就是 1 Hz。如果采样点数增加到 2048，分辨率就提高到 0.5 Hz。
想要更高的频率分辨率，就必须增加采样点数——也就是延长采样时间。但在一些实时性要求高的应用里，时间窗口是有限的，这就是现实中的取舍。
举个栗子
假设有一个信号，包含2V直流分量、频率0.5371Hz幅度73V的交流分量、以及频率1.025Hz幅度50V的交流分量。数学表达式为：
S = 2 + 73·sin(2π·0.5371·t) + 50·sin(2π·1.025·t)
用50Hz采样率对该信号采样，取N=1024个点做FFT。根据 Fn = (n-1)×Fs/N，相邻两个频率点之间的间隔是 50/1024 Hz。理想情况下，在三个信号频率对应的点上会出现峰值，其他点接近0（因为离散点的傅里叶频谱是连续的，而DFT只是对连续频谱的采样）。
结果验证了理论——频谱图上三个清晰的峰值，对应着直流、0.5371Hz和1.025Hz的分量。这就是FFT真正的价值：把隐藏在时间序列里的频率成分，清清楚楚地摊开在你面前。