线卷积 圆卷积,线性卷积与圆周卷积的计算

前言

在信号处理基础那篇博客中证明了时域的线卷积和频域DTFT相乘等价，但实际应用中用到的更多是DFT（FFT）变换和线卷积，因此也就没法应用此特性进行快速计算。幸运的是，频域的DFT相乘和时域的圆周卷积等价，因此只要在某种条件下，圆周卷积和线卷积等价，就可以利用FFT变换快速计算时域的线卷积。

圆周卷积和线卷积 有限长序列时移

有限长序列 x ( n ) , 0 ≤ n ≤ N − 1 x(n),0leq nleq N-1 x(n),0≤n≤N−1，经过时移 m m m位，序列变为 x ( n − m ) , m ≤ n ≤ N + m − 1 x(n-m),mleq nleq N+m-1 x(n−m),m≤n≤N+m−1,两个序列进行DFT变换取级数的范围会不同，这给DFT研究带来不便，为了解决这个问题，把有线长序列的位移赋予一种新的解释，圆周移位，首先将序列周期扩展、移位，然后取主值区，将这种操作写为： x ( ( n − m ) ) N R N ( n ) x((n-m))_NR_N(n) x((n−m))N​RN​(n)

圆周卷积： x ( n ) ⊗ h ( n ) = ∑ m = 0 N − 1 x ( m ) h ( ( n − m ) ) N R N ( n ) x(n)otimes h(n)=sum_{m=0}^{N-1}x(m)h((n-m))_NR_N(n) x(n)⊗h(n)=m=0∑N−1​x(m)h((n−m))N​RN​(n)
序列 x ( n ) x(n) x(n)长度为 N N N, h ( n ) h(n) h(n)长度为 M M M,则线性卷积后的长度为 M + N − 1 M+N-1 M+N−1,假设圆周卷积长度为 L L L,则当 L ≥ M + N − 1 Lgeq M+N-1 L≥M+N−1时，圆周卷积的前 M + N − 1 M+N-1 M+N−1和线性卷积结果一样。

例子

举个例子：x=[1,1,1],h=[1,1,1,1], L = 6 L=6 L=6,线性卷积过程为：

进行圆周卷积之前会对数据补齐为：
x = [1 1 1 0 0 0]
h = [1 1 1 1 0 0]
圆周卷积过程为：

对比运行过程可以发现，当圆周卷积长度 L ≥ M + N − 1 Lgeq M+N-1 L≥M+N−1时，两个序列多余的交叠部分都是和0相乘的，因此圆周卷积结果的前 M + N − 1 M+N-1 M+N−1点和线卷积的结果一致。

所以通过选择FFT变换长度 L ≥ M + N − 1 Lgeq M+N-1 L≥M+N−1时，可以利用FFT快速计算线卷积。
一个matlab例子，y1和y2的运行结果一致。

x = [1 1 1];h = [1 1 1 1];y1 = conv(x,h);L = 6;y2 = ifft(fft(x,L).*fft(h,L); 参考文献

[1] 信号与系统（第二版）yhdxbc