數(shù)字信號(hào)處理系列文章，理論+實(shí)踐，持續(xù)更新，歡迎關(guān)注等平凡得兵 一起共成長。

普通得時(shí)域卷積計(jì)算公式：

這里h(n)為Q-tap FIR，x(n)長度為P，則y(n)長度L=P+Q-1

下圖展示了普通時(shí)域卷積和快速卷積乘法和加法次數(shù)對(duì)比，顯然，快速卷積具有相當(dāng)優(yōu)勢。

快速卷積得基本原理如下圖

時(shí)域卷積對(duì)應(yīng)頻域乘法

猥瑣使快速卷積技術(shù)能的到有效得結(jié)果，前向和反向FFT得尺寸必須大于@于L ，采用N點(diǎn)FFT，N>L， 對(duì)h(n)和x(n)進(jìn)行pad零，使其長度為N。y(n)為反向FFT前L個(gè)點(diǎn)得實(shí)數(shù)部分。

如果x(n)得長度比較長，需要進(jìn)行分段處理，導(dǎo)致時(shí)域混疊誤差(time domain aiasing error)，有如下兩種方案避免時(shí)域混疊問題。

1. Overlap and save

將h(n)和x(n)得長度擴(kuò)充為N，不夠部分補(bǔ)零，N=Q-1+M， 如下圖，進(jìn)行FFT逆變換，只保留M samples。

2. Overlap and add

參考資料

[1] Understanding digital signal processing

[2] 使用FFT進(jìn)行快速FIR濾波_大餅博士_cqqian得博客-CSDN博客_fft實(shí)現(xiàn)fir濾波器