重叠-存储之卷积法
简介
在信号处理中，重叠-保存是评估一个很长的信号x [ n ] {displaystyle x[n]}和一个有限脉冲响应（FIR）滤波器h [ n ] {displaystyle h[n]}之间离散卷积的有效方式的传统名称。
其中可以理解为这些函数应该被认为是整体的，而不是在特定的时刻t {fnMicrosoftYaHeifs15bord1shad03aHCCb0}（见Convolution#Notation）。
这个概念是计算任意长度为L的y[n]的短片段，并将这些片段串联起来。考虑一个从n = kL + M开始的段，对于任何整数k，并定义。
随着j = n – k L {displaystyle j=n-kL}的替换，任务减少到计算y_{k}[n-kL]。这些步骤在图1的前3条痕迹中得到了说明，只是输出的期望部分（第三条痕迹）对应于1≤j≤L。
如果我们定期延长xk[n]，周期为N≥L+M-1，根据。
子区域[M + 1, L + M]被附加到输出流中，而其他的值被丢弃。 其优点是，根据循环卷积定理，循环卷积可以比线性卷积更有效地计算。
(公式2)
DFTN和IDFDN指的是离散傅里叶变换和它的逆，在N个离散点上进行评估，L通常被选择为N=L+M-1是2的整数次方，为了提高效率，变换用FFT算法实现。 圆周卷积的前缘和后缘效应被重叠和添加，随后被丢弃。
效率考虑 当DFT和IDFT由FFT算法实现时，上面的伪代码需要大约N（log2（N）+1）次复数乘法，用于FFT、数组的乘积和IFFT。每次迭代产生N-M+1个输出样本，因此每个输出样本的复数乘法数量约为。
(公式.3)
例如，当M=201和N=1024时，公式.3等于13.67，而直接评估公式.1将需要每个输出样本进行多达201次复数乘法，最坏的情况是当x和h都是复数值时。图2是在一定的滤波器长度（M）范围内，使公式3最小化的N值的图。
取代公式1，我们也可以考虑将公式2应用于长度为N x {displaystyle N_{x}}样本的长序列。复数乘法的总数量将是。
相对而言，伪码算法所需的复数乘法数量为。
因此，重叠保存方法的成本几乎是O
而单个大循环卷积的成本几乎是O