卷积

卷积、互相关和自相关的图示比较。运算涉及函数$f$，并假定$f$的高度是1.0，在5个不同点上的值，用在每个点下面的阴影面积来指示。$f$的对称性是卷积$g*f$和互相关$f\star g$在这个例子中相同的原因。

在泛函分析中，卷积（convolution），或译为叠积、褶积或旋积，是透过两个函数$f$和$g$生成第三个函数的一种数学算子，表征函数$f$与经过翻转和平移的$g$的乘积函数所围成的曲边梯形的面积。如果将参加卷积的一个函数看作区间的指示函数，卷积还可以被看作是“移动平均”的推广。

定义

卷积是数学分析中一种重要的运算。设：$f(t)$和$g(t)$是实数$\mathbb {R}$上的两个可积函数，定义二者的卷积$(f*g)(t)$为如下特定形式的积分变换：

$(f*g)(t)\triangleq \int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,\mathrm {d} \tau$

$(f*g)(t)$仍为可积函数，并且有着：

$(f*g)(t)\triangleq \int _{-\infty }^{\infty }f(t-\tau )g(\tau )\,d\tau =(g*f)(t)$

函数$f$和$g$，如果只支撑在$[0,\infty ]$之上，则积分界限可以截断为：

$(f*g)(t)=\int _{0}^{t}f(\tau )g(t-\tau )\,d\tau \quad$对于$\ f,g:[0,\infty )\to \mathbb {R}$

对于两个得出复数值的多元实变函数，可以定义二者的卷积为如下形式的多重积分：

${\begin{aligned}(f*g)(t_{1},t_{2},\cdots ,t_{n})&\triangleq \int \int \cdots \int _{\mathbb {R} ^{n}}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}\\&\triangleq \int _{\mathbb {R} ^{n}}f(\tau )g(t-\tau )\,d^{n}\tau \end{aligned}}$

卷积有一个通用的工程上的符号约定：

$f(t)*g(t)\triangleq \underbrace {\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau } _{(f*g)(t)}$

它必须被谨慎解释以避免混淆。例如：$f(t)*g(t-t_{0})$等价于$(f*g)(t-t_{0})$，而$f(t-t_{0})*g(t-t_{0})$却实际上等价于$(f*g)(t-2t_{0})$。

历史

卷积运算的最早使用出现在达朗贝尔于1754年出版的《宇宙体系的几个要点研究》中对泰勒定理的推导之中。还有西尔维斯特·拉克鲁瓦，将${\textstyle \int f(u)\cdot g(x-u)\,du}$类型的表达式，用在他的1797年–1800年出版的著作《微分与级数论文》中。此后不久，卷积运算出现在皮埃尔-西蒙·拉普拉斯、约瑟夫·傅里叶和西梅翁·泊松等人的著作中。这个运算以前有时叫做“Faltung”（德语中的折叠）、合成乘积、叠加积分或卡森积分。

“卷积”这个术语早在1903年就出现了，然而其定义在早期使用中是相当生僻的，直到1950年代或1960年代之前都未曾广泛使用。

简介

如果$f$和$g$都是在L^p 空间$L^{1}(\mathbb {R} ^{n})$内的勒贝格可积函数，则二者的卷积存在，并且在这种情况下$f*g$也是可积的。这是托内利定理的结论。对于在$L^{1}$中的函数在离散卷积下，或更一般的对于在任何群的上的卷积，这也是成立的。同样的，如果$f\in L^{1}(\mathbb {R} ^{n})$而$g\in L^{p}(\mathbb {R} ^{n})$，这里的$1\leq p\leq \infty$，则$f*g\in L^{p}(\mathbb {R} ^{n})$，并且其L^p 范数间有着不等式：

$\|{f}*g\|_{p}\leq \|f\|_{1}\|g\|_{p}$

在$p=1$的特殊情况下，这显示出$L^{1}$是在卷积下的巴拿赫代数（并且如果$f$和$g$几乎处处非负则两边间等式成立）。

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

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

函数$f(t)$和$g(t)$的互相关$(f\star g)(\tau )$，等价于$f(-\tau )$的共轭复数${\overline {f(-\tau )}}$与$g(\tau )$的卷积：

$(f\star g)(\tau )\triangleq \int _{-\infty }^{\infty }{\overline {f(t-\tau )}}g(t)\,dt={\overline {f(-\tau )}}*g(\tau )$

这里的$\tau$叫做移位（displacement）或滞后（lag）。

对于单位脉冲函数$\delta (t)$和某个函数$h(t)$，二者得到的卷积就是$h(t)$本身，此$h(t)$被称为冲激响应：

$(\delta *h)(t)=\int _{-\infty }^{\infty }\delta (\tau )h(t-\tau )\,d\tau =h(t)$

在连续时间线性非时变系统中，输出信号$y(t)$被描述为输入信号$x(t)$与冲激响应$h(t)$的卷积：

$y(t)=(x*h)(t)\ \triangleq \ \int \limits _{-\infty }^{\infty }x(t-\tau )\cdot h(\tau )\,\mathrm {d} \tau =\int \limits _{-\infty }^{\infty }x(\tau )\cdot h(t-\tau )\,\mathrm {d} \tau$

两个独立的随机变量$U$和$V$，每个都有一个概率密度函数，二者之和的概率密度，是它们单独的密度函数的卷积：

$f_{U+V}(x)=\int _{-\infty }^{\infty }f_{U}(y)f_{V}(x-y)\,dy=\left(f_{U}*f_{V}\right)(x)$

图解

已知右侧第一行图中两个函数$f(t)$和$g(t)$。 首先将两个函数都用约束变量$\tau$来表示，并将$g(\tau )$翻转至纵轴另一侧，从而得到右侧第二行图中$f(\tau )$和$g(-\tau )$。 向函数$g(-\tau )$增加一个时间偏移量$t$，得到函数$g(-(\tau -t))=g(t-\tau )$。$t$不是常数而是自由变量，当$t$取不同值时，$g(t-\tau )$能沿着$\tau$轴“滑动”。如果$t$是正值，则$g(t-\tau )$等于$g(-\tau )$沿着$\tau$轴向右（朝向$+\infty$）滑动数量$t$。如果$t$是负值，则$g(t-\tau )$等价于$g(-\tau )$向左（朝向$-\infty$）滑动数量$|t|$。 让$t$从$-\infty$变化至$+\infty$，当两个函数交会时，计算交会范围中两个函数乘积的积分值。换句话说，在时间$t$，计算函数$f(\tau )$经过权重函数$g(t-\tau )$施以权重后其下的面积。右侧第三、第四和第五行图中，分别是$t=0$、$t=2.5$和$t=5.5$时的情况，从$t>1$时开始有交会，例如在第四行图中，$\tau =0$则$g(t-\tau )=g(2.5)$，$\tau =1.5$则$g(t-\tau )=g(1)$，对于$\tau \notin [0,1.5]$有着$f(\tau )g(t-\tau )=0$。 最后得到的波形（未包含在此图中）就是$f$和$g$的卷积。
两个矩形脉冲波的卷积。其中函数$g$首先对$\tau =0$反射，接着平移$t$，成为$g(t-\tau )$。那么重叠部分的面积就相当于$t$处的卷积，其中横坐标代表待变量$\tau$以及新函数$f\ast g$的自变量$t$。
矩形脉冲波和指数衰减脉冲波的卷积（后者可能出现于RC电路中），同样地重叠部分面积就相当于$t$处的卷积。注意到因为$g$是对称的，所以在这两张图中，反射并不会改变它的形状。

周期卷积

主条目：圆周卷积

矩形脉冲波和指数衰减脉冲波的周期卷积

两个$T$周期的函数$h_{_{T}}(t)$和$x_{_{T}}(t)$的“周期卷积”定义为：

$\int _{t_{0}}^{t_{0}+T}h_{_{T}}(\tau )x_{_{T}}(t-\tau )\,d\tau$

这里的$t_{0}$是任意参数。

任何可积分函数$s(t)$，都可以通过求函数$s(t)$的所有整数倍$P$的平移的总和，从而制作出具有周期$P$的周期函数 $s_{_{P}}(t)$，这叫做周期求和：

$s_{_{P}}(t)\triangleq \sum _{m=-\infty }^{\infty }s(t+mP)=\sum _{m=-\infty }^{\infty }s(t-mP),\quad m\in \mathbb {Z}$

对于无周期函数$h$与$x$，其周期$T$的周期求和分别是$h_{_{T}}(t)$与$x_{_{T}}(t)$，$h$与$x$的周期卷积，可以定义为$h(t)$与$x_{_{T}}(t)$的常规卷积，或$x(t)$与$h_{_{T}}(t)$的常规卷积，二者都等价于$h_{_{T}}(t)$与$x_{_{T}}(t)$的周期积分：

$(h*x_{_{T}})(t)\ \triangleq \ \ \int _{-\infty }^{\infty }h(\tau )x_{_{T}}(t-\tau )\,d\tau \ =\ \int _{t_{0}}^{t_{0}+T}h_{_{T}}(\tau )x_{_{T}}(t-\tau )\,d\tau$

$(h*x_{_{T}})(t)=(x*h_{_{T}})(t)$

圆周卷积是周期卷积的特殊情况，其中函数$h$和$x$二者的非零部分，都限定在区间$[0,T]$之内，此时的周期求和称为“周期延拓”。$h*x_{_{T}}$中函数$x_{_{T}}$可以通过取非负余数的模除运算表达为“圆周函数”：

$x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R}$

而积分的界限可以缩简至函数$h$的长度范围$[0,T]$：

$(h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )x((t-\tau )_{\mathrm {mod} \ T})\ d\tau$

离散卷积

离散卷积示意图

对于定义在整数$\mathbb {Z}$上且得出复数值的函数$f[n]$和$g[n]$，离散卷积定义为：

$(f*g)[n]\ \ \triangleq \ \sum _{m=-\infty }^{\infty }{f[m]g[n-m]}=\sum _{m=-\infty }^{\infty }f[n-m]\,g[m]$

这里一样把函数定义域以外的值当成零，所以可以扩展函数到所有整数上（如果本来不是的话）。两个有限序列的卷积的定义，是将这些序列扩展成在整数集合上有限支撑的函数。在这些序列是两个多项式的系数之时，这两个多项式的普通乘积的系数，就是这两个序列的卷积。这叫做序列系数的柯西乘积。

当$g[n]$的支撑集为有限长度的$\{-M,-M+1,\dots ,M-1,M\}$之时，上式会变成有限求和：

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

多维离散卷积

主条目：多维离散卷积

用离散二维卷积对图像进行锐化处理的动画

类似于一维情况，使用星号表示卷积，而维度体现在星号的数量上，$M$维卷积就写为$M$个星号。下面是$M$维信号的卷积的表示法：

$y(n_{1},n_{2},...,n_{_{M}})=h(n_{1},n_{2},...,n_{_{M}})*{\overset {M}{\cdots }}*x(n_{1},n_{2},...,n_{_{M}})$

对于离散值的信号，这个卷积可以直接如下这样计算：

$\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }...\sum _{k_{_{M}}=-\infty }^{\infty }h(k_{1},k_{2},...,k_{_{M}})x(n_{1}-k_{1},n_{2}-k_{2},...,n_{_{M}}-k_{_{M}})$

结果的离散多维卷积所支撑的输出区域，基于两个输入信号所支撑的大小和区域来决定。

在两个二维信号之间的卷积的可视化

离散周期卷积

对比离散无周期卷积（左列）与离散圆周卷积（右列）

对于离散序列和一个参数$N$，无周期函数$h$和$x$的“周期卷积”是为：

$(h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}\ =\ \sum _{m=0}^{N-1}\left(\sum _{k=-\infty }^{\infty }{h}[m-kN]\right)x_{_{N}}[n-m]$

这个函数有周期$N$，它有最多$N$个唯一性的值。$h$和$x$的非零范围都是$[0,N-1]$的特殊情况叫做圆周卷积：

$(h*x_{_{N}})[n]=\sum _{m=0}^{N-1}h[m]x_{_{N}}[n-m]=\sum _{m=0}^{N-1}h[m]x[(n-m)_{\bmod {N}}]$

离散圆周卷积可简约为矩阵乘法，这里的积分变换的核函数是循环矩阵:

${\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{_{N-1}}\end{bmatrix}}={\begin{bmatrix}h_{0}&h_{_{N-1}}&\cdots &h_{1}\\h_{1}&h_{0}&\cdots &h_{2}\\\vdots &\vdots &\ddots &\vdots \\h_{_{N-1}}&h_{_{N-2}}&\cdots &h_{0}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\\vdots \\x_{_{N-1}}\end{bmatrix}}$

圆周卷积最经常出现的快速傅里叶变换的实现算法比如雷德算法之中。

性质

代数

主条目：卷积代数

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

交换律

$f*g=g*f\,$

结合律

$f*(g*h)=(f*g)*h\,$

分配律

$f*(g+h)=(f*g)+(f*h)\,$

数乘结合律

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

其中$a$为任意实数（或复数）。

复数共轭

${\overline {f*g}}={\overline {f}}*{\overline {g}}$

微分有关

$(f*g)'=f'*g=f*g'$

积分有关

如果${\textstyle F(t)=\int _{-\infty }^{t}f(\tau )d\tau }$，并且${\textstyle G(t)=\int _{-\infty }^{t}g(\tau )\,d\tau }$，则有：

$(F*g)(t)=(f*G)(t)=\int _{-\infty }^{t}(f*g)(\tau )\,d\tau$

积分

如果$f$和$g$是可积分函数，则它们在整个空间上的卷积的积分，简单的就是它们积分的乘积：

$\int _{\mathbb {R} ^{n}}(f*g)(t)\,d^{n}t=\left(\int _{\mathbb {R} ^{n}}f(t)\,d^{n}t\right)\left(\int _{\mathbb {R} ^{n}}g(t)\,d^{n}t\right)$

这是富比尼定理的结果。如果$f$和$g$只被假定为非负可测度函数，根据托内利定理，这也是成立的。

微分

在一元函数情况下，$f$和$g$的卷积的导数有着：

${\frac {d}{dt}}(f*g)={\frac {df}{dt}}*g=f*{\frac {dg}{dt}}$

这里的${\frac {d}{dt}}$是微分算子。更一般的说，在多元函数的情况下，对偏导数也有类似的公式：

${\frac {\partial }{\partial t_{i}}}(f*g)={\frac {\partial f}{\partial t_{i}}}*g=f*{\frac {\partial g}{\partial t_{i}}}$

这就有了一个特殊结论，卷积可以看作“光滑”运算：$f$和$g$的卷积可微分的次数，是$f$和$g$的总数。

这些恒等式成立的严格条件，为$f$和$g$是绝对可积分的，并且至少二者之一有绝对可积分（$L^{1}$）弱导数，这是Young卷积不等式的结论。

在离散情况下，差分算子$\Delta [f](n)=f(n+1)-f(n)$满足类似的关系：

$\Delta (f*g)=(\Delta f)*g=f*(\Delta g)$

卷积定理

主条目：卷积定理

卷积定理指出，在适当的条件下，两个函数（或信号）的卷积的傅里叶变换，是它们的傅里叶变换的逐点乘积。更一般的说，在一个域（比如时域）中的卷积等于在其他域（比如频域）逐点乘法。

设两个函数$g(x)$和$h(x)$，分别具有傅里叶变换$G(s)$和$H(s)$：

${\begin{aligned}G(s)&\triangleq {\mathcal {F}}\{g\}(s)=\int _{-\infty }^{\infty }g(x)e^{-i2\pi sx}\,dx,\quad s\in \mathbb {R} \\H(s)&\triangleq {\mathcal {F}}\{h\}(s)=\int _{-\infty }^{\infty }h(x)e^{-i2\pi sx}\,dx,\quad s\in \mathbb {R} \end{aligned}}$

这里的${\mathcal {F}}$算子指示傅里叶变换。

卷积定理声称：

${\mathcal {F}}\{g*h\}(s)=G(s)H(s),\quad s\in \mathbb {R}$

${\mathcal {F}}\{g\cdot h\}(s)=G(s)*H(s),\quad s\in \mathbb {R}$

应用逆傅里叶变换${\mathcal {F}}^{-1}$产生推论：

$(g*h)(s)={\mathcal {F}}^{-1}\{G\cdot H\},\quad s\in \mathbb {R}$

$(g\cdot h)(s)={\mathcal {F}}^{-1}\{G*H\},\quad s\in \mathbb {R}$

这里的算符$\,\cdot \,$指示逐点乘法。

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

周期卷积

对于周期为$P$的函数$g_{_{P}}(x)$和$h_{_{P}}(x)$，可以被表达为二者的周期求和：

${\begin{aligned}g_{_{P}}(x)\ &\triangleq \sum _{m=-\infty }^{\infty }g(x-mP),\quad m\in \mathbb {Z} \\h_{_{P}}(x)\ &\triangleq \sum _{m=-\infty }^{\infty }h(x-mP),\quad m\in \mathbb {Z} \end{aligned}}$

它们的傅里叶级数系数为：

${\begin{aligned}G[k]&\triangleq {\mathcal {F}}\{g_{_{P}}\}[k]={\frac {1}{P}}\int _{P}g_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \\H[k]&\triangleq {\mathcal {F}}\{h_{_{P}}\}[k]={\frac {1}{P}}\int _{P}h_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \end{aligned}}$

这里的${\mathcal {F}}$算子指示傅里叶级数积分。

逐点乘积$g_{_{P}}(x)\cdot h_{_{P}}(x)$的周期也是$P$，它的傅里叶级数系数为：

${\mathcal {F}}\{g_{_{P}}\cdot h_{_{P}}\}[k]=(G*H)[k]$

周期卷积$(g_{_{P}}*h)(x)$的周期也是$P$，周期卷积的卷积定理为：

${\mathcal {F}}\{g_{_{P}}*h\}[k]=\ P\cdot G[k]\ H[k]$

离散卷积

对于作为两个连续函数采样的序列$g[n]$和$h[n]$，它们具有离散时间傅里叶变换$G(s)$和$H(s)$：

${\begin{aligned}G(s)&\triangleq {\mathcal {F}}\{g\}(s)=\sum _{n=-\infty }^{\infty }g[n]\cdot e^{-i2\pi sn}\;,\quad s\in \mathbb {R} \\H(s)&\triangleq {\mathcal {F}}\{h\}(s)=\sum _{n=-\infty }^{\infty }h[n]\cdot e^{-i2\pi sn}\;,\quad s\in \mathbb {R} \end{aligned}}$

这里的${\mathcal {F}}$算子指示离散时间傅里叶变换（DTFT）。

离散卷积的卷积定理为：

${\mathcal {F}}\{g*h\}(s)=\ G(s)H(s)$

离散周期卷积

对于周期为$N$的序列$g_{_{N}}[n]$和$h_{_{N}}[n]$：

${\begin{aligned}g_{_{N}}[n]\ &\triangleq \sum _{m=-\infty }^{\infty }g[n-mN],\quad m,n\in \mathbb {Z} \\h_{_{N}}[n]\ &\triangleq \sum _{m=-\infty }^{\infty }h[n-mN],\quad m,n\in \mathbb {Z} \end{aligned}}$

相较于离散时间傅里叶变换$G(s)$和$H(s)$的周期是$1$，它们是按间隔$1/N$采样$G(s)$和$H(s)$，并在$N$个采样上进行了逆离散傅里叶变换（DFT^-1或IDFT）的结果。

离散周期卷积$(g_{_{N}}*h)[n]$的周期也是$N$。离散周期卷积定理为：

${\mathcal {F}}\{g_{_{N}}*h\}[k]=\ \underbrace {{\mathcal {F}}\{g_{_{N}}\}[k]} _{G(k/N)}\cdot \underbrace {{\mathcal {F}}\{h_{_{N}}\}[k]} _{H(k/N)},\quad k,n\in \mathbb {Z}$

这里的${\mathcal {F}}$算子指示长度$N$的离散傅里叶变换（DFT）。

它有着推论：

$(g_{_{N}}*h)[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{g_{_{N}}\}\cdot {\mathcal {F}}\{h_{_{N}}\}\}$

对于其非零时段小于等于$N$的$g$和$h$，离散圆周卷积的卷积定理为：

$(g_{_{N}}*h)[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{g\}\cdot {\mathcal {F}}\{h\}\}$

推广

卷积的概念还可以推广到数列、测度以及广义函数上去。函数$f,g$是定义在$\mathbb {R} ^{n}$上的可测函数（measurable function），$f$与$g$存在卷积并记作$f*g$。如果函数不是定义在$\mathbb {R} ^{n}$上，可以把函数定义域以外的值都规定成零，这样就变成一个定义在$\mathbb {R} ^{n}$上的函数。

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

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

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

离散卷积的计算方法

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

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

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

方法1：直接计算

• 作法：利用卷积的定义

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

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

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

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

方法2：快速傅里叶变换

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

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

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

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

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

，于是

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

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

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

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

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

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

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

方法3：分段卷积

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

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

$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: $f_{1}[n]=f[n],n=0,1,...,L-1$

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

$\vdots$

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

$\vdots$

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

，$f[n]$为各个section的和

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

因此，

$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，先将时域信号转到频域相乘，再转回时域：

$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$。

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

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

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

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

分段卷积: Overlap-Add

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

Step 1: 将$x[n]$每 $L$ 分成一段

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

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

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

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

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

举例来说:

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

$h[n]=[1,2,3]$, 长度 $M=3$

令 $L=5$

• 
  x[n]和h[n]

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

• 
  分段x[n]

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

• 
  分段运算结果

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

• 
  合并分段运算结果

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

• 
  结果比较图

分段卷积: Overlap-Save

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

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

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

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

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

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

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

举例来说:

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

$h[n]=[1,2,3]$, 长度 $M=3$

令 $L=7$

• 
  x[n]和h[n]

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

• 
  分段x[n]

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

• 
  分段运算结果

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

• 
  合并分段运算结果

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

• 
  结果比较图

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

以下以一例子来阐述:

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

$h[n]=[1,2,3,4,5]$, 长度 $M=5$,

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

• 
  x[n]和h[n]

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

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

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

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

• 
  循环卷积

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

• 
  位移以后内积

应用时机

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

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

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

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

例子

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

Ans：

方法1：所需乘法量为$3MN=102000$

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

方法3：

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

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

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

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

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

因此，

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

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

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

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

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

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

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

Ans：

方法1：所需乘法量为$3MN=9216$

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

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

方法3：

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

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

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

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

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

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

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

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

Ans：

方法1：所需乘法量为$3MN=1843200$

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

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

方法3：

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

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

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

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

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

应用

高斯模糊可被用来从半色调印刷品复原出光滑灰度数字图像。

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

• 代数中，整数乘法和多项式乘法都是卷积。
• 卷积神经网络应用了多重级联的卷积核心，它被用于机器视觉和人工智能，尽管在多数情况下实际上用的是互相关而非卷积。
• 在非人工智能的图像处理中，用作图像模糊、锐化、边缘检测。
• 统计学中，加权的滑动平均是一种卷积。
• 概率论中，两个统计独立变量X与Y的和的概率密度函数是X与Y的概率密度函数的卷积。
• 声学中，回声可以用源声与一个反映各种反射效应的函数的卷积表示。
• 电子工程与信号处理中，任一个线性系统的输出都可以通过将输入信号与系统函数（系统的冲激响应）做卷积获得。
• 物理学中，任何一个线性系统（符合叠加原理）都存在卷积。

参见

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

延伸阅读

• Bracewell, R., The Fourier Transform and Its Applications 2nd, McGraw–Hill, 1986, ISBN 0-07-116043-4 .
• Damelin, S.; Miller, W., The Mathematics of Signal Processing, Cambridge University Press, 2011, ISBN 978-1107601048 
• Diggle, P. J., A kernel method for smoothing point process data, Journal of the Royal Statistical Society, Series C, 1985, 34 (2): 138–147, JSTOR 2347366, S2CID 116746157, doi:10.2307/2347366 
• Dominguez-Torres, Alejandro (Nov 2, 2010). "Origin and history of convolution". 41 pgs. http://www.slideshare.net/Alexdfar/origin-adn-history-of-convolution （页面存档备份，存于互联网档案馆）. Cranfield, Bedford MK43 OAL, UK. Retrieved Mar 13, 2013.
• Ghasemi, S. Hooman; Nowak, Andrzej S., Reliability Index for Non-normal Distributions of Limit State Functions, Structural Engineering and Mechanics, 2017, 62 (3): 365–372, doi:10.12989/sem.2017.62.3.365 
• Grinshpan, A. Z., An inequality for multiple convolutions with respect to Dirichlet probability measure, Advances in Applied Mathematics, 2017, 82 (1): 102–119, doi:10.1016/j.aam.2016.08.001  
• Hewitt, Edwin; Ross, Kenneth A., Abstract harmonic analysis. Vol. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 115 2nd, Berlin, New York: Springer-Verlag, 1979, ISBN 978-3-540-09434-0, MR 0551496 .
• Hewitt, Edwin; Ross, Kenneth A., Abstract harmonic analysis. Vol. II: Structure and analysis for compact groups. Analysis on locally compact Abelian groups, Die Grundlehren der mathematischen Wissenschaften, Band 152, Berlin, New York: Springer-Verlag, 1970, MR 0262773 .
• Hörmander, L., The analysis of linear partial differential operators I, Grundl. Math. Wissenschaft. 256, Springer, 1983, ISBN 3-540-12104-8, MR 0717035, doi:10.1007/978-3-642-96750-4 .
• Kassel, Christian, Quantum groups, Graduate Texts in Mathematics 155, Berlin, New York: Springer-Verlag, 1995, ISBN 978-0-387-94370-1, MR 1321145, doi:10.1007/978-1-4612-0783-2  含有内容需登入查看的页面 (link).
• Knuth, Donald, Seminumerical Algorithms 3rd., Reading, Massachusetts: Addison–Wesley, 1997, ISBN 0-201-89684-2 .
• Template:Narici Beckenstein Topological Vector Spaces
• Reed, Michael; Simon, Barry, Methods of modern mathematical physics. II. Fourier analysis, self-adjointness, New York-London: Academic Press Harcourt Brace Jovanovich, Publishers: xv+361, 1975, ISBN 0-12-585002-6, MR 0493420 
• Rudin, Walter, Fourier analysis on groups, Interscience Tracts in Pure and Applied Mathematics 12, New York–London: Interscience Publishers, 1962, ISBN 0-471-52364-X, MR 0152834 .
• Template:Schaefer Wolff Topological Vector Spaces
• Stein, Elias; Weiss, Guido, Introduction to Fourier Analysis on Euclidean Spaces, Princeton University Press, 1971, ISBN 0-691-08078-X  含有内容需登入查看的页面 (link).
• Sobolev, V.I., Convolution of functions, Hazewinkel, Michiel (编), 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4 .
• Strichartz, R., A Guide to Distribution Theory and Fourier Transforms, CRC Press, 1994, ISBN 0-8493-8273-4 .
• Titchmarsh, E, Introduction to the theory of Fourier integrals 2nd, New York, N.Y.: Chelsea Pub. Co., 19481986, ISBN 978-0-8284-0324-5 .
• Template:Trèves François Topological vector spaces, distributions and kernels
• Uludag, A. M., On possible deterioration of smoothness under the operation of convolution, J. Math. Anal. Appl., 1998, 227 (2): 335–358, doi:10.1006/jmaa.1998.6091  
• von zur Gathen, J.; Gerhard, J ., Modern Computer Algebra, Cambridge University Press, 2003, ISBN 0-521-82646-2 .
• Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John R. Discrete-time signal processing 2nd. Upper Saddle River,N.J.: Prentice Hall. 1999: 548, 571. ISBN 0-13-754920-2.  含有内容需登入查看的页面 (link)
• McGillem, Clare D.; Cooper, George R. Continuous and Discrete Signal and System Analysis 2. Holt, Rinehart and Winston. 1984. ISBN 0-03-061703-0. 

外部链接

• Earliest Uses: The entry on Convolution has some historical information. （页面存档备份，存于互联网档案馆）
• Convolution, on The Data Analysis BriefBook
• http://www.jhu.edu/~signals/convolve/index.html （页面存档备份，存于互联网档案馆） Visual convolution Java Applet
• http://www.jhu.edu/~signals/discreteconv2/index.html （页面存档备份，存于互联网档案馆） Visual convolution Java Applet for discrete-time functions
• https://get-the-solution.net/projects/discret-convolution discret-convolution online calculator
• https://lpsa.swarthmore.edu/Convolution/CI.html （页面存档备份，存于互联网档案馆） Convolution demo and visualization in javascript
• https://phiresky.github.io/convolution-demo/ （页面存档备份，存于互联网档案馆） Another convolution demo in javascript
• Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lecture 7 is on 2-D convolution., by Alan Peters
• * https://archive.org/details/Lectures_on_Image_Processing
• Convolution Kernel Mask Operation Interactive tutorial （页面存档备份，存于互联网档案馆）
• Convolution （页面存档备份，存于互联网档案馆） at MathWorld
• Freeverb3 Impulse Response Processor （页面存档备份，存于互联网档案馆）: Opensource zero latency impulse response processor with VST plugins
• Stanford University CS 178 interactive Flash demo （页面存档备份，存于互联网档案馆） showing how spatial convolution works.
• A video lecture on the subject of convolution （页面存档备份，存于互联网档案馆） given by Salman Khan
• Example of FFT convolution for pattern-recognition (image processing) （页面存档备份，存于互联网档案馆）
• Intuitive Guide to Convolution （页面存档备份，存于互联网档案馆） A blogpost about an intuitive interpretation of convolution.