查看“卷积”的源代码

{{noteTA
|G1=Signals and Systems
|G2=Math
}}
[[File:Convolution of box signal with itself2.gif|thumb|350px|图示两个方形脈衝波的捲積。其中函数"g"首先对<math>\tau=0</math>反射，接著平移"t"，成為<math>g(t-\tau)</math>。那么重叠部份的面积就相当于"t"处的卷积，其中橫坐標代表待变量<math>\tau</math>以及新函數<math>f\ast g</math>的自變量"t"。]]

[[File:Convolution of spiky function with box2.gif|thumb|350px|圖示方形脈衝波和指數衰退的脈衝波的捲積（後者可能出現於[[RC電路]]中），同樣地重疊部份面積就相當於"t"處的捲積。注意到因為"g"是對稱的，所以在這兩張圖中，反射並不會改變它的形狀。]]

在[[泛函分析]]中，'''捲積'''（又称'''疊積'''（convolution）、'''-{褶}-積'''或'''旋積'''），是通过两个[[函数]]''f''和''g''生成第三个函数的一种数学[[算子]]，表徵函数''f''与经过翻转和平移的''g''的乘積函數所圍成的曲邊梯形的面積。如果将参加卷积的一个函数看作[[区间]]的[[指示函数]]，卷积还可以被看作是“[[滑動平均]]”的推广。

== 简单介绍 ==
卷积是[[数学分析]]中一种重要的运算。设：<math> f(x)</math>、<math>g(x)</math>是<math>\mathbb{R}</math>上的两个[[可积函数]]，作[[积分]]：
:<math> \int_{-\infty}^{\infty} f(\tau) g(x - \tau)\, \mathrm{d}\tau</math>
可以证明，关于几乎所有的<math>x \in (-\infty,\infty)</math>，上述积分是[[存在]]的。这样，随着<math>x</math>的不同取值，这个积分就定义了一个新函数<math>h(x)</math>，称为函数<math>f</math>与<math>g</math>的卷积，记为<math>h(x)=(f*g)(x)</math>。我們可以輕易验证：<math>(f * g)(x) = (g * f)(x)</math>，并且<math>(f * g)(x)</math>仍为可积函数。这就是说，把卷积代替乘法，<math>L^1(R^1)</math>空间是一个代数，甚至是[[巴拿赫代数]]。雖然這裡為了方便我們假設 <math>\textstyle f, g\in L^1(\mathbb{R})</math>，不過捲積只是運算符號，理論上並不需要對函數 <math>f,g</math> 有特別的限制，雖然常常要求 <math>f,g</math> 至少是可測函數（measurable function）（如果不是可測函數的話，積分可能根本沒有意義），至於生成的卷積函數性質會在運算之後討論。

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

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

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

== 定义 ==
[[函数]] <math>f,g</math> 是定義在 <math>\mathbb{R}^n</math> 上的[[可測函數]]（measurable function），<math>f</math>与<math>g</math>的卷积记作<math>f * g</math>，它是其中一个函数[[翻转]]并[[平移]]后与另一个函数的乘积的积分，是一个对平移量的函数，也就是：
: <math>(f * g)(t)\ \ \,\stackrel{\mathrm{def}}{=}\ \int_{\mathbb{R}^n} f(\tau) g(t - \tau)\, d\tau</math>。

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

{| class="wikitable"
|-
!colspan=2 |'''圖解摺積'''<br />
|-
|
# 已知两函数f(t)和g(t)。右图第一行两图分别为f(t)和g(t)。
# 首先將兩個函數都用<math>\tau</math>來表示，从而得到f(<math>\tau</math>)和g(<math>\tau</math>)。将函数g(<math>\tau</math>)向右移动t个单位，得到函数g(<math>\tau</math>-t)的图像。将g(<math>\tau</math>-t)翻转至纵轴另一侧，得到g(-(<math>\tau</math>-t))即g(t-<math>\tau</math>)的图像。右图第二行两图分别为f(<math>\tau</math>)和g(t-<math>\tau</math>)。
# 由于t非[[常数]]（实际上是[[时间]][[变量]]），当时间变量（以下简称“时移”）取不同值时，<math>g(t-\tau)</math>能沿着<math>\tau</math>轴“滑动”。右图第三四五行可理解为“滑动”。
# 讓''<math>\tau</math>''從-∞滑動到+∞。兩函數交會時，計算交會範圍中兩函數乘積的積分值。換句話說，我們是在計算一個<u>滑動的</u>的加權總和(weighted-sum)。也就是使用<math>g(t-\tau)</math>當做[[加權函數]]，來對<math>f(\tau)</math>取加權值。
:最後得到的波形（未包含在此圖中）就是''f''和''g''的摺積。如果'''''f''（''t''）'''是一個[[狄拉克δ函數|單位脈衝]]，我們得到的乘積就是'''''g''（''t''）'''本身，稱為[[衝激響應]]。
|[[File:Convolution3.PNG|right|350px]]
|}

== 离散卷积 ==
对于定义在整數 <math>\mathbb{Z}</math> 上的函数 <math>f, g</math>，卷积定义为
:<math>(f  * g)[n]\ \ \stackrel{\mathrm{def}}{=}\ \sum_{m=-\infty}^{\infty} {f[m] g[n-m]} </math>
::::<math>= \sum_{m=-\infty}^\infty f[n-m]\, g[m].</math>
這裡一樣把函數定義域以外的值當成零，所以可以擴展函數到所有整數上（如果本來不是的話）。

當<math> g[n] </math> 的支撐集（support）為有限長度<math>M </math>，上式會變成有限和：
:<math>(f*g)[n]=\sum_{m=-M}^M f[n-m]g[m].</math>

===計算离散卷積的方法 ===
計算卷積<math>f[n]*g[n]</math>有三種主要的方法，分別為
#直接計算（Direct Method）
#[[快速傅立葉轉換]]（FFT）
#分段卷積（sectioned convolution）
方法1是直接利用定義來計算卷積，而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法，如使用[[數論轉換]]。

====方法1：直接計算====

*作法：利用卷積的定義

:: <math> y[n] = f[n]*g[n] = \sum_{m=0}^{M-1} f[n-m]g[m] </math>

*若<math> f[n] </math>和<math> g[n] </math>皆為實數信號，則需要<math> MN </math>個乘法。

*若<math> f[n] </math>和<math> g[n] </math>皆為更一般性的複數信號，不使用複數乘法的快速演算法，會需要<math> 4MN </math>個乘法;但若使用複數乘法的快速演算法，則可簡化至<math> 3MN </math>個乘法。

:因此，使用定義直接計算卷積的複雜度為<math> O(MN) </math>。

====方法2：快速傅立葉轉換（FFT）====

*概念：由於兩個離散信號在時域（time domain）做卷積相當於這兩個信號的離散傅立葉轉換在頻域（frequency domain）做相乘：

::<math> y[n] = f[n]*g[n] \leftrightarrow Y[f] = F[f]G[f] </math>

:，可以看出在頻域的計算較簡單。

*作法：因此這個方法即是先將信號從時域轉成頻域：

::<math> F[f] = DFT_P(f[n]), G[f] = DFT_P(g[n])  </math> 

:，於是

::<math> Y[f] = DFT_P(f[n])DFT_P(g[n])  </math> 

:，最後再將頻域信號轉回時域，就完成了卷積的計算：

::<math> y[n] = IDFT_P{DFT_P(f[n])DFT_P(g[n])}  </math> 

:總共做了2次DFT和1次IDFT。

*特別注意DFT和IDFT的點數<math>P</math>要滿足<math> P \ge M+N-1 </math>。

*由於DFT有快速演算法FFT，所以運算量為<math> O(P\log_{2}P) </math>

*假設<math> P </math>點DFT的乘法量為<math> a </math>，<math> f[n] </math>和<math> g[n] </math>為一般性的複數信號，並使用複數乘法的快速演算法，則共需要<math> 3a + 3P </math>個乘法。

====方法3：分段卷積（sectioned convolution）====

*概念：將<math> f[n] </math>切成好幾段，每一段分別和<math> g[n] </math>做卷積後，再將結果相加。

*作法：先將<math> f[n] </math>切成每段長度為<math> L </math>的區段（<math> L > M </math>），假設共切成S段：

::<math> 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)</math>

::Section 1: <math> f_1[n] = f[n]  , n=0,1,...,L-1</math>

::Section 2: <math> f_2[n] = f[n+L], n=0,1,...,L-1</math>

:::<math> \vdots </math> 

::Section r: <math> f_r[n] = f[n+(r-1)L], n=0,1,...,L-1 </math> 

:::<math> \vdots </math> 

::Section S: <math> f_S[n] = f[n+(S-1)L], n=0,1,...,L-1</math>

:，<math> f[n] </math>為各個section的和

::<math> f[n] =  \sum_{r=1}^{S} f_r[n+(r-1)L] </math>。

:因此，

::<math> y[n] = f[n]*g[n] =  \sum_{r=1}^{S} \sum_{m=0}^{M-1} f_r[n+(r-1)L-m]g[m] </math>，

:每一小段作卷積則是採用方法2，先將時域信號轉到頻域相乘，再轉回時域：

::<math> 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 \ge M+L-1 </math>。

*總共只需要做<math> P </math>點FFT <math>2S+1</math>次，因為<math> g[n] </math>只需要做一次FFT。

*假設<math> P </math>點DFT的乘法量為<math> a </math>，<math> f[n] </math>和<math> g[n] </math>為一般性的複數信號，並使用複數乘法的快速演算法，則共需要<math>(2S+1)a+3SP </math>個乘法。

*運算量：<math> \frac{N}{L}3(L+M-1)[\log_{2}(L+M-1)+1] </math>

*運算複雜度：<math> O(N)</math>，和<math> N </math>呈線性，較方法2小。
*分為 Overlap-Add 和 Overlap-Save 兩種方法。
'''分段卷積: Overlap-Add'''

欲做<math> x[n]*h[n] </math>的分段卷積分，<math> x[n] </math> 長度為 <math> N
 </math>，<math> h[n] </math> 長度為 <math> M
 </math>,

Step 1: 將<math> x[n] </math>每 <math> L </math> 分成一段

Step 2: 再每段 <math> L </math> 點後面添加 <math> M-1 </math> 個零，變成長度 <math> L+M-1 </math>

Step 3: 把 <math> h[n] </math> 添加 <math> L-1 </math>個零，變成長度 <math> L+M-1 </math>的 <math> h'[n] </math>

Step 4: 把每個 <math> x[n] </math> 的小段和 <math> h'[n] </math> 做快速卷積，也就是<math> IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])} \} </math>，每小段會得到長度 <math> L+M-1 </math> 的時域訊號

Step 5: 放置第 <math> i </math> 個小段的起點在位置 <math> L\times i </math> 上, <math> i=0, 1, ...,\lceil \frac{N}{L}  \rceil-1 </math>

Step 6: 會發現在每一段的後面 <math> M-1 </math> 點有重疊，將所有點都相加起來，顧名思義 Overlap-Add，最後得到結果

舉例來說:

<math> x[n]=[1, 2, 3, 4, 5, -1, -2, -3, -4, -5, 1, 2, 3, 4, 5] </math>, 長度 <math> N=15 </math>

<math> h[n]=[1, 2, 3] </math>, 長度 <math> M=3 </math>

令 <math> L=5 </math> <gallery mode="nolines" widths="300" heights="300">
File:Data overlap add.png|x[n]和h[n]
</gallery>

令 <math> L=5 </math> 切成三段，分別為 <math> x_0[n], x_1[n], x_2[n] </math>, 每段填 <math> M-1 </math> 個零，並將 <math> h[n] </math> 填零至長度 <math> L+M-1 </math><gallery mode="nolines" widths="300" heights="300">
File:Seperate x overlap add.png|分段x[n]
</gallery>將每一段做<math> IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])} \} </math><gallery mode="nolines" widths="300" heights="300">
File:Seperate result overlap add.png|分段運算結果
</gallery>若將每小段擺在一起，可以注意到第一段的範圍是 <math> 0\thicksim6 </math> ，第二段的範圍是 <math> 5\thicksim 11 </math>，第三段的範圍是 <math> 10\thicksim 16 </math>，三段的範圍是有重疊的<gallery mode="nolines" widths="300" heights="300">
File:Summation overlap add.png|合併分段運算結果
</gallery>最後將三小段加在一起，並將結果和未分段的卷積做比較，上圖是分段的結果，下圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。<gallery mode="nolines" widths="300" heights="300">
File:Final result overlap add.png|結果比較圖
</gallery>'''分段卷積: Overlap-Save'''

欲做<math> x[n]*h[n] </math>的分段卷積分，<math> x[n] </math> 長度為 <math> N
 </math>，<math> h[n] </math> 長度為 <math> M
 </math>,

Step 1: 將 <math> x[n] </math> 前面填 <math> M-1 </math> 個零

Step 2: 第一段 <math> i=0 </math>, 從新的 <math> x[n] </math> 中 <math> L\times i- (M-1)\times i </math> 取到 <math> L\times (i+1)- (M-1)\times i -1 </math> 總共 <math> L </math> 點當做一段，因此每小段會重複取到前一小段的 <math> M-1 </math> 點，取到新的一段全為零為止

Step 3: 把 <math> h[n] </math> 添加 <math> L-M </math> 個零，變成長度 <math> L </math> 的 <math> h'[n] </math>

Step 4: 把每個 <math> x[n] </math> 的小段和 <math> h'[n] </math> 做快速卷積，也就是<math> IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])} \} </math>，每小段會得到長度 <math> L </math> 的時域訊號

Step 5: 對於每個 <math> i </math> 小段，只會保留末端的 <math> L-(M-1) </math> 點，因此得名 Overlap-Save

Step 6: 將所有保留的點合再一起，得到最後結果

舉例來說:

<math> x[n]=[1, 2, 3, 4, 5, 6,7, 8, 9, 10, 11, 12, 13, 14, 15] </math>, 長度 <math> N=15 </math>

<math> h[n]=[1, 2, 3] </math>, 長度 <math> M=3 </math>

令 <math> L=7 </math> <gallery mode="nolines" widths="300" heights="300">
File:Data overlap save.png|x[n]和h[n]
</gallery>將 <math> x[n] </math> 前面填 <math> M-1 </math> 個零以後，按照 Step 2 的方式分段，可以看到每一段都重複上一段的 <math> M-1 </math> 點<gallery mode="nolines" widths="300" heights="300">
File:Seperate x overlap save.png|分段x[n]
</gallery>再將每一段做 <math> IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])} \} </math>以後可以得到<gallery mode="nolines" widths="300" heights="300">
File:Seperate result overlap save.png|分段運算結果
</gallery>保留每一段末端的 <math> L-(M-1) </math> 點，擺在一起以後，可以注意到第一段的範圍是 <math> 0\thicksim 4 </math> ，第二段的範圍是 <math> 5\thicksim 9 </math>，第三段的範圍是 <math> 10\thicksim 14 </math>，第四段的範圍是 <math> 15\thicksim 16 </math>，四段的範圍是沒有重疊的<gallery mode="nolines" widths="300" heights="300">
File:Summation overlap save.png|合併分段運算結果
</gallery>將結果和未分段的卷積做比較，下圖是分段的結果，上圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。<gallery mode="nolines" widths="300" heights="300">
File:Final compare overlap save.png|結果比較圖
</gallery>至於為什麼要把前面 <math> M-1 </math> 丟掉?

以下以一例子來闡述:

<math> x[n]=[1, 2, 3, 4, 5, 6,7, 8, 9, 10] </math>, 長度 <math> L=10 </math>，

<math> h[n]=[1, 2, 3, 4, 5] </math>, 長度 <math> M=5 </math>,

第一條藍線代表 <math> y </math> 軸，而兩條藍線之間代表長度 <math> L </math>，是在做快速摺積時的週期<gallery mode="nolines" widths="300" heights="300">
File:Original ov extra.png|x[n]和h[n]
</gallery>當在做快速摺積時<math> IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])} \} </math>，是把訊號視為週期 <math> L </math>，在時域上為循環摺積分,

而在一開始前 <math> M-1 </math> 點所得到的值，是 <math> h[0], h[6], h[7], h[8], h[9] </math> 和 <math> x[0], x[6], x[7], x[8], x[9] </math> 內積的值，

然而 <math> h[6], h[7], h[8], h[9] </math> 這 <math> M-1 </math> 個值應該要為零，以往在做快速摺積時長度為 <math> L+M-1 </math> 時不會遇到這些問題，

而今天因為在做快速摺積時長度為 <math> L </math> 才會把這 <math> M-1 </math> 點算進來，因此我們要丟棄這 <math> M-1 </math> 點內積的結果<gallery mode="nolines" widths="300" heights="300">
File:Cir conv ov extra.png|循環摺積
</gallery>為了要丟棄這 <math> M-1 </math> 點內積的結果，位移 <math> h[-n] </math> <math> M-1 </math> 點，並把位移以後內積合的值才算有效。<gallery mode="nolines" widths="300" heights="300">
File:Cir conv shift ov extra.png|位移以後內積
</gallery>

==== 應用時機 ====

以上三種方法皆可用來計算卷積，其差別在於所需總體乘法量不同。基於運算量以及效率的考量，在計算卷積時，通常會選擇所需總體乘法量較少的方法。

以下根據<math> f[n] </math>和<math> g[n] </math>的長度（<math> N, M </math>）分成5類，並列出適合使用的方法：

# <math> M </math>為一非常小的整數 - 直接計算
# <math> M \ll N </math> - 分段卷积
# <math> M \approx N </math> - 快速傅里叶变换
# <math> M \gg N </math> - 分段卷积
# <math> N </math>為一非常小的整數 - 直接計算

基本上，以上只是粗略的分類。在實際應用時，最好還是算出三種方法所需的總乘法量，再選擇其中最有效率的方法來計算卷積。

===== 例子 =====

Q1：當<math> N = 2000, M = 17 </math>，適合用哪種方法計算卷積?

Ans：

:方法1：所需乘法量為<math> 3MN = 102000 </math> 

:方法2：<math> P \ge M+N-1 = 2016 </math>，而2016點的DFT最少乘法數<math> a = 12728 </math>，所以總乘法量為<math> 3(a+P) = 44232 </math> 

:方法3： 
::若切成8塊（<math> S = 8 </math>），則<math> L = 250, P \ge M+L-1=266 </math>。選<math> P = 288 </math>，則總乘法量為<math>(2S+1)a+3SP = 26632 </math>，比方法1和2少了很多。
::但是若要找到最少的乘法量，必須依照以下步驟
:::(1)先找出<math> L </math>:解<math> L</math> : <math> \frac{\partial {\frac{N}{L}3(L+M-1)[\log_{2}(L+M-1)+1]}}{\partial L}=0 </math>
:::(2)由<math>P \ge L+M-1</math>算出點數在<math> P </math>附近的DFT所需最少的乘法量，選擇DFT的點數
:::(3)最後由<math>L = P+1-M</math>算出<math> L_{opt} </math>
::因此，
:::(1)由運算量對<math> L </math>的偏微分為0而求出<math> L = 85 </math>
:::(2)<math> P \ge L+M-1 = 101 </math>，所以選擇101點DFT附近點數乘法量最少的點數<math>P = 96 </math>或<math>P = 120</math>。
:::(3-1)當<math> P = 96 \to a = 280, L = P+1-M = 80 \to S = 25</math>，總乘法量為<math>(2S+1)a+3SP = 21480 </math>。
:::(3-2)當<math> P = 120 \to a = 380, L = P+1-M = 104 \to S = 20</math>，總乘法量為<math>(2S+1)a+3SP = 22780 </math>。
::由此可知，切成20塊會有較好的效率，而所需總乘法量為21480。
*因此，當<math> N = 2000, M = 17 </math>，所需總乘法量：分段卷積<快速傅立葉轉換<直接計算。故，此時選擇使用分段卷積來計算卷積最適合。
  
Q2：當<math> N = 1024, M = 3 </math>，適合用哪種方法計算卷積?

Ans：

:方法1：所需乘法量為<math> 3MN = 9216 </math> 
  
:方法2：<math> P \ge M+N-1 = 1026 </math>，選擇1026點DFT附近點數乘法量最少的點數，<math> \to P = 1152, a = 7088 </math>。
:::因此，所需乘法量為<math> 3(a+P) = 24342 </math> 

:方法3： 
:::(1)由運算量對<math> L </math>的偏微分為0而求出<math> L = 5 </math>
:::(2)<math> P \ge L+M-1 = 7 </math>，所以選擇7點DFT附近點數乘法量最少的點數<math>P = 8</math>或<math>P = 6</math>或<math>P = 4</math>。
:::(3-1)當<math> P = 8 \to a = 4, L = P+1-M = 6 \to S = 171</math>，總乘法量為<math>(2S+1)a+3SP = 5476 </math>。
:::(3-2)當<math> P = 6 \to a = 4, L = P+1-M = 4 \to S = 256</math>，總乘法量為<math>(2S+1)a+3SP = 6660 </math>。
:::(3-3)當<math> P = 4 \to a = 0, L = P+1-M = 2 \to S = 512</math>，總乘法量為<math>(2S+1)a+3SP = 6144 </math>。
::由此可知，切成171塊會有較好的效率，而所需總乘法量為5476。
*因此，當<math> N = 1024, M = 3 </math>，所需總乘法量：分段卷積<直接計算<快速傅立葉轉換。故，此時選擇使用分段卷積來計算卷積最適合。
*雖然當<math>M </math>是個很小的正整數時，大致上適合使用直接計算。但實際上還是將3個方法所需的乘法量都算出來，才能知道用哪種方法可以達到最高的效率。

Q3：當<math> N = 1024, M = 600 </math>，適合用哪種方法計算卷積?

Ans：

:方法1：所需乘法量為<math> 3MN = 1843200 </math> 
  
:方法2：<math> P \ge M+N-1 = 1623 </math>，選擇1026點DFT附近點數乘法量最少的點數，<math> \to P = 2016, a = 12728 </math>。
:::因此，所需乘法量為<math> 3(a+P) = 44232 </math> 

:方法3： 
:::(1)由運算量對<math> L </math>的偏微分為0而求出<math> L = 1024 </math>
:::(2)<math> P \ge L+M-1 = 1623 </math>，所以選擇1623點DFT附近點數乘法量最少的點數<math>P = 2016</math>。
:::(3)當<math> P = 2016 \to a = 12728, L = P+1-M = 1417 \to S = 1</math>，總乘法量為<math>(2S+1)a+3SP = 44232 </math>。
::由此可知，此時切成一段，就跟方法2一樣，所需總乘法量為44232。
*因此，當<math> N = 1024, M = 600 </math>，所需總乘法量：快速傅立葉轉換 = 分段卷積<直接計算。故，此時選擇使用分段卷積來計算卷積最適合。

== 多元函数卷积 ==
按照翻转、平移、积分的定义，还可以类似的定义多元函数上的积分：
: <math>(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</math>

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

;[[交换律]]
: <math>f * g = g * f \,</math>

;[[结合律]]
: <math>f  * (g * h) = (f * g) * h \,</math>

;[[分配律]]
: <math>f * (g + h) = (f * g) + (f * h) \,</math>

;[[数乘结合律]]
: <math>a (f * g) = (a f) * g = f * (a g) \,</math>
其中<math>a</math>为任意[[实数]]（或[[复数]]）。

;[[微分定理]]
: <math>\mathcal{D}(f * g) = \mathcal{D}f * g = f * \mathcal{D}g \,</math>

其中D''f''表示''f''的[[微分]]，如果在离散域中则是指[[差分]]算子，包括前向差分与后向差分两种：
* 前向差分：<math>\mathcal{D}^+f(n) = f(n+1) - f(n)</math>
* 后向差分：<math>\mathcal{D}^-f(n) = f(n) - f(n-1)</math>

== 卷积定理 ==

'''[[卷积定理]]'''指出，函数卷积的[[傅里叶变换]]是函数傅里叶变换的乘积。即，一个域中的卷积相当于另一个域中的乘积，例如[[时域]]中的卷积就对应于[[频域]]中的乘积。
: <math> \mathcal{F}(f * g) =  \mathcal{F} (f) \cdot \mathcal{F} (g)   </math>
其中<math>\mathcal{F}(f)</math>表示''f''的[[傅里叶变换]]。

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

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

== 在群上的卷积 ==

若''G''是有某''m'' [[测度]]的[[群]]（例如[[豪斯多夫空间]]上[[哈尔测度]]下[[局部紧致]]的[[拓扑群]]），对于''G''上''m''-[[勒贝格可积]]的[[实数]]或[[复数]]函数''f''和''g''，可定义它们的卷积：
:<math>(f * g)(x) = \int_G f(y)g(xy^{-1})\,dm(y) \,</math>

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

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

== 参见 ==
* [[互相关|反卷积]]
* [[自相关函数]]
* [[傅里叶变换]]

== 外部链接 ==
* {{planetmath reference|title=Convolution|id=2790|}}
* [http://www.jhu.edu/~signals/convolve/index.html Visual convolution Java Applet]
* Lecture notes, Jian-Jiun Ding (2013), [http://djj.ee.ntu.edu.tw/ADSP.htm Advanced Digital Signal Processing] 

[[Category:泛函分析|J]]
[[Category:信号处理|J]]
[[Category:二元運算|J]]
[[Category:双线性算子]]
[[Category:特征检测_(计算机视觉)]]