有限长序列的线性卷积和圆周卷积

线性卷积

卷积是两个时间序列之间一种激励和响应得出结果的关系，是可交换、可结合和可分配的。假定一个线性时不变系统的冲激响应为，输入信号通过该系统的输出信号为

对于离散信号，长度分别为N，M的两个有限长序列x[n](0~N-1)，h[n](0~M-1)的线性卷积定义如下：

两个有限长序列的线性卷积结果也是有限长序列，长度为N+N-1(0~N+M-2)。信号的卷积在Matlab中有实现函数conv(u,v)，可自行查看，具体实现如下：

线性卷积的实现过程：将其中一个序列进行反褶后平移，与另一个序列相乘，相乘结果进行累加，用动图表示如下：

循环卷积

长度都为N的两个有限长序列x[n](0~N-1)，h[n](0~N-1)的循环卷积定义如下：

循环卷积结果的长度仍为N，若两序列长度不等，采用补零法。

循环卷积主要过程：

1)对两个序列进行指定长度的周期延拓(长度不够，进行补零)；

2)其中一个周期序列固定，另外一个周期序列翻转；

3)翻转后的周期序列不断时移，然后对两个周期序列重叠的点进行相乘；

4)对上一步相乘的结果在一个周期内进行累加，所得结果也是一个周期序列；

5)对得到的周期序列取主值区间，得到循环卷积结果。

快速傅里叶变换(FFT)的出现，使得利用循环卷积计算线性卷积成为了常规思维。循环卷积和线性卷积等价的条件为：循环卷积长度应该大于或等于两个序列非零值长度之和减1。

用一个特别简单的例子给大家介绍一下线性卷积和循环卷积的输出结果：

N=5;

x=[1 2 3];

h=[1 1 1];

conv(x,h) % 线性卷积结果

x=[x,zeros(1,N-length(x))];

h=[h,zeros(1,N-length(h))];

m=0:N-1;

xcir=zeros(N,N);

for n=0:N-1

xcir(:,n+1)=x(mod((n-m),N)+1)’;

end

yn=h*xcir % 循环卷积结果

两个长度都为3的序列：[1 2 3]和[1 1 1]，当N=5时，线性卷积和循环卷积结果都为：[1 3 6 5 3]。当N=4时，循环卷积结果为：[4 3 6 5]，当N=3时，循环卷积结果为：[6 6 6]。

在很多实际应用当中，输入序列可能是一个很长的序列，如果用循环卷积代替线性卷积，系统响应h[n]需要补很多零，用FFT计算循环卷积的运算量相对直接计算线性卷积的运算量没有优势，甚至会超过直接计算的运算量。

因此，在利用循环卷积计算线性卷积之前，要对输入序列(长序列)进行分段，得到和h[n]长度相当的子序列。这个过程中会遇到哪些问题，有什么解决方法？且听下回解释。

原文始发于微信公众号（雷达通信电子战）

有限长序列的线性卷积和圆周卷积留言