2012数字信号处理课件第二章第八节.pdf

一、利用FFT 求解线性卷积 两个有限长序列 x(n) ，0 £n £N -1和h(n) ，0 £n £M -1 做线性卷积，可以得 y (n) =x (n) *h(n) ，0 £n £N +M -2 ， 根据第三节中有限长序列圆周卷积和线性卷积关系的讨论， 可以采用FFT 实现线性卷积运算。 L 对x(n) 和y (n) 补零至 点，L ‡ N +M -1 x(n) f (n) =x(n)*y (n) y (n) ⚫ 运算量分析： N-1 y(n) =x(n)*h(n) = x(m)h(n-m)，假设 ，则直接计算线性卷积需要的  N ‡M m=0 复数乘法的次数为 1+2+L +M +L +M +(M -1)+L +1=M ·(N-M +1)+M ·(M -1) =MN次 14444244443 N-M +1 复数加法的次数为 1+2+L +(M -1)+(M -1)+L +1=(M-1)(N -M +1)+(M -1)(M -2) =(M -1)(N -1)次 1444444244444443 N-M +1 ⚫ 运算量分析： 利用FFT 实现线性卷积运算则需要 L 复数乘法 log2 L ·3 +L 次，复数加法3L log 2 L 次 2 如果M 和N 较大，则采用 FFT 实现的线性卷积运 算可以大幅度减少运算量。 二、 相加法和 保留法 在实际应用的卷积中，常常会遇到一个序列的长度远大于令一个序列， 即x(n) ，0 £n £N 1 -1，h(n) ，0 £n £M -1且N 1 ? M (或N 1 fi ¥ )。 在这种情况下，采用上面补零的方法是不可取的，为此可以将长序列 x(n) 分段，每段N 点，与h(n) 的长度相近，分别与h(n) 卷积后， 再将得到的分段结果合并成y (n) 。 1． 相加法 （Overlap-add method ） 分段 x (n) iN £n £(i +1)N -1  x (n) = i 0 其余n  ¥ 则x(n) ＝ x (n) i=0 i y (n) =x (n) *h(n) = ¥ x (n)  *h(n) =¥ x (n) *h(n) = ¥ y (n)  i=0 i  i=0 i i=0 i 其中x (n) ，N 点；h(n) ，M 点；y (n) ，N +M -1 点。因此，每相邻 i i 两段输出必有M -1点 ，最后输出结果应将 部分相加，故称为 相加法。 2. 保留法(Overlap save method) 分段，每段L 点，每相邻两段之间有M -1点 x (n +iN -M +1) 0 £n £L -1  x (n) =