卷积
在泛函分析中,捲積(又称疊積(convolution)、積或旋積),是透過两个函数 f 和 g 生成第三个函数的一种数学算子,表徵函数 f 与经过翻转和平移的 g 的乘積函數所圍成的曲邊梯形的面積。如果将参加卷积的一个函数看作区间的指示函数,卷积还可以被看作是“滑動平均”的推廣。
简单介绍
卷积是数学分析中一种重要的运算。设:、是上的两个可积函数,作积分:
可以证明,关于几乎所有的,上述积分是存在的。这样,随着的不同取值,这个积分就定义了一个新函数,称为函数与的卷积,记为。我們可以輕易验证:,并且仍为可积函数。这就是说,把卷积代替乘法,空间是一个代数,甚至是巴拿赫代数。雖然這裡為了方便我們假設 ,不過捲積只是運算符號,理論上並不需要對函數 有特別的限制,雖然常常要求 至少是可測函數(measurable function)(如果不是可測函數的話,積分可能根本沒有意義),至於生成的卷積函數性質會在運算之後討論。
卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换,利用此一性質,能簡化傅里叶分析中的许多问题。
由卷积得到的函数一般要比和都光滑。特别当为具有紧支集的光滑函数,为局部可积时,它们的卷积也是光滑函数。利用这一性质,对于任意的可积函数,都可以简单地构造出一列逼近于的光滑函数列,这种方法称为函数的光滑化或正则化。
定义
函数 是定義在 上的可測函數(measurable function),与的卷积记作,它是其中一个函数翻转,並平移后,与另一个函数的乘积的积分,是一个对平移量的函数,也就是:
- 。
如果函數不是定義在 上,可以把函數定義域以外的值都規定成零,這樣就變成一個定義在 上的函數。
圖解摺積 | |
---|---|
|
离散卷积
对于定义在整數 上的函数 ,卷积定义为
這裡一樣把函數定義域以外的值當成零,所以可以擴展函數到所有整數上(如果本來不是的話)。
當 的支撐集(support)為有限長度,上式會變成有限和:
計算离散卷積的方法
計算卷積有三種主要的方法,分別為
- 直接計算(Direct Method)
- 快速傅立葉轉換(FFT)
- 分段卷積(sectioned convolution)
方法1是直接利用定義來計算卷積,而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法,如使用數論轉換。
方法1:直接計算
- 作法:利用卷積的定義
- 若和皆為實數信號,則需要個乘法。
- 若和皆為更一般性的複數信號,不使用複數乘法的快速演算法,會需要個乘法;但若使用複數乘法的快速演算法,則可簡化至個乘法。
- 因此,使用定義直接計算卷積的複雜度為。
方法2:快速傅立葉轉換(FFT)
- 概念:由於兩個離散信號在時域(time domain)做卷積相當於這兩個信號的離散傅立葉轉換在頻域(frequency domain)做相乘:
- ,可以看出在頻域的計算較簡單。
- 作法:因此這個方法即是先將信號從時域轉成頻域:
- ,於是
- ,最後再將頻域信號轉回時域,就完成了卷積的計算:
- 總共做了2次DFT和1次IDFT。
- 特別注意DFT和IDFT的點數要滿足。
- 由於DFT有快速演算法FFT,所以運算量為
- 假設點DFT的乘法量為,和為一般性的複數信號,並使用複數乘法的快速演算法,則共需要個乘法。
方法3:分段卷積(sectioned convolution)
- 概念:將切成好幾段,每一段分別和做卷積後,再將結果相加。
- 作法:先將切成每段長度為的區段(),假設共切成S段:
- Section 1:
- Section 2:
- Section r:
- Section S:
- ,為各個section的和
- 。
- 因此,
- ,
- 每一小段作卷積則是採用方法2,先將時域信號轉到頻域相乘,再轉回時域:
- 。
- 總共只需要做點FFT 次,因為只需要做一次FFT。
- 假設點DFT的乘法量為,和為一般性的複數信號,並使用複數乘法的快速演算法,則共需要個乘法。
- 運算量:
- 運算複雜度:,和呈線性,較方法2小。
- 分為 Overlap-Add 和 Overlap-Save 兩種方法。
分段卷積: Overlap-Add
欲做的分段卷積分, 長度為 , 長度為 ,
Step 1: 將每 分成一段
Step 2: 再每段 點後面添加 個零,變成長度
Step 3: 把 添加 個零,變成長度 的
Step 4: 把每個 的小段和 做快速卷積,也就是,每小段會得到長度 的時域訊號
Step 5: 放置第 個小段的起點在位置 上,
Step 6: 會發現在每一段的後面 點有重疊,將所有點都相加起來,顧名思義 Overlap-Add,最後得到結果
舉例來說:
, 長度
, 長度
令
- x[n]和h[n]
令 切成三段,分別為 , 每段填 個零,並將 填零至長度
- 分段x[n]
將每一段做
- 分段運算結果
若將每小段擺在一起,可以注意到第一段的範圍是 ,第二段的範圍是 ,第三段的範圍是 ,三段的範圍是有重疊的
- 合併分段運算結果
最後將三小段加在一起,並將結果和未分段的卷積做比較,上圖是分段的結果,下圖是沒有分段並利用快速卷積所算出的結果,驗證兩者運算結果相同。
- 結果比較圖
分段卷積: Overlap-Save
欲做的分段卷積分, 長度為 , 長度為 ,
Step 1: 將 前面填 個零
Step 2: 第一段 , 從新的 中 取到 總共 點當做一段,因此每小段會重複取到前一小段的 點,取到新的一段全為零為止
Step 3: 把 添加 個零,變成長度 的
Step 4: 把每個 的小段和 做快速卷積,也就是,每小段會得到長度 的時域訊號
Step 5: 對於每個 小段,只會保留末端的 點,因此得名 Overlap-Save
Step 6: 將所有保留的點合再一起,得到最後結果
舉例來說:
, 長度
, 長度
令
- x[n]和h[n]
將 前面填 個零以後,按照 Step 2 的方式分段,可以看到每一段都重複上一段的 點
- 分段x[n]
再將每一段做 以後可以得到
- 分段運算結果
保留每一段末端的 點,擺在一起以後,可以注意到第一段的範圍是 ,第二段的範圍是 ,第三段的範圍是 ,第四段的範圍是 ,四段的範圍是沒有重疊的
- 合併分段運算結果
將結果和未分段的卷積做比較,下圖是分段的結果,上圖是沒有分段並利用快速卷積所算出的結果,驗證兩者運算結果相同。
- 結果比較圖
至於為什麼要把前面 丟掉?
以下以一例子來闡述:
, 長度 ,
, 長度 ,
第一條藍線代表 軸,而兩條藍線之間代表長度 ,是在做快速摺積時的週期
- x[n]和h[n]
當在做快速摺積時,是把訊號視為週期 ,在時域上為循環摺積分,
而在一開始前 點所得到的值,是 和 內積的值,
然而 這 個值應該要為零,以往在做快速摺積時長度為 時不會遇到這些問題,
而今天因為在做快速摺積時長度為 才會把這 點算進來,因此我們要丟棄這 點內積的結果
- 循環摺積
為了要丟棄這 點內積的結果,位移 點,並把位移以後內積合的值才算有效。
- 位移以後內積
應用時機
以上三種方法皆可用來計算卷積,其差別在於所需總體乘法量不同。基於運算量以及效率的考量,在計算卷積時,通常會選擇所需總體乘法量較少的方法。
以下根據和的長度()分成5類,並列出適合使用的方法:
- 為一非常小的整數 - 直接計算
- - 分段卷积
- - 快速傅里叶变换
- - 分段卷积
- 為一非常小的整數 - 直接計算
基本上,以上只是粗略的分類。在實際應用時,最好還是算出三種方法所需的總乘法量,再選擇其中最有效率的方法來計算卷積。
例子
Q1:當,適合用哪種方法計算卷積?
Ans:
- 方法1:所需乘法量為
- 方法2:,而2016點的DFT最少乘法數,所以總乘法量為
- 方法3:
- 若切成8塊(),則。選,則總乘法量為,比方法1和2少了很多。
- 但是若要找到最少的乘法量,必須依照以下步驟
- (1)先找出:解 :
- (2)由算出點數在附近的DFT所需最少的乘法量,選擇DFT的點數
- (3)最後由算出
- 因此,
- (1)由運算量對的偏微分為0而求出
- (2),所以選擇101點DFT附近點數乘法量最少的點數或。
- (3-1)當,總乘法量為。
- (3-2)當,總乘法量為。
- 由此可知,切成20塊會有較好的效率,而所需總乘法量為21480。
- 因此,當,所需總乘法量:分段卷積<快速傅立葉轉換<直接計算。故,此時選擇使用分段卷積來計算卷積最適合。
Q2:當,適合用哪種方法計算卷積?
Ans:
- 方法1:所需乘法量為
- 方法2:,選擇1026點DFT附近點數乘法量最少的點數,。
- 因此,所需乘法量為
- 方法3:
- (1)由運算量對的偏微分為0而求出
- (2),所以選擇7點DFT附近點數乘法量最少的點數或或。
- (3-1)當,總乘法量為。
- (3-2)當,總乘法量為。
- (3-3)當,總乘法量為。
- 由此可知,切成171塊會有較好的效率,而所需總乘法量為5476。
- 因此,當,所需總乘法量:分段卷積<直接計算<快速傅立葉轉換。故,此時選擇使用分段卷積來計算卷積最適合。
- 雖然當是個很小的正整數時,大致上適合使用直接計算。但實際上還是將3個方法所需的乘法量都算出來,才能知道用哪種方法可以達到最高的效率。
Q3:當,適合用哪種方法計算卷積?
Ans:
- 方法1:所需乘法量為
- 方法2:,選擇1026點DFT附近點數乘法量最少的點數,。
- 因此,所需乘法量為
- 方法3:
- (1)由運算量對的偏微分為0而求出
- (2),所以選擇1623點DFT附近點數乘法量最少的點數。
- (3)當,總乘法量為。
- 由此可知,此時切成一段,就跟方法2一樣,所需總乘法量為44232。
- 因此,當,所需總乘法量:快速傅立葉轉換 = 分段卷積<直接計算。故,此時選擇使用分段卷積來計算卷積最適合。
多元函数卷积
按照翻转、平移、积分的定义,还可以类似的定义多元函数上的积分:
卷积定理
卷积定理指出,函数卷积的傅里叶变换是函数傅里叶变换的乘积。即,一个域中的卷积相当于另一个域中的乘积,例如时域中的卷积就对应于频域中的乘积。
其中表示f的傅里叶变换。
这一定理对拉普拉斯变换、双边拉普拉斯变换、Z变换、Mellin变换和Hartley变换(参见Mellin inversion theorem)等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。
利用卷积定理可以简化卷积的运算量。对于长度为的序列,按照卷积的定义进行计算,需要做组对位乘法,其计算复杂度为;而利用傅里叶变换将序列变换到频域上后,只需要一组对位乘法,利用傅里叶变换的快速算法之后,总的计算复杂度为。这一结果可以在快速乘法计算中得到应用。
应用
卷积在科学、工程和数学上都有很多应用:
外部链接
- PlanetMath上Convolution的資料。
- Visual convolution Java Applet
- Lecture notes, Jian-Jiun Ding (2013), Advanced Digital Signal Processing 页面存档备份,存于