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

本节介绍离散傅里叶逆变换（IDFT）及其快速算法（IFFT）。

本节介绍离散傅里叶逆变换（IDFT）及其快速算法（IFFT）。IFFT的推导与FFT类似，利用旋转因子的周期性和对称性逐级分解以减少计算量；实现上只需将FFT的旋转因子取共轭，并在最后将结果整体除以N，蝶形结构与位序重排方法不变。

随后讲解如何用FFT与IFFT实现频域均衡器。相比时域的IIR/FIR滤波器，频域均衡器无相位误差和延迟，且段数增加不会加大运算量。实现流程是：将音频分块做FFT转到频域，按用户设定的分贝值计算叠加量（实部按0.75、虚部按0.25的权重分配），再用三次样条曲线插值使各频段中心到边缘的增益平滑过渡，最后经IFFT还原到时域。处理中需防止信号越界产生杂音，越界值直接截为最大值。文中给出一个仿Foobar的18段均衡器演示程序。