重叠-存储之卷积法

概念上，这个做法是选用一个较短的适当长度 L 来切割 y[n] ，则因为 h[n] 是有限长度，因此在某一区块内的 y[n] 也只被有限长的 x[n] 区块（会比 y[n] 分割成的区块长一点）所决定。因此只要选择有影响的输入区块和 h[n] 卷积，再选择结果中适当的部分即可得到正确的输出区块。

${\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 [kL+1,(k+1)L]}$  内的 n ， 输出 y[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}}}$ 

所以只需计算 n 在 ${\displaystyle [kL+1,(k+1)L]}$  中的 y_k[n + M - kL] ，亦即 n 在 ${\displaystyle [M+1,L+M]}$  的 y_k[n] 部分即可。因此每一段输出区块 y_k[n] 的前 M-1 点可丢弃（discard）。

尽管一时看不出切割成区块的好处为何，但将 x_k[n] 做  ${\displaystyle N\geq L+M-1\,}$   的周期延伸，

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

则  ${\displaystyle (x_{k,N})\star h\,}$   和  ${\displaystyle x_{k}\star h\,}$   这两个卷积在 ${\displaystyle [M+1,L+M]}$  的部分相等。所以可以将线性卷积改以 ${\displaystyle N\,}$  点循环卷积计算，结果的 ${\displaystyle [M+1,L+M]}$  部分作为输出 y[n] 在 ${\displaystyle [kL+1,(k+1)L]}$  的部分。由于每段 x_k[n] 原本就有  ${\displaystyle L+M-1\,}$   长，所以选择  ${\displaystyle N=L+M-1\,}$   的话输入 x[n] 就不需补零。 改以循环卷积计算后即可藉循环卷积定理

${\displaystyle y_{k}[n]={\textrm {IFFT}}\left({\textrm {FFT}}\left(x_{k}[n]\right)\cdot {\textrm {FFT}}\left(h[n]\right)\right)}$ 

变换成三次 ${\displaystyle N\,}$  点快速傅里叶变换和 ${\displaystyle N\,}$  次乘法，使原本每段 O(N²) 的运算量减少至 O(N logN)，速度大幅增加。

准代码

   (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 < log₂N' ），直接卷积（不透过循环卷积和 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.  引文格式1维护：冗余文本 (link)
• 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） 

• DSP class Fall 2005 Lecture08^{[永久失效链接]} at The University of Texas at Arlington]