# 重疊-儲存之摺積法

{\displaystyle {\begin{aligned}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{aligned}}}

## 算法

${\displaystyle x_{k}[n]\ {\stackrel {\mathrm {def} }{=}}{\begin{cases}x[n+kL-M]&1\leq n\leq L+M-1\\0&{\textrm {otherwise}}.\end{cases}}}$
${\displaystyle y_{k}[n]\ {\stackrel {\mathrm {def} }{=}}\ x_{k}[n]\star h[n]\,}$

{\displaystyle {\begin{aligned}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{aligned}}}

${\displaystyle x_{k,N}[n]\ {\stackrel {\mathrm {def} }{=}}\ \sum _{k=-\infty }^{\infty }x_{k}[n-kN],}$

${\displaystyle 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 相關以外，也要考慮當兩者相除有餘數時，剩下一小段的輸入可能會造成浪費。