重叠-相加之卷积法

重叠-相加之卷积法 ( Overlap-add method ) 是一种区块卷积 ( block convolution, sectioned convolution )，可以有效的计算一个很长的信号 x[n] 和一个 FIR 滤波器 h[n] 的离散卷积。

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

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

重叠-相加之卷积法算出重叠的输出区块；另一种区块卷积的作法，重叠-存储之卷积法则是将输入区块重叠。

算法

图1：重叠-相加法

概念上，这个做法是选用一个较短的适当长度 L 来切割 x[n] ，计算 x[n] 的子数列滤波后的结果 y_k[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{aligned}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{aligned}}$

其中  $y_{k}[n]\ {\stackrel {\mathrm {def} }{=}}\ x_{k}[n]\star h[n]\,$  在 [1, L+M-1] 之外为零。 每个 y_k[n] 长度 $L+M-1$ ，以间隔 $L$ 位移后相加，所以输出是由互相重叠的区块相加而成，因此称为重叠-相加之卷积法。

尽管一时看不出切割成区块的好处为何，但考虑到对任何  $N\geq 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(N²) 的运算量减少至 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 < 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） 

外部链接

• Matlab （页面存档备份，存于互联网档案馆） 使用 Matlab 函数 fftfilt.m 实现重叠-相加之卷积法
• DSP class Fall 2005 Lecture08 at The University of Texas at Arlington