计算机科学

首页 > 计算机科学

重叠-相加之卷积法

2018-09-06 14:26:23     所属分类:数值分析

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

其中 hm 在 1, M 之外为零。

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

目录

  • 1 算法
    • 1.1 伪代码
  • 2 区块长度的选择
  • 3 相关条目
  • 4 参考文献
  • 5 外部链接

算法

图1:重叠-相加法

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

而因为卷积是线性时不变运算,所以 yn 可被表示为

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


尽管一时看不出切割成区块的好处为何,但考虑到对任何    以上每段的卷积都等价于 点循环卷积 ,不够的部分补上零 (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

区块长度的选择

xn 的长度 N' hn 的长度 M 相差太大时(例如 M < log2N' ),直接卷积(不透过循环卷积和 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. 
  • Helms, H., Fast Fourier transform method of computing difference equations and simulating filters, IEEE Transactions on Audio and Electroacoustics, 1967, 15(2): 85–90 

外部链接

  • Matlab 使用 Matlab 函数 fftfilt.m 实现重叠-相加之卷积法
  • DSP class Fall 2005 Lecture08[永久失效链接] at The University of Texas at Arlington

相关推荐