反饋

重疊-相加之卷積法

重疊-相加之卷積法 ( Overlap-add method ) 是一種區塊卷積 ( block convolution, sectioned convolution )，可以有效的計算一個很長的信號 x[n] 和一個 FIR 濾波器 h[n] 的離散卷積。

中文名: 重疊-相加之卷積法

外文名: Overlap–add method
分組: 數理科學

重疊-相加之卷積法形式

其中h[m] 在 [1,M] 之外為零。

重疊-相加之卷積法算出重疊的輸出區塊；另一種區塊卷積的作法，重疊-存儲之卷積法則是將輸入區塊重疊。

重疊-相加之卷積法算法

概念上，這個做法是選用一個較短的適當長度L來切割x[n] ，計算x[n] 的子數列濾波後的結果y_k[n] ，然後連接起來成為y[n] 。並考慮到一個長度

和長度

的有限長度離散信號，做卷積之後會成為長度

的信號。

則

而因為卷積是線性時不變運算，所以y[n] 可被表示為

其中

在 [1,L+M-1] 之外為零。每個y_k[n] 長度

，以間隔

位移後相加，所以輸出是由互相重疊的區塊相加而成，因此稱為重疊-相加之卷積法^[1] 。

儘管一時看不出切割成區塊的好處為何，但考慮到對任何

以上每段的卷積都等價於

和

做

點循環卷積，不夠的部分補上零 (zero-padding)。如此一來因為循環卷積可以藉由循環卷積定理

變換成三次

點快速傅里葉變換和

次乘法，使原本每段O(N) 的運算量減少至O(NlogN)，速度大幅增加。

重疊-相加之卷積法偽代碼

  Algorithm (OA for linear convolution)   Evaluate the best value of N and L   H = FFT(h,N)       (zero-padded FFT)   i = 1   while i <= Nx       il = min(i+L-1,Nx)       yt = IFFT( FFT(x(i:il),N) * H, N)       k  = min(i+N-1,Nx)       y(i:k) = y(i:k) + yt    (add the overlapped output blocks)       i = i+L   end

重疊-相加之卷積法區塊長度的選擇

當x[n] 的長度N'和h[n] 的長度M相差太大時（例如M< log₂N'），直接卷積（不透過循環卷積和FFT）反而最快。而當N'和M差不多在同一個數量級時，不用分區，也就是隻有一塊長度L=N'的區塊去做 FFT 即可。而當N'比M大了不少，卻沒大太多時，區塊長度L就需要選擇。除了與N'和M相關以外，也要考慮當兩者相除有餘數時，剩下一小段的輸入可能會造成浪費。

重疊-相加之卷積法相關條目

參考資料

1. Rahman M R, Thulasiram R K, Thulasiraman P. Wavelet Optimized Finite-Difference Approach to Solve Jump-Diffusion type Partial Differential Equation for Option Pricing[J]. Computing in Economics & Finance, 2005.

詞條統計

瀏覽次數：次
編輯次數：2次歷史版本
最近更新：双鱼雨后彩虹12 （2022-01-12）

1 形式
2 算法
3 偽代碼
4 區塊長度的選擇
5 相關條目