卷积

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

在泛函分析中，捲積（convolution），或译为疊積、褶積或旋積，是透過两个函数$f$和$g$生成第三个函数的一种数学算子，表徵函数$f$与经过翻转和平移的$g$的乘積函數所圍成的曲邊梯形的面積。如果将参加卷积的一个函数看作区间的指示函数，卷积还可以被看作是“滑動平均”的推廣。卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换，利用此一性質，能簡化傅里叶分析中的许多问题。

定义

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

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

可以证明，关于几乎所有的$t\in (-\infty ,\infty )$，上述积分是存在的。这样，随着$t$的不同取值，这个积分就定义了一个新函数$h(t)$，称为函数$f$与$g$的卷积，记为$h(t)=(f*g)(t)$。$(f*g)(t)$仍为可积函数，并且有着：

$(f*g)(t)=(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}$

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

$(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}$

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

$f(t)*g(t)\mathrel {:=} \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})$。

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

$(f\star g)(t)={\overline {f(-t)}}*g(t)$

简介

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

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

如果$f$和$g$都是在L^p空间$L^{1}(\mathbb {R} ^{d})$内的勒贝格可积函数，则二者的卷积存在，并且在这种情况下$f*g$也是可积的。这是Tonelli定理的结论。对于在$L^{1}$中的函数在离散卷积下，或更一般的对于在任何群的上的卷积，这也是成立的。

同样的，如果$f\in L^{1}(\mathbb {R} ^{d})$而$g\in L^{p}(\mathbb {R} ^{d})$，这里的$1\leq p\leq \infty$，则$f*g\in L^{p}(\mathbb {R} ^{d})$，并且其L^p范数间有着不等式：

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

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

对于單位脈衝函数$\delta (t)$和某个函数$h(t)$，二者得到的捲積就是$h(t)$本身，此$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)\mathrel {\stackrel {\mathrm {def} }{=}} \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$

图解

已知右侧第一行图中两个函数$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$是對稱的，所以在這兩張圖中，反射並不會改變它的形狀。

性质

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

交换律

$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$为任意实数（或复数）。

微分定理

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

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

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

卷积定理

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

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

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

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

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

推广

卷积的概念还可以推广到数列、测度以及广义函数上去。函数 $f,g$ 是定義在 $\mathbb {R} ^{n}$ 上的可測函數（measurable function），$f$与$g$的卷积记作$f*g$，它是其中一个函数反轉（reverse），並平移后，与另一个函数的乘积的积分，是一个对平移量的函数，也就是：

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

如果函數不是定義在 $\mathbb {R} ^{n}$ 上，可以把函數定義域以外的值都規定成零，這樣就變成一個定義在 $\mathbb {R} ^{n}$ 上的函數。

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

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

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

圆周卷积

主条目：圆周卷积

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

$h_{_{T}}(t)\triangleq \sum _{n=-\infty }^{\infty }h(t-nT)=\sum _{n=-\infty }^{\infty }h(t+nT)$

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

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

这里的$t_{0}$是任意参数。周期卷积也可以通过将$h_{_{T}}(t)$和$x_{_{T}}(t)$，表达为无周期的函数$h$和$x$的周期总和，而用无周期的常规卷积来定义：

$\int _{t_{0}}^{t_{0}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau =\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau \ \triangleq \ (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 )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau$

离散卷积

离散二维卷积的动画

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

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

$(f*g)[n]\ \ {\stackrel {\mathrm {def} }{=}}\ \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})=x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(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]\cdot \underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}$

这个函数有周期$N$，它有最多$N$个唯一性的值。对于$h$和$x$的非零范围都是$[0,N-1]$的特殊情况，它可精简为矩阵乘法，这里的积分变换的核函数是循环矩阵。

离散卷積的計算方法

計算卷積$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.