[科普中国]-重叠-相加之卷积法

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

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

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

算法

概念上，这个做法是选用一个较短的适当长度L来切割x[n] ，计算x[n] 的子数列滤波后的结果yk[n] ，然后连接起来成为y[n] 。并考虑到一个长度 和长度 的有限长度离散信号，做卷积之后会成为长度的信号。

则

而因为卷积是线性时不变运算，所以y[n] 可被表示为

其中 在 [1,L+M-1] 之外为零。每个yk[n] 长度 ，以间隔位移后相加，所以输出是由互相重叠的区块相加而成，因此称为重叠-相加之卷积法1。

尽管一时看不出切割成区块的好处为何，但考虑到对任何 以上每段的卷积都等价于 和 做 点循环卷积，不够的部分补上零 (zero-padding)。如此一来因为循环卷积可以借由循环卷积定理

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

伪代码 Algorithm (OA for linear convolution) Evaluate the best value of N and L H = FFT(h,N) (zero-padded FFT) i = 1 while i