卷積

卷積、互相關和自相關的圖示比較。運算涉及函數$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.