重叠-相加之卷积法

在信号处理中，重叠相加法是一种有效的方法来评估非常长的信号 x [ n ] {displaystyle x[n]} 与有限脉冲响应 (FIR) 滤波器 h [ n ] { displaystyle h[n]} :

（等式 1）

其中 h[m] = 0 表示 m 在区域 [1, M] 之外。本文使用常见的抽象符号，例如 y ( t ) = x ( t ) ∗ h ( t ) , {textstyle y(t) =x(t)*h(t),} 或 y ( t ) = H { x ( t ) } , {textstyle y(t)={mathcal {H}}{x(t) },} 其中应该理解函数应该整体考虑，而不是在特定时刻 t {textstyle t}（参见 Convolution#Notation）。

这个概念是将问题分成 h[n] 的多个卷积和 x [ n ] {displaystyle x[n]} 的短片段：

x k [ n ] ≜ { x [ n + k L ] , n = 1 , 2 , … , L 0 , 否则 {displaystyle x_{k}[n] triangleq {begin{ cases}x[n+kL],&n=1,2,ldots ,L\0,&{text{otherwise}},end{cases}}}

其中 L 是任意段长度。 然后：

x [ n ] = ∑ k x k [ n − k L ] , {displaystyle x[n]=sum _{k}x_{k}[n-kL],,}

y[n] 可以写成短卷积的总和：

y [ n ] = ( ∑ k x k [ n − k L ] ) ∗ h [ n ] = ∑ k ( x k [ n − k L ] ∗ h [ n ] ) = ∑ k y k [ n − k L ] , { displaystyle {begin{aligned}y[n]=left(sum _{k}x_{k}[n-kL]right)*h[n]&=sum _{ k}left(x_{k}[n-kL]*h[n]right)\&=sum _{k}y_{k}[n-kL], 结束{对齐}}}

其中线性卷积 y k [ n ] ≈ x k [ n ] ∗ h [ n ] {displaystyle y_{k}[n] triangleq x_{k}[n]*h[n] ,} 在区域 [1, L + M − 1] 之外为零。 而对于任意参数 N ≥ L + M − 1 , {displaystyle Ngeq L+M-1,,} 等价于 x k [ n ] {displaystyle x_ {k}[n],} 和 h [ n ] {displaystyle h[n],} 在区域 [1, N] 中。 优点是循环卷积可以比线性卷积更有效地计算，根据循环卷积定理：

（等式 2）

在哪里：

• DFTN 和 IDFTN 指的是离散傅里叶变换及其逆变换，在 N 个离散点上求值，并且
• 通常选择 L，使得 N = L+M-1 是 2 的整数次幂，并且为了提高效率，使用 FFT 算法实现转换。

下面是该算法的伪代码：

(Overlap-add algorithm for linear convolution)h = FIR_filterM = length(h)Nx = length(x)N = 8 × 2ceiling( log2(M) ) （8 乘以大于滤波器长度 M 的两个最小幂。

当用FFT算法实现DFT和IDFT时，上面的伪代码需要对FFT、数组乘积和IFFT进行大约N(log2(N)+1)次复数乘法。 每次迭代产生 N-M+1 个输出样本，因此每个输出样本的复数乘法次数约为：

（等式 3）

例如，当 M=201 和 N=1024 时，Eq.3 等于 13.67，而 Eq.1 的直接评估将需要每个输出样本进行多达 201 次复数乘法，最坏的情况是 x 和 h 均为复值。 另请注意，对于任何给定的 M，Eq.3 具有相对于 N 的最小值。图 2 是在滤波器长度 (M) 的范围内最小化 Eq.3 的 N 值的图表。

除了方程式 1，我们还可以考虑将方程式 2 应用于长度为 N x {displaystyle N_{x}} 样本的长序列。 复数乘法的总数为：

N x ⋅ ( log 2 ⁡ ( N x ) + 1 ) 。 {displaystyle N_{x}cdot (log _{2}(N_{x})+1).}

相比之下，伪代码算法所需的复数乘法次数为：

N x ⋅ ( log 2 ⁡ ( N ) + 1 ) ⋅ N N − M + 1 。 {displaystyle N_{x}cdot (log _{2}(N)+1)cdot {frac {N}{N-M+1}}.}

因此，重叠相加方法的成本几乎为 O ( N x log 2 ⁡ N ) {displaystyle Oleft(N_{x}log _{2}Nright)} 而成本 一个大的圆形卷积几乎是 O ( N x log 2 ⁡ N x ) {displaystyle Oleft(N_{x}log _{2}N_{x}right)} 。 这两种方法也在图 3 中进行了比较，该图由 Matlab 仿真创建。 等高线是执行这两种方法所需时间的恒定比率线。 当 overlap-add 方法更快时，比率超过 1，并且比率高达 3。