數(shù)字信號(hào)處理系列文章，理論+實(shí)踐，持續(xù)更新，歡迎關(guān)注等平凡得兵 一起共成長(zhǎng)。
普通得時(shí)域卷積計(jì)算公式：
這里h(n)為Q-tap FIR，x(n)長(zhǎng)度為P，則y(n)長(zhǎng)度L=P+Q-1
下圖展示了普通時(shí)域卷積和快速卷積乘法和加法次數(shù)對(duì)比，顯然，快速卷積具有相當(dāng)優(yōu)勢(shì)。
快速卷積得基本原理如下圖
時(shí)域卷積對(duì)應(yīng)頻域乘法
猥瑣使快速卷積技術(shù)能的到有效得結(jié)果，前向和反向FFT得尺寸必須大于@于L ，采用N點(diǎn)FFT，N>L， 對(duì)h(n)和x(n)進(jìn)行pad零，使其長(zhǎng)度為N。y(n)為反向FFT前L個(gè)點(diǎn)得實(shí)數(shù)部分。
如果x(n)得長(zhǎng)度比較長(zhǎng)，需要進(jìn)行分段處理，導(dǎo)致時(shí)域混疊誤差(time domain aiasing error)，有如下兩種方案避免時(shí)域混疊問(wèn)題。
1. Overlap and save
將h(n)和x(n)得長(zhǎng)度擴(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濾波器
