重叠-相加之卷积法

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

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

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

算法

 
图1:重叠-相加法

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

 

 

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

 

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


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

 

变换成三次  快速傅里叶变换  次乘法,使原本每段 O(N2) 的运算量减少至 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 < log2N' ),直接卷积(不透过循环卷积FFT )反而最快。而当 N' M 差不多在同一个数量级时,不用分割,也就是只有一块长度 L = N' 的区块去做 FFT 即可。而当 N' M 大了不少,却没大太多时,区块长度 L 就需要选择。除了与 N' M 相关以外,也要考虑当两者相除有余数时,剩下一小段的输入可能会造成浪费。

相关条目

参考文献

外部链接