重疊-相加之摺積法

维基百科,自由的百科全书
跳转至: 导航搜索

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


\begin{align}
y[n] = x[n] \star h[n] \ \stackrel{\mathrm{def}}{=} \ \sum_{m=-\infty}^{\infty} h[m] \cdot x[n-m]
= \sum_{m=1}^{M} h[m] \cdot x[n-m]
\end{align}

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

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

算法[编辑]

概念上,這個做法是選用一個較短的適當長度 L 來切割 x[n] ,計算 x[n] 的子數列濾波後的結果 yk[n] ,然後連接起來成為 y[n] 。並考慮到一個長度 L 和長度 M 的有限長度離散信號,做摺積之後會成為長度 L+M-1 的信號。

x_k[n]  \ \stackrel{\mathrm{def}}{=} 
\begin{cases}
x[n+kL] & n=1,2,\ldots,L\\
0 & \textrm{otherwise}
\end{cases}

x[n] = \sum_{k} x_k[n-kL]\,

而因為摺積線性非時變運算,所以 y[n] 可被表示為


\begin{align}
y[n] = \left(\sum_{k} x_k[n-kL]\right) \star h[n] &= \sum_{k} \left(x_k[n-kL]\star h[n]\right)\\
&= \sum_{k} y_k[n-kL]
\end{align}

其中  y_k[n] \ \stackrel{\mathrm{def}}{=} \ x_k[n] \star h[n]\,  在 [1, L+M-1] 之外為零。 每個 yk[n] 長度 L+M-1 ,以間隔 L 位移後相加,所以輸出是由互相重疊的區塊相加而成,因此稱為重疊-相加之摺積法。


儘管一時看不出切割成區塊的好處為何,但考慮到對任何  N\ge L+M-1\,  以上每段的摺積都等價於 x_k[n]\,h[n]\,N\,圓周摺積 ,不夠的部分補上零 (zero-padding)。如此一來因為圓周摺積可以藉由圓周摺積定理

y_k[n] = \textrm{IFFT}\left(\textrm{FFT}\left(x_k[n]\right)\cdot\textrm{FFT}\left(h[n]\right)\right)

轉換成三次 N\,快速傅立葉變換N\, 次乘法,使原本每段 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