本页使用了标题或全文手工转换

卷积

维基百科,自由的百科全书
跳转至: 导航搜索
圖示兩個方形脈衝波的捲積。其中函數"g"首先對\tau=0反射,接著平移"t",成為g(t-\tau)。那麼重疊部份的面積就相當於"t"處的捲積,其中橫坐標代表待積變量\tau以及新函數f\ast g的自變量"t"。
圖示方形脈衝波和指數衰退的脈衝波的捲積(後者可能出現於RC電路中),同樣地重疊部份面積就相當於"t"處的捲積。注意到因為"g"是對稱的,所以在這兩張圖中,反射並不會改變它的形狀。

泛函分析中,卷積捲積)、旋積疊積摺積,是通过两个函数fg生成第三个函数的一种数学算子,表徵函数f与经过翻转和平移的g的重叠部分的面積。如果将参加卷积的一个函数看作区间指示函数,卷积还可以被看作是“滑動平均”的推广。

简单介绍[编辑]

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

 \int_{-\infty}^{\infty} f(\tau) g(x - \tau)\, \mathrm{d}\tau

可以证明,关于几乎所有的x \in (-\infty,\infty),上述积分是存在的。这样,随着x的不同取值,这个积分就定义了一个新函数h(x),称为函数fg的卷积,记为h(x)=(f*g)(x)。我們可以輕易验证:(f * g)(x) = (g * f)(x),并且(f * g)(x)仍为可积函数。这就是说,把卷积代替乘法,L^1(R^1)空间是一个代数,甚至是巴拿赫代数

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

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

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

定义[编辑]

函数fg的卷积记作f * g,它是其中一个函数翻转并平移后与另一个函数的乘积的积分,是一个对平移量的函数。

(f * g)(t) = \int f(\tau) g(t - \tau)\, d\tau

积分区间取决于fg定义域

对于定义在离散域的函数,卷积定义为

(f  * g)[m] = \sum_n {f[n] g[m - n]}
圖解摺積
  1. 首先將兩個函數都用\tau來表示。
  2. 對其中一個函數做水平翻轉:g(\tau)g(-\tau).
  3. 加上一個時間偏移量,讓g(t-\tau)能沿著\tau軸滑動。
  4. t從-∞滑動到+∞。兩函數交會時,計算交會範圍中兩函數乘積的積分值。換句話說,我們是在計算一個滑動的的加權平均值。也就是使用g(-\tau).當做加權函數,來對f(\tau)取加權平均值。
最後得到的波形(未包含在此圖中)就是fg的摺積。

如果ft是一個單位脈衝,我們得到的乘積就是gt本身,稱為衝激響應

Convolution3.PNG

計算卷積的方法[编辑]

 f[n] 為有限長度 N  g[n] 為有限長度 M 的信號,計算卷積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快速傅立葉轉換(FFT)[编辑]

  • 概念:由於兩個離散信號在時域(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 \ge M+N-1
  • 由於DFT有快速演算法FFT,所以運算量為 O(P\log_{2}P)
  • 假設 P 點DFT的乘法量為 a  f[n]  g[n] 為一般性的複數信號,並使用複數乘法的快速演算法,則共需要 3a + 3P 個乘法。

方法3分段卷積(sectioned convolution)[编辑]

  • 概念:將 f[n] 切成好幾段,每一段分別和 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 \ge 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小。

應用時機[编辑]

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

以下根據 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 \ge M+N-1 = 2016 ,而2016點的DFT最少乘法數 a = 12728 ,所以總乘法量為 3(a+P) = 44232
方法3:
若切成8塊( S = 8 ),則 L = 250, P \ge 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 \ge L+M-1算出點數在 P 附近的DFT所需最少的乘法量,選擇DFT的點數
(3)最後由L = P+1-M算出 L_{opt}
因此,
(1)由運算量對 L 的偏微分為0而求出 L = 85
(2) P \ge 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 \ge M+N-1 = 1026 ,選擇1026點DFT附近點數乘法量最少的點數, \to P = 1152, a = 7088
因此,所需乘法量為 3(a+P) = 24342
方法3:
(1)由運算量對 L 的偏微分為0而求出 L = 5
(2) P \ge L+M-1 = 7 ,所以選擇7點DFT附近點數乘法量最少的點數P = 8P = 6P = 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 \ge M+N-1 = 1623 ,選擇1026點DFT附近點數乘法量最少的點數, \to P = 2016, a = 12728
因此,所需乘法量為 3(a+P) = 44232
方法3:
(1)由運算量對 L 的偏微分為0而求出 L = 1024
(2) P \ge 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 ,所需總乘法量:快速傅立葉轉換 = 分段卷積<直接計算。故,此時選擇使用分段卷積來計算卷積最適合。

多元函数卷积[编辑]

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

(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 * g = g * f \,
结合律
f  * (g * h) = (f * g) * h \,
分配律
f * (g + h) = (f * g) + (f * h) \,
数乘结合律
a (f * g) = (a f) * g = f * (a g) \,

其中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变换(参见Mellin inversion theorem)等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。

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

在群上的卷积[编辑]

G是有某m 测度(例如豪斯多夫空间哈尔测度局部紧致拓扑群),对于Gm-勒贝格可积实数复数函数fg,可定义它们的卷积:

(f * g)(x) = \int_G f(y)g(xy^{-1})\,dm(y) \,

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

应用[编辑]

卷积在工程和数学上都有很多应用:

  • 统计学中,加权的滑动平均是一种卷积。
  • 概率论中,两个统计独立变量X与Y的和的概率密度函数是X与Y的概率密度函数的卷积。
  • 声学中,回声可以用源声与一个反映各种反射效应的函数的卷积表示。
  • 电子工程与信号处理中,任一个线性系统的输出都可以通过将输入信号与系统函数(系统的冲激响应)做卷积获得。
  • 物理学中,任何一个线性系统(符合叠加原理)都存在卷积。

参见[编辑]

外部链接[编辑]