实现卷积运算的两种方法为何得到结果的长度不一样？

卓大大，打扰一下。我想问下您就是互相关运算和卷积在一定程度上是一样的运算吧？那为什么卷积之后序列长度是 2N-1，而互相关运算的结果按照那个频域相乘再求快速傅里叶的逆变换得到的序列长度应该是就是之前的序列长度 N 吧？为啥和卷积的长度不一致呢？

这里的频域相乘应该就是对应的序列相乘吧？比如 X[1]=a[1]*b[1]，这样子我是哪里想错了呢？麻烦卓大大解惑啦。

提问分析(Analaysis)

你所提出的问题是关于“信号与系统”学科中十种信号[1]中的主要两种复杂运算形式：卷积运算和相关运算。具体疑问是实现卷积运算的两种方法为何得到结果的长度不一样？

方法 1: 直接在时域利用公式计算；方法 2: 利用快速傅里叶变换加速计算；

这个问题涉及到关于卷积、相关运算的如何定义、结果长度是多少、如何加速卷积相关运算等问题。下面来分析一下其中的理由。

基础理论(Principle)

1. 相关与卷积

你一开始提到相关运算和卷积运算在一定程度上是一样的运算吧？对的，这两种运算的确很相像。从它们的公式就可以看出来：两个连续时间信号的卷积运算为：

两个信号的相关运算为：

对于实值信号来讲，这两个运算主要区别就在于积分号内部，第二个信号是否需要反褶[2]。如果参与运算的第二个信号是偶信号[^3]，那么这两个运算就几乎相同。因此，你所说它们在一定程度上是一样具有一定的道理。

当然，这两种运算在使用目的、数学性质方面还是有一定的差异。下面分析就主要以卷积运算进行讨论。

当信号为离散时间序列时，相应的运算就是累加和的形式。以卷积运算为例：

卷积也可以扩展到高维信号运算。下面是二维图像信号的离散卷积运算。它被广泛应用到深度学习中的卷积神经网络中。

▲ 二维离散卷积和运算

2. 有限长信号运算结果长度

根据卷积运算公式可以看出，参与卷积运算的两个信号，任选其中一个信号进行反褶、平移，然后在于另外一个信号进行相乘、积分便得到计算结果。

如果参与运算的两个信号的长度都是有限长，分别是，那么它们卷积结果也是一个有限长的信号，长度等于。

对于有限长的离散时间序列信号，它们的卷积结果的长度等于参与卷积的两个信号长度之和，再减去 1。这些结论可以通过如下卷积运算的图解过程分析可得。

▲ 卷积运算的图解过程

相关运算结果的长度也是类似的。

3. 计算复杂度

你的问题中提到了使用快速傅里叶变换（FFT）来加快计算卷积结果。相比于两个信号的乘积运算，信号的卷积（相关）运算的确复杂。要获得每一个结果值，都需要完成相应的积分（累加和）。

比如，对于长度分别为的两个序列，得到对应长度为卷积结果，需要的乘法次数为，加法次数为。

如何加快卷积运算呢？在数学上可以利用傅里叶变换的卷积定理，来将时域空间中的卷积运算转换成频域（变换域）中的乘积运算。由于存在着快速傅里叶变换变换算法，这就整体提高了计算的效率。

▲ 利用 FFT 加速卷积运算的示意图

看似傅里叶变换“真香”，但它也会带来麻烦。比如，两个信号的时域乘积运算，经过傅里叶变换之后，在频域又变成了卷积运算。这还不是主要的问题，最主要的是，这种变化所完成的计算结果，是两个信号的“圆卷积”。

4. 线卷积与圆卷积

由于快速傅里叶变换（FFT），是离散傅里叶变换（DFT）的快速算法，而离散傅里叶变换的公式来源于周期序列信号的傅里叶级数分解（DTFS）的公式。所以本质上讲，他们反映的是周期离散序列信号中在一个周期内有限个波形数据，与它的频谱，也是一个周期序列信号，在一个周期内的有限个频谱数据之间的对应关系。因此，通常对信号的平移、反褶等操作，都需要按照圆位移、圆反褶来进行，即先把信号拓展长一个周期信号，然后进行相应的平移，反褶。然后在结果的基础上在提取其中的一个主周期[3]的数据。

下图显示了圆位移的过程。

▲ 圆位移示意图

将卷积运算中的反褶、位移都替换成圆反褶、圆位移，就形成了两个信号的圆卷积操作。两个信号进行圆卷积，它们必须长度相同，圆卷积的结果等于两个信号的长度本身，而不是它们的长度之和，再减一。

由于有了圆卷积的定义，所以将原来的普通卷积称为线卷积。

到此为止，我们知道为什么使用 FFT 加速卷积计算的结果与直接使用公式计算所得到的结果长度不同了。这是因为利用 FFT 所得到的卷积结果是两个等长序列的圆卷积，与两个序列的线卷积的结果是不同的。

那么，怎么解决这个问题呢？

问题解决(Problem)

解决方法很简单，那就是补零，即在序列后面通过增加若干个 0，来增加序列的长度。

圆卷积运算要求参与运算的两个信号长度必须相同，满足这一点是通过对短序列后面补零来实现。同样，为了使得圆卷积也能够得到和线卷积相同长度的结果，只要将两个序列（长度分别为）长度通过补零延长到即可。这样通过圆卷积所得到的结果不仅长度和线卷积的长度相同，实际上，结果也是一样的。

下图中显示了两个长度分别为 4,6 的信号，线卷积和圆卷积的结果，显然它们是不同的。右边通过补零，将它们的长度都扩展到，所得到的圆卷积结果就与线卷积相同了。

▲ 圆卷积、线卷积、补零后的圆卷积

实验观察(Laboratory)

下面是两个序列以及它们的线卷积结果。

▲ 线卷积结果

计算结果调用了 scipy.signal 中的 fftconvolve 指令。参与运算的长度分别为 10,14，线卷积结果的长度为 23。在 fftconvolve 命令中，还可以通过改变参数 mode，使其分别为“same”,"valide"，分别抽取结果中的长度为 10,5 的结果中心部分，这样就可以获得与参与卷积运算的最短序列相同，以及两个序列完全重合的结果。

▲ 线卷积的不同结果

t = linspace(0, 10, 10, endpoint=False)[newaxis]d = ones((1, 14), dtype=int16)cv1 = fftconvolve(t, d, 'full')cv2 = fftconvolve(t, d, 'same')cv3 = fftconvolve(t, d, 'valid')

使用 scipy.ndimage 中的 convolve 可以实现圆卷积，需要将 mode 设置为"wrap"即可。

t = linspace(0, 10, 10, endpoint=False)[newaxis]d = ones((1, 14), dtype=int16)cvc = scipy.ndimage.convolve(t, d, mode='wrap')

▲ 圆卷积结果

下面是设定长度增加的圆卷积结果，长度从 14 一直增加到 30。可以看到圆卷积的结果逐步与线卷积变得相同。直道长度大于 23 之后，圆卷积所得到的结果就变得与线卷积一样了。

▲ 长度变化后的圆卷积结果

for i in range(30):    length = 14+i    t = linspace(0, length, length, endpoint=False)[newaxis]    d = ones((1, length), dtype=int16)
    t[0][10:] = 0    d[0][14:] = 0

    cvc =scipy.ndimage.convolve(t,d, mode='wrap')
    plt.clf()    plt.subplot(3,1,1)    plt.stem(t[0])    plt.axis([0, length+1, 0, 10])
    plt.subplot(3,1,2)    plt.stem(d[0])    plt.axis([0, length+1, 0, 5])
    plt.subplot(3,1,3)    plt.stem(cvc[0])    plt.axis([0, length+1, 0, 100])    plt.draw()    plt.pause(.5)

扩展联系(Extention)

通过卷积、相关运算，可以获得丰富的信号处理能力。相关运算就可以用于检测信号之间的相似程度，并用于信号的位置检测。

两个有限长信号的相关运算

使用快速傅里叶变换来加速卷积，相关运算，可以达到实时信号处理的目的。通过在频域数据的补零，还可以实现对卷积结果的理想插值。

其他相关提问

卓大大，有些同学提议学习美赛分成两个时间段来做，我觉得这个建议不是特别妥当。因为公平起见肯定要控制变量，比赛环节需要尽量一致。退一万步说，一届比赛获奖结果也是需要一起比较得出来的，即便是美赛也是一起评的奖，八月份的比赛结果总不能等到寒假再出成绩吧。望大大三思而后行。

博士您好，我在广州的学校，学校通知六月底毕业生返校，我们这些大三的这学期估计没办法返校，就是有点担心比赛的事情怎么进行，毕竟三个组员没办法协同工作

卓大大，双车组可以使用现成的电磁铁模块吗，如图。

▲ 电磁铁模块

回复：可以的。

参考资料

[1]十种信号运算: 、相加、相乘、反褶、位移、尺度、微分、积分、卷积和相关

[2]说明: 信号反褶:信号的自变量改变符号，引起信号左右反转对调。

[3]说明: 周期序列的主周期:定义为 0~N-1 对应的一个周期内的数据