一文读懂基于FFT的快速FIR 快速fft变换

数字信号处理系列文章，理论+实践，持续更新，欢迎关注@平凡的兵 一起共成长。

普通的时域卷积计算公式：

这里h(n)为Q-tap FIR，x(n)长度为P，则y(n)长度L=P+Q-1

下图展示了普通时域卷积和快速卷积乘法和加法次数对比，显然，快速卷积具有相当优势。

快速卷积的基本原理如下图

时域卷积对应频域乘法

为了使快速卷积技术能得到有效的结果，前向和反向FFT的尺寸必须大于等于L ，采用N点FFT，N>L， 对h(n)和x(n)进行pad零，使其长度为N。y(n)为反向FFT前L个点的实数部分。

如果x(n)的长度比较长，需要进行分段处理，导致时域混叠误差(time domain aiasing error)，有如下两种方案避免时域混叠问题。

1. Overlap and save

将h(n)和x(n)的长度扩充为N，不够部分补零，N=Q-1+M， 如下图，进行FFT逆变换，只保留M samples。

2. Overlap and add

参考资料

[1] Understanding digital signal processing

[2] 使用FFT进行快速FIR滤波_大饼博士_cqqian的博客-CSDN博客_fft实现fir滤波器