本页使用了标题或全文手工转换

重叠-储存之折积法

维基百科,自由的百科全书
跳到导航 跳到搜索

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

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

重叠-相加之折积法不同之处在于,重叠-储存之折积法所算出的输出区块并不重叠 (因此计算上少了将输出区块相加所需的加法),而是每次用的输入区块有所重叠。因此实作时每次读取输入后需将和下一个输入重叠的部分储存起来,作为下一输入区块的开头部份,因此称为重叠-储存之折积法。另外重叠-储存之折积法也不需补零。

算法[编辑]

概念上,这个做法是选用一个较短的适当长度 L 来切割 y[n] ,则因为 h[n] 是有限长度,因此在某一区块内的 y[n] 也只被有限长的 x[n] 区块(会比 y[n] 分割成的区块长一点)所决定。因此只要选择有影响的输入区块和 h[n] 折积,再选择结果中适当的部分即可得到正确的输出区块。



则对于在 内的 n , 输出 y[n] 可写成

所以只需计算 n 中的 yk[n + M - kL] ,亦即 nyk[n] 部份即可。因此每一段输出区块 yk[n] 的前 M-1 点可丢弃(discard)。


尽管一时看不出切割成区块的好处为何,但将 xk[n] 做    的周期延伸

则    和    这两个折积在 的部份相等。所以可以将线性折积改以 圆周折积计算,结果的 部分作为输出 y[n] 在 的部份。由于每段 xk[n] 原本就有    长,所以选择    的话输入 x[n] 就不需补零。 改以圆周折积计算后即可藉圆周折积定理

转换成三次 快速傅立叶变换 次乘法,使原本每段 O(N2) 的运算量减少至 O(N logN),速度大幅增加。

准程式码[编辑]

   (Overlap-save algorithm for linear convolution)
   //////// revised by fantastic ////////
   N = length(x), M = length(h)
   O = M – 1;	// overlap length must be M-1
   L = M;	// >=1 is OK
   P = O + L;
   H = FFT(h, P);	// just calc once
   idx = - (O - 1);	// starting index which is offset M-1 in matlab
   while (idx <= N)
       i1 = max(1, idx);	// must be >= 1
       i2 = min(N, idx+P-1);	// must be <= N
       yt = IFFT( FFT(x(i1:i2), P).*H, P );
       y(idx:idx+P-M) = yt(M:P);	// discard first M-1 values and concatenate the remaining
       idx = idx + L;
   end
   y = y(1:M+N-1);	// the first M+N-1 values are the convolution result

区块长度的选择[编辑]

x[n] 的长度 N' h[n] 的长度 M 相差太大时(例如 M < log2N' ),直接折积(不透过圆周折积FFT )反而最快。而当 N' M 差不多在同一个数量级时,不用分割,也就是只有一块长度 L = N' 的区块去做 FFT 即可。而当 N' M 大了不少,却没大太多时,区块长度 L 就需要选择。除了与 N' M 相关以外,也要考虑当两者相除有馀数时,剩下一小段的输入可能会造成浪费。

相关条目[编辑]

参考文献[编辑]

外部链接[编辑]