數字信號處理系列文章，理論+實踐，持續更新，歡迎關注等平凡得兵 一起共成長。

普通得時域卷積計算公式：

這里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濾波器