重疊-相加之摺積法

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

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

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

算法

概念上，這個做法是選用一個較短的適當長度 L 來切割 x[n] ，計算 x[n] 的子數列濾波後的結果 yk[n] ，然後連接起來成為 y[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 相關以外，也要考慮當兩者相除有餘數時，剩下一小段的輸入可能會造成浪費。

相關條目

離散摺積
圓周摺積
快速傅立葉變換
重疊-儲存之摺積法

參考文獻

外部連結

 Matlab  使用 Matlab 函數 fftfilt.m 實作重疊-相加之摺積法
DSP class Fall 2005 Lecture08 at The University of Texas at Arlington

数字信号处理
傅里叶分析
数值分析