摺積

在泛函分析中，捲積（convolution），或譯為疊積、褶積或旋積，是透過兩個函數$f$和$g$生成第三個函數的一種數學算子，表徵函數$f$與經過翻轉和平移的$g$的乘積函數所圍成的曲邊梯形的面積。如果將參加摺積的一個函數看作區間的指示函數，摺積還可以被看作是「滑動平均」的推廣。

摺積、互相關和自我相關的圖示比較。運算涉及函數$f$，並假定$f$的高度是1.0，在5個不同點上的值，用在每個點下面的陰影面積來指示。$f$的對稱性是摺積$g*f$和互相關$f\star 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.