重疊-相加之摺積法
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
重疊-相加之摺積法 ( Overlap-add method ) 是一種區塊摺積 ( block convolution, sectioned convolution ),可以有效的計算一個很長的信號 x[n] 和一個 FIR 濾波器 h[n] 的離散摺積。
其中 h[m] 在 [1, M] 之外為零。
重疊-相加之摺積法算出重疊的輸出區塊;另一種區塊摺積的作法,重疊-儲存之摺積法則是將輸入區塊重疊。
算法
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/7/77/Depiction_of_overlap-add_algorithm.png)
概念上,這個做法是選用一個較短的適當長度 L 來切割 x[n] ,計算 x[n] 的子數列濾波後的結果 yk[n] ,然後連接起來成為 y[n] 。並考慮到一個長度 和長度 的有限長度離散信號,做摺積之後會成為長度 的信號。
則
其中 在 [1, L+M-1] 之外為零。 每個 yk[n] 長度 ,以間隔 位移後相加,所以輸出是由互相重疊的區塊相加而成,因此稱為重疊-相加之摺積法。
儘管一時看不出切割成區塊的好處為何,但考慮到對任何 以上每段的摺積都等價於 和 做 點圓周摺積 ,不夠的部分補上零 (zero-padding)。如此一來因為圓周摺積可以藉由圓周摺積定理
轉換成三次 點快速傅立葉變換和 次乘法,使原本每段 O(N2) 的運算量減少至 O(N logN),速度大幅增加。
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 < log2N' ),直接摺積(不透過圓周摺積和 FFT )反而最快。而當 N' 和 M 差不多在同一個數量級時,不用分割,也就是只有一塊長度 L = N' 的區塊去做 FFT 即可。而當 N' 比 M 大了不少,卻沒大太多時,區塊長度 L 就需要選擇。除了與 N' 和 M 相關以外,也要考慮當兩者相除有餘數時,剩下一小段的輸入可能會造成浪費。
相關條目
參考文獻
- Rabiner, Lawrence R.; Gold, Bernard. Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. 1975: pp 65–67. ISBN 0-13-914101-4.
- Helms, H., Fast Fourier transform method of computing difference equations and simulating filters, IEEE Transactions on Audio and Electroacoustics, 1967, 15(2): 85–90 [2008-06-23], (原始内容存档于2019-06-30)