《算法的乐趣》第四十七节

本节讲解快速傅里叶变换（FFT）的核心原理与实现思路。FFT利用旋转因子的周期性和对称性，采用分治策略，将N点离散傅里叶变换（DFT）递归分解为多个N/2点的DFT……

本节讲解快速傅里叶变换（FFT）的核心原理与实现思路。FFT利用旋转因子的周期性和对称性，采用分治策略，将N点离散傅里叶变换（DFT）递归分解为多个N/2点的DFT，从而大幅降低运算量。以基2算法为例，每次分解将原始信号按序号奇偶分成两组，通过蝶形运算建立子变换与原变换的映射关系。蝶形运算会改变数据位置，因此需要按码位倒序规律（即序号二进制反读）对输入或输出进行重排。算法实现时，通常预先计算好旋转因子的正弦、余弦值表供查表使用。

在应用层面，本节介绍了频域数据的特点：采样率和变换点数共同决定频率分辨率，频域数据前后各半呈对称，计算功率谱只需取前一半。将音频PCM数据转为复数（虚部为0）后即可进行变换。由于计算机只能处理有限长数据，需对信号分段截取，这会造成频谱能量泄露，通常使用窗函数对信号截断来减少这种泄露。