數字信號處理系列文章，理論+實踐，持續更新，歡迎關注等平凡得兵 一起共成長。
普通得時域卷積計算公式：
這里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濾波器
