# 重疊-儲存之摺積法

\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}

## 算法

$x_k[n] \ \stackrel{\mathrm{def}}{=} \begin{cases} x[n+kL-M] & 1 \le n \le L+M-1\\ 0 & \textrm{otherwise}. \end{cases}$
$y_k[n] \ \stackrel{\mathrm{def}}{=} \ x_k[n] \star h[n]\,$

\begin{align} y[n] = \sum_{m=1}^{M} h[m] \cdot x[n-m] = \sum_{m=1}^{M} h[m] \cdot x_k[n+M-kL-m] &= x_k[n+M-kL] \star h[n] \\ &\stackrel{\mathrm{def}}{=} \ y_k[n+M-kL]. \end{align}

$x_{k,N}[n] \ \stackrel{\mathrm{def}}{=} \ \sum_{k=-\infty}^{\infty} x_k[n - kN],$

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

### 準程式碼

   (Overlap-save algorithm for linear convolution)
//////// revised by fantastic ////////
N = length(x), M = length(h)
O = M – 1;   // overlap length must be M-1
L = M;       // >=1 is OK
P = O + L;
H = FFT(h, P);       // just calc once
idx = - (O - 1);     // starting index which is offset M-1 in matlab
while (idx <= N)
i1 = max(1, idx);        // must be >= 1
i2 = min(N, idx+P-1);    // must be <= N
yt = IFFT( FFT(x(i1:i2), P).*H, P );
y(idx:idx+P-M) = yt(M:P);        // discard first M-1 values and concatenate the remaining
idx = idx + L;
end
y = y(1:M+N-1);      // the first M+N-1 values are the convolution result


## 區塊長度的選擇

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

## 外部連結

• DSP class Fall 2005 Lecture08 at The University of Texas at Arlington]