卷积

卷积是数学分析中一种重要的运算。设：${\displaystyle f(x)}$ 、${\displaystyle g(x)}$ 是${\displaystyle \mathbb {R} }$ 上的两个可积函数，作积分：

${\displaystyle \int _{-\infty }^{\infty }f(\tau )g(x-\tau )\,\mathrm {d} \tau }$ 

可以证明，关于几乎所有的${\displaystyle x\in (-\infty ,\infty )}$ ，上述积分是存在的。这样，随着${\displaystyle x}$ 的不同取值，这个积分就定义了一个新函数${\displaystyle h(x)}$ ，称为函数${\displaystyle f}$ 与${\displaystyle g}$ 的卷积，记为${\displaystyle h(x)=(f*g)(x)}$ 。我们可以轻易验证：${\displaystyle (f*g)(x)=(g*f)(x)}$ ，并且${\displaystyle (f*g)(x)}$ 仍为可积函数。这就是说，把卷积代替乘法，${\displaystyle L^{1}(R^{1})}$ 空间是一个代数，甚至是巴拿赫代数。虽然这里为了方便我们假设 ${\displaystyle \textstyle f,g\in L^{1}(\mathbb {R} )}$ ，不过卷积只是运算符号，理论上并不需要对函数 ${\displaystyle f,g}$  有特别的限制，虽然常常要求 ${\displaystyle f,g}$  至少是可测函数（measurable function）（如果不是可测函数的话，积分可能根本没有意义），至于生成的卷积函数性质会在运算之后讨论。

卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换，利用此一性质，能简化傅里叶分析中的许多问题。

由卷积得到的函数${\displaystyle f*g}$ 一般要比${\displaystyle f}$ 和${\displaystyle g}$ 都光滑。特别当${\displaystyle g}$ 为具有紧支集的光滑函数，${\displaystyle f}$ 为局部可积时，它们的卷积${\displaystyle f*g}$ 也是光滑函数。利用这一性质，对于任意的可积函数${\displaystyle f}$ ，都可以简单地构造出一列逼近于${\displaystyle f}$ 的光滑函数列${\displaystyle f_{s}}$ ，这种方法称为函数的光滑化或正则化。

卷积的概念还可以推广到数列、测度以及广义函数上去。

函数 ${\displaystyle f,g}$  是定义在 ${\displaystyle \mathbb {R} ^{n}}$  上的可测函数（measurable function），${\displaystyle f}$ 与${\displaystyle g}$ 的卷积记作${\displaystyle f*g}$ ，它是其中一个函数反转（reverse），并平移后，与另一个函数的乘积的积分，是一个对平移量的函数，也就是：

${\displaystyle (f*g)(t)\ \ \,{\stackrel {\mathrm {def} }{=}}\ \int _{\mathbb {R} ^{n}}f(\tau )g(t-\tau )\,d\tau }$ 。

如果函数不是定义在 ${\displaystyle \mathbb {R} ^{n}}$  上，可以把函数定义域以外的值都规定成零，这样就变成一个定义在 ${\displaystyle \mathbb {R} ^{n}}$  上的函数。

对于定义在整数 ${\displaystyle \mathbb {Z} }$  上的函数 ${\displaystyle f,g}$ ，卷积定义为

${\displaystyle (f*g)[n]\ \ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }{f[m]g[n-m]}}$ 

${\displaystyle =\sum _{m=-\infty }^{\infty }f[n-m]\,g[m].}$ 

这里一样把函数定义域以外的值当成零，所以可以扩展函数到所有整数上（如果本来不是的话）。

当${\displaystyle g[n]}$  的支撑集（support）为有限长度${\displaystyle M}$ ，上式会变成有限和：

${\displaystyle (f*g)[n]=\sum _{m=-M}^{M}f[n-m]g[m].}$ 

计算离散卷积的方法

计算卷积${\displaystyle f[n]*g[n]}$ 有三种主要的方法，分别为

1. 直接计算（Direct Method）
2. 快速傅里叶变换（FFT）
3. 分段卷积（sectioned convolution）

方法1是直接利用定义来计算卷积，而方法2和3都是用到了FFT来快速计算卷积。也有不需要用到FFT的作法，如使用数论变换。

方法1：直接计算

• 作法：利用卷积的定义

${\displaystyle y[n]=f[n]*g[n]=\sum _{m=0}^{M-1}f[n-m]g[m]}$ 

• 若${\displaystyle f[n]}$ 和${\displaystyle g[n]}$ 皆为实数信号，则需要${\displaystyle MN}$ 个乘法。

• 若${\displaystyle f[n]}$ 和${\displaystyle g[n]}$ 皆为更一般性的复数信号，不使用复数乘法的快速算法，会需要${\displaystyle 4MN}$ 个乘法;但若使用复数乘法的快速算法，则可简化至${\displaystyle 3MN}$ 个乘法。

因此，使用定义直接计算卷积的复杂度为${\displaystyle O(MN)}$ 。

方法2：快速傅里叶变换（FFT）

• 概念：由于两个离散信号在时域（time domain）做卷积相当于这两个信号的离散傅里叶变换在频域（frequency domain）做相乘：

${\displaystyle y[n]=f[n]*g[n]\leftrightarrow Y[f]=F[f]G[f]}$ 

，可以看出在频域的计算较简单。

• 作法：因此这个方法即是先将信号从时域转成频域：

${\displaystyle F[f]=DFT_{P}(f[n]),G[f]=DFT_{P}(g[n])}$ 

，于是

${\displaystyle Y[f]=DFT_{P}(f[n])DFT_{P}(g[n])}$ 

，最后再将频域信号转回时域，就完成了卷积的计算：

${\displaystyle y[n]=IDFT_{P}{DFT_{P}(f[n])DFT_{P}(g[n])}}$ 

总共做了2次DFT和1次IDFT。

• 特别注意DFT和IDFT的点数${\displaystyle P}$ 要满足${\displaystyle P\geq M+N-1}$ 。

• 由于DFT有快速算法FFT，所以运算量为${\displaystyle O(P\log _{2}P)}$ 

• 假设${\displaystyle P}$ 点DFT的乘法量为${\displaystyle a}$ ，${\displaystyle f[n]}$ 和${\displaystyle g[n]}$ 为一般性的复数信号，并使用复数乘法的快速算法，则共需要${\displaystyle 3a+3P}$ 个乘法。

方法3：分段卷积（sectioned convolution）

• 概念：将${\displaystyle f[n]}$ 切成好几段，每一段分别和${\displaystyle g[n]}$ 做卷积后，再将结果相加。

• 作法：先将${\displaystyle f[n]}$ 切成每段长度为${\displaystyle L}$ 的区段（${\displaystyle L>M}$ ），假设共切成S段：

${\displaystyle f[n](n=0,1,...,N-1)\to f_{1}[n],f_{2}[n],f_{3}[n],...,f_{S}[n](S=\left\lceil {\frac {N}{L}}\right\rceil )}$ 

Section 1: ${\displaystyle f_{1}[n]=f[n],n=0,1,...,L-1}$ 

Section 2: ${\displaystyle f_{2}[n]=f[n+L],n=0,1,...,L-1}$ 

${\displaystyle \vdots }$ 

Section r: ${\displaystyle f_{r}[n]=f[n+(r-1)L],n=0,1,...,L-1}$ 

${\displaystyle \vdots }$ 

Section S: ${\displaystyle f_{S}[n]=f[n+(S-1)L],n=0,1,...,L-1}$ 

，${\displaystyle f[n]}$ 为各个section的和

${\displaystyle f[n]=\sum _{r=1}^{S}f_{r}[n+(r-1)L]}$ 。

因此，

${\displaystyle y[n]=f[n]*g[n]=\sum _{r=1}^{S}\sum _{m=0}^{M-1}f_{r}[n+(r-1)L-m]g[m]}$ ，

每一小段作卷积则是采用方法2，先将时域信号转到频域相乘，再转回时域：

${\displaystyle y[n]=IDFT(\sum _{r=1}^{S}\sum _{m=0}^{M-1}DFT_{P}(f_{r}[n+(r-1)L-m])DFT_{P}(g[m])),P\geq M+L-1}$ 。

• 总共只需要做${\displaystyle P}$ 点FFT ${\displaystyle 2S+1}$ 次，因为${\displaystyle g[n]}$ 只需要做一次FFT。

• 假设${\displaystyle P}$ 点DFT的乘法量为${\displaystyle a}$ ，${\displaystyle f[n]}$ 和${\displaystyle g[n]}$ 为一般性的复数信号，并使用复数乘法的快速算法，则共需要${\displaystyle (2S+1)a+3SP}$ 个乘法。

• 运算量：${\displaystyle {\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}$ 

• 运算复杂度：${\displaystyle O(N)}$ ，和${\displaystyle N}$ 呈线性，较方法2小。
• 分为 Overlap-Add 和 Overlap-Save 两种方法。

分段卷积: Overlap-Add

欲做${\displaystyle x[n]*h[n]}$ 的分段卷积分，${\displaystyle x[n]}$  长度为 ${\displaystyle N}$ ，${\displaystyle h[n]}$  长度为 ${\displaystyle M}$ ,

Step 1: 将${\displaystyle x[n]}$ 每 ${\displaystyle L}$  分成一段

Step 2: 再每段 ${\displaystyle L}$  点后面添加 ${\displaystyle M-1}$  个零，变成长度 ${\displaystyle L+M-1}$ 

Step 3: 把 ${\displaystyle h[n]}$  添加 ${\displaystyle L-1}$ 个零，变成长度 ${\displaystyle L+M-1}$ 的 ${\displaystyle h'[n]}$ 

Step 4: 把每个 ${\displaystyle x[n]}$  的小段和 ${\displaystyle h'[n]}$  做快速卷积，也就是${\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])}\}}$ ，每小段会得到长度 ${\displaystyle L+M-1}$  的时域信号

Step 5: 放置第 ${\displaystyle i}$  个小段的起点在位置 ${\displaystyle L\times i}$  上, ${\displaystyle i=0,1,...,\lceil {\frac {N}{L}}\rceil -1}$ 

Step 6: 会发现在每一段的后面 ${\displaystyle M-1}$  点有重叠，将所有点都相加起来，顾名思义 Overlap-Add，最后得到结果

举例来说:

${\displaystyle x[n]=[1,2,3,4,5,-1,-2,-3,-4,-5,1,2,3,4,5]}$ , 长度 ${\displaystyle N=15}$ 

${\displaystyle h[n]=[1,2,3]}$ , 长度 ${\displaystyle M=3}$ 

令 ${\displaystyle L=5}$ 

•  

  x[n]和h[n]

令 ${\displaystyle L=5}$  切成三段，分别为 ${\displaystyle x_{0}[n],x_{1}[n],x_{2}[n]}$ , 每段填 ${\displaystyle M-1}$  个零，并将 ${\displaystyle h[n]}$  填零至长度 ${\displaystyle L+M-1}$ 

•  

  分段x[n]

将每一段做${\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])}\}}$ 

•  

  分段运算结果

若将每小段摆在一起，可以注意到第一段的范围是 ${\displaystyle 0\thicksim 6}$  ，第二段的范围是 ${\displaystyle 5\thicksim 11}$ ，第三段的范围是 ${\displaystyle 10\thicksim 16}$ ，三段的范围是有重叠的

•  

  合并分段运算结果

最后将三小段加在一起，并将结果和未分段的卷积做比较，上图是分段的结果，下图是没有分段并利用快速卷积所算出的结果，验证两者运算结果相同。

•  

  结果比较图

分段卷积: Overlap-Save

欲做${\displaystyle x[n]*h[n]}$ 的分段卷积分，${\displaystyle x[n]}$  长度为 ${\displaystyle N}$ ，${\displaystyle h[n]}$  长度为 ${\displaystyle M}$ ,

Step 1: 将 ${\displaystyle x[n]}$  前面填 ${\displaystyle M-1}$  个零

Step 2: 第一段 ${\displaystyle i=0}$ , 从新的 ${\displaystyle x[n]}$  中 ${\displaystyle L\times i-(M-1)\times i}$  取到 ${\displaystyle L\times (i+1)-(M-1)\times i-1}$  总共 ${\displaystyle L}$  点当做一段，因此每小段会重复取到前一小段的 ${\displaystyle M-1}$  点，取到新的一段全为零为止

Step 3: 把 ${\displaystyle h[n]}$  添加 ${\displaystyle L-M}$  个零，变成长度 ${\displaystyle L}$  的 ${\displaystyle h'[n]}$ 

Step 4: 把每个 ${\displaystyle x[n]}$  的小段和 ${\displaystyle h'[n]}$  做快速卷积，也就是${\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}}$ ，每小段会得到长度 ${\displaystyle L}$  的时域信号

Step 5: 对于每个 ${\displaystyle i}$  小段，只会保留末端的 ${\displaystyle L-(M-1)}$  点，因此得名 Overlap-Save

Step 6: 将所有保留的点合再一起，得到最后结果

举例来说:

${\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}$ , 长度 ${\displaystyle N=15}$ 

${\displaystyle h[n]=[1,2,3]}$ , 长度 ${\displaystyle M=3}$ 

令 ${\displaystyle L=7}$ 

•  

  x[n]和h[n]

将 ${\displaystyle x[n]}$  前面填 ${\displaystyle M-1}$  个零以后，按照 Step 2 的方式分段，可以看到每一段都重复上一段的 ${\displaystyle M-1}$  点

•  

  分段x[n]

再将每一段做 ${\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}}$ 以后可以得到

•  

  分段运算结果

保留每一段末端的 ${\displaystyle L-(M-1)}$  点，摆在一起以后，可以注意到第一段的范围是 ${\displaystyle 0\thicksim 4}$  ，第二段的范围是 ${\displaystyle 5\thicksim 9}$ ，第三段的范围是 ${\displaystyle 10\thicksim 14}$ ，第四段的范围是 ${\displaystyle 15\thicksim 16}$ ，四段的范围是没有重叠的

•  

  合并分段运算结果

将结果和未分段的卷积做比较，下图是分段的结果，上图是没有分段并利用快速卷积所算出的结果，验证两者运算结果相同。

•  

  结果比较图

至于为什么要把前面 ${\displaystyle M-1}$  丢掉?

以下以一例子来阐述:

${\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10]}$ , 长度 ${\displaystyle L=10}$ ，

${\displaystyle h[n]=[1,2,3,4,5]}$ , 长度 ${\displaystyle M=5}$ ,

第一条蓝线代表 ${\displaystyle y}$  轴，而两条蓝线之间代表长度 ${\displaystyle L}$ ，是在做快速卷积时的周期

•  

  x[n]和h[n]

当在做快速卷积时${\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}}$ ，是把信号视为周期 ${\displaystyle L}$ ，在时域上为循环卷积分,

而在一开始前 ${\displaystyle M-1}$  点所得到的值，是 ${\displaystyle h[0],h[6],h[7],h[8],h[9]}$  和 ${\displaystyle x[0],x[6],x[7],x[8],x[9]}$  内积的值，

然而 ${\displaystyle h[6],h[7],h[8],h[9]}$  这 ${\displaystyle M-1}$  个值应该要为零，以往在做快速卷积时长度为 ${\displaystyle L+M-1}$  时不会遇到这些问题，

而今天因为在做快速卷积时长度为 ${\displaystyle L}$  才会把这 ${\displaystyle M-1}$  点算进来，因此我们要丢弃这 ${\displaystyle M-1}$  点内积的结果

•  

  循环卷积

为了要丢弃这 ${\displaystyle M-1}$  点内积的结果，位移 ${\displaystyle h[-n]}$  ${\displaystyle M-1}$  点，并把位移以后内积合的值才算有效。

•  

  位移以后内积

应用时机

以上三种方法皆可用来计算卷积，其差别在于所需总体乘法量不同。基于运算量以及效率的考量，在计算卷积时，通常会选择所需总体乘法量较少的方法。

以下根据${\displaystyle f[n]}$ 和${\displaystyle g[n]}$ 的长度（${\displaystyle N,M}$ ）分成5类，并列出适合使用的方法：

1. ${\displaystyle M}$ 为一非常小的整数 - 直接计算
2. ${\displaystyle M\ll N}$  - 分段卷积
3. ${\displaystyle M\approx N}$  - 快速傅里叶变换
4. ${\displaystyle M\gg N}$  - 分段卷积
5. ${\displaystyle N}$ 为一非常小的整数 - 直接计算

基本上，以上只是粗略的分类。在实际应用时，最好还是算出三种方法所需的总乘法量，再选择其中最有效率的方法来计算卷积。

例子

Q1：当${\displaystyle N=2000,M=17}$ ，适合用哪种方法计算卷积?

Ans：

方法1：所需乘法量为${\displaystyle 3MN=102000}$ 

方法2：${\displaystyle P\geq M+N-1=2016}$ ，而2016点的DFT最少乘法数${\displaystyle a=12728}$ ，所以总乘法量为${\displaystyle 3(a+P)=44232}$ 

方法3：

若切成8块（${\displaystyle S=8}$ ），则${\displaystyle L=250,P\geq M+L-1=266}$ 。选${\displaystyle P=288}$ ，则总乘法量为${\displaystyle (2S+1)a+3SP=26632}$ ，比方法1和2少了很多。

但是若要找到最少的乘法量，必须依照以下步骤

(1)先找出${\displaystyle L}$ :解${\displaystyle L}$  : ${\displaystyle {\frac {\partial {{\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}}{\partial L}}=0}$ 

(2)由${\displaystyle P\geq L+M-1}$ 算出点数在${\displaystyle P}$ 附近的DFT所需最少的乘法量，选择DFT的点数

(3)最后由${\displaystyle L=P+1-M}$ 算出${\displaystyle L_{opt}}$ 

因此，

(1)由运算量对${\displaystyle L}$ 的偏微分为0而求出${\displaystyle L=85}$ 

(2)${\displaystyle P\geq L+M-1=101}$ ，所以选择101点DFT附近点数乘法量最少的点数${\displaystyle P=96}$ 或${\displaystyle P=120}$ 。

(3-1)当${\displaystyle P=96\to a=280,L=P+1-M=80\to S=25}$ ，总乘法量为${\displaystyle (2S+1)a+3SP=21480}$ 。

(3-2)当${\displaystyle P=120\to a=380,L=P+1-M=104\to S=20}$ ，总乘法量为${\displaystyle (2S+1)a+3SP=22780}$ 。

由此可知，切成20块会有较好的效率，而所需总乘法量为21480。

• 因此，当${\displaystyle N=2000,M=17}$ ，所需总乘法量：分段卷积<快速傅里叶变换<直接计算。故，此时选择使用分段卷积来计算卷积最适合。

Q2：当${\displaystyle N=1024,M=3}$ ，适合用哪种方法计算卷积?

Ans：

方法1：所需乘法量为${\displaystyle 3MN=9216}$ 

方法2：${\displaystyle P\geq M+N-1=1026}$ ，选择1026点DFT附近点数乘法量最少的点数，${\displaystyle \to P=1152,a=7088}$ 。

因此，所需乘法量为${\displaystyle 3(a+P)=24342}$ 

方法3：

(1)由运算量对${\displaystyle L}$ 的偏微分为0而求出${\displaystyle L=5}$ 

(2)${\displaystyle P\geq L+M-1=7}$ ，所以选择7点DFT附近点数乘法量最少的点数${\displaystyle P=8}$ 或${\displaystyle P=6}$ 或${\displaystyle P=4}$ 。

(3-1)当${\displaystyle P=8\to a=4,L=P+1-M=6\to S=171}$ ，总乘法量为${\displaystyle (2S+1)a+3SP=5476}$ 。

(3-2)当${\displaystyle P=6\to a=4,L=P+1-M=4\to S=256}$ ，总乘法量为${\displaystyle (2S+1)a+3SP=6660}$ 。

(3-3)当${\displaystyle P=4\to a=0,L=P+1-M=2\to S=512}$ ，总乘法量为${\displaystyle (2S+1)a+3SP=6144}$ 。

由此可知，切成171块会有较好的效率，而所需总乘法量为5476。

• 因此，当${\displaystyle N=1024,M=3}$ ，所需总乘法量：分段卷积<直接计算<快速傅里叶变换。故，此时选择使用分段卷积来计算卷积最适合。
• 虽然当${\displaystyle M}$ 是个很小的正整数时，大致上适合使用直接计算。但实际上还是将3个方法所需的乘法量都算出来，才能知道用哪种方法可以达到最高的效率。

Q3：当${\displaystyle N=1024,M=600}$ ，适合用哪种方法计算卷积?

Ans：

方法1：所需乘法量为${\displaystyle 3MN=1843200}$ 

方法2：${\displaystyle P\geq M+N-1=1623}$ ，选择1026点DFT附近点数乘法量最少的点数，${\displaystyle \to P=2016,a=12728}$ 。

因此，所需乘法量为${\displaystyle 3(a+P)=44232}$ 

方法3：

(1)由运算量对${\displaystyle L}$ 的偏微分为0而求出${\displaystyle L=1024}$ 

(2)${\displaystyle P\geq L+M-1=1623}$ ，所以选择1623点DFT附近点数乘法量最少的点数${\displaystyle P=2016}$ 。

(3)当${\displaystyle P=2016\to a=12728,L=P+1-M=1417\to S=1}$ ，总乘法量为${\displaystyle (2S+1)a+3SP=44232}$ 。

由此可知，此时切成一段，就跟方法2一样，所需总乘法量为44232。

• 因此，当${\displaystyle N=1024,M=600}$ ，所需总乘法量：快速傅里叶变换 = 分段卷积<直接计算。故，此时选择使用分段卷积来计算卷积最适合。

按照翻转、平移、积分的定义，还可以类似的定义多元函数上的积分：

${\displaystyle (f*g)(t_{1},t_{2},\cdots ,t_{n})=\int \int \cdots \int f(\tau _{1},\tau _{2},\cdots ,\tau _{n})g(t_{1}-\tau _{1},t_{2}-\tau _{2},\cdots ,t_{n}-\tau _{n},)\,d\tau _{1}d\tau _{2}\cdots d\tau _{n}}$ 

各种卷积算子都满足下列性质：

交换律

${\displaystyle f*g=g*f\,}$ 

结合律

${\displaystyle f*(g*h)=(f*g)*h\,}$ 

分配律

${\displaystyle f*(g+h)=(f*g)+(f*h)\,}$ 

数乘结合律

${\displaystyle a(f*g)=(af)*g=f*(ag)\,}$ 

其中${\displaystyle a}$ 为任意实数（或复数）。

微分定理

${\displaystyle {\mathcal {D}}(f*g)={\mathcal {D}}f*g=f*{\mathcal {D}}g\,}$ 

其中Df表示f的微分，如果在离散域中则是指差分算子，包括前向差分与后向差分两种：

• 前向差分：${\displaystyle {\mathcal {D}}^{+}f(n)=f(n+1)-f(n)}$ 
• 后向差分：${\displaystyle {\mathcal {D}}^{-}f(n)=f(n)-f(n-1)}$ 

卷积定理指出，函数卷积的傅里叶变换是函数傅里叶变换的乘积。即，一个域中的卷积相当于另一个域中的乘积，例如时域中的卷积就对应于频域中的乘积。

${\displaystyle {\mathcal {F}}(f*g)={\mathcal {F}}(f)\cdot {\mathcal {F}}(g)}$ 

其中${\displaystyle {\mathcal {F}}(f)}$ 表示f的傅里叶变换。

这一定理对拉普拉斯变换、双边拉普拉斯变换、Z变换、Mellin变换和Hartley变换（参见Mellin inversion theorem（英语：Mellin inversion theorem））等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。

利用卷积定理可以简化卷积的运算量。对于长度为${\displaystyle n}$ 的序列，按照卷积的定义进行计算，需要做${\displaystyle 2n-1}$ 组对位乘法，其计算复杂度为${\displaystyle {\mathcal {O}}(n^{2})}$ ；而利用傅里叶变换将序列变换到频域上后，只需要一组对位乘法，利用傅里叶变换的快速算法之后，总的计算复杂度为${\displaystyle {\mathcal {O}}(n\log n)}$ 。这一结果可以在快速乘法计算中得到应用。

若G是有某m 测度的群（例如豪斯多夫空间上哈尔测度下局部紧致的拓扑群），对于G上m-勒贝格可积的实数或复数函数f和g，可定义它们的卷积：

${\displaystyle (f*g)(x)=\int _{G}f(y)g(xy^{-1})\,dm(y)\,}$ 

对于这些群上定义的卷积同样可以给出诸如卷积定理等性质，但是这需要对这些群的表示理论以及调和分析的彼得-外尔定理。

卷积在科学、工程和数学上都有很多应用：

• 代数中，整数乘法和多项式乘法都是卷积。
• 图像处理中，用作图像模糊、锐化、边缘检测。
• 统计学中，加权的滑动平均是一种卷积。
• 概率论中，两个统计独立变量X与Y的和的概率密度函数是X与Y的概率密度函数的卷积。
• 声学中，回声可以用源声与一个反映各种反射效应的函数的卷积表示。
• 电子工程与信号处理中，任一个线性系统的输出都可以通过将输入信号与系统函数（系统的冲激响应）做卷积获得。
• 物理学中，任何一个线性系统（符合叠加原理）都存在卷积。

• 反卷积
• 自相关函数
• 傅里叶变换

• Convolution. PlanetMath. 
• Visual convolution Java Applet （页面存档备份，存于互联网档案馆）
• Lecture notes, Jian-Jiun Ding (2013), Advanced Digital Signal Processing（页面存档备份，存于互联网档案馆）