卷積

在泛函分析中，摺積，是透過兩個函式 "f" 和 "g" 生成第三個函式的一種數學運算元，表徵函式 "f" 與經過翻轉和平移的 "g" 的乘積函式所圍成的曲邊梯形的面積。如果將參加卷積的一個函式看作區間的指示函式，卷積還可以被看作是“滑動平均”的推廣。簡單介紹.卷積是數學分析中一種重要的運算。設：formula_1、formula_2是formula_3上的兩個可積函式，作積分：formula_4可以證明，關於幾乎所有的formula_5，上述積分是存在的。這樣，隨著formula_6的不同取值，這個積分就定義了一個新函式formula_7，稱為函式formula_8與formula_9的卷積，記為formula_10。我們可以輕易驗證：formula_11，並且formula_12仍為可積函式。這就是說，把卷積代替乘法，formula_13空間是一個代數，甚至是巴拿赫代數。雖然這裡為了方便我們假設 formula_14，不過摺積只是運算子號，理論上並不需要對函式 formula_15 有特別的限制，雖然常常要求 formula_15 至少是可測函式，至於生成的卷積函式性質會在運算之後討論。卷積與傅立葉變換有著密切的關係。例如兩函式的傅立葉變換的乘積等於它們卷積後的傅立葉變換，利用此一性質，能簡化傅立葉分析中的許多問題。由卷積得到的函式formula_17一般要比formula_8和formula_9都光滑。特別當formula_9為具有緊支集的光滑函式，formula_8為區域性可積時，它們的卷積formula_22也是光滑函式。利用這一性質，對於任意的可積函式formula_8，都可以簡單地構造出一列逼近於formula_8的光滑函式列formula_25，這種方法稱為函式的光滑化或正則化。卷積的概念還可以推廣到數列、測度以及廣義函式上去。定義.函式 formula_15 是定義在 formula_27 上的可測函式，並平移後，與另一個函式的乘積的積分，是一個對平移量的函式，也就是：formula_31。如果函式不是定義在 formula_27 上，可以把函式定義域以外的值都規定成零，這樣就變成一個定義在 formula_27 上的函式。離散卷積.對於定義在整數 formula_34 上的函式 formula_35，卷積定義為formula_36formula_37這裡一樣把函式定義域以外的值當成零，所以可以擴充套件函式到所有整數上。當formula_38 的支撐集為有限長度formula_39，上式會變成有限和：formula_40計算離散卷積的方法.計算卷積formula_41有三種主要的方法，分別為方法1是直接利用定義來計算卷積，而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法，如使用數論轉換。formula_42因此，使用定義直接計算卷積的複雜度為formula_50。formula_51，可以看出在頻域的計算較簡單。formula_52，於是formula_53，最後再將頻域訊號轉回時域，就完成了卷積的計算：formula_54總共做了2次DFT和1次IDFT。formula_68Section 1: formula_69Section 2: formula_70formula_71Section r: formula_72formula_71Section S: formula_74，formula_43為各個section的和formula_76。因此，formula_77，每一小段作卷積則是採用方法2，先將時域訊號轉到頻域相乘，再轉回時域：formula_78。方法3：分段卷積.分段卷積: Overlap-Add欲做formula_90的分段卷積分，formula_91 長度為 formula_92，formula_93 長度為 formula_94,Step 1: 將formula_91每 formula_66 分成一段Step 2: 再每段 formula_66 點後面新增 formula_98 個零，變成長度 formula_99Step 3: 把 formula_93 新增 formula_101個零，變成長度 formula_99的 formula_103Step 4: 把每個 formula_91 的小段和 formula_103 做快速卷積，也就是formula_106，每小段會得到長度 formula_99 的時域訊號Step 5: 放置第 formula_108 個小段的起點在位置 formula_109 上, formula_110Step 6: 會發現在每一段的後面 formula_98 點有重疊，將所有點都相加起來，顧名思義 Overlap-Add，最後得到結果舉例來說:formula_112, 長度 formula_113formula_114, 長度 formula_115令 formula_116令 formula_116 切成三段，分別為 formula_118, 每段填 formula_98 個零，並將 formula_93 填零至長度 formula_99將每一段做formula_106若將每小段擺在一起，可以注意到第一段的範圍是 formula_123 ，第二段的範圍是 formula_124，第三段的範圍是 formula_125，三段的範圍是有重疊的最後將三小段加在一起，並將結果和未分段的卷積做比較，上圖是分段的結果，下圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。分段卷積: Overlap-Save欲做formula_90的分段卷積分，formula_91 長度為 formula_92，formula_93 長度為 formula_94,Step 1: 將 formula_91 前面填 formula_98 個零Step 2: 第一段 formula_133, 從新的 formula_91 中 formula_135 取到 formula_136 總共 formula_66 點當做一段，因此每小段會重複取到前一小段的 formula_98 點，取到新的一段全為零為止Step 3: 把 formula_93 新增 formula_140 個零，變成長度 formula_66 的 formula_103Step 4: 把每個 formula_91 的小段和 formula_103 做快速卷積，也就是formula_145，每小段會得到長度 formula_66 的時域訊號Step 5: 對於每個 formula_108 小段，只會保留末端的 formula_148 點，因此得名 Overlap-SaveStep 6: 將所有保留的點合再一起，得到最後結果舉例來說:formula_149, 長度 formula_113formula_114, 長度 formula_115令 formula_153 將 formula_91 前面填 formula_98 個零以後，按照 Step 2 的方式分段，可以看到每一段都重複上一段的 formula_98 點再將每一段做 formula_145以後可以得到保留每一段末端的 formula_148 點，擺在一起以後，可以注意到第一段的範圍是 formula_159 ，第二段的範圍是 formula_160，第三段的範圍是 formula_161，第四段的範圍是 formula_162，四段的範圍是沒有重疊的將結果和未分段的卷積做比較，下圖是分段的結果，上圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。至於為什麼要把前面 formula_98 丟掉?以下以一例子來闡述:formula_164, 長度 formula_165，formula_166, 長度 formula_167,第一條藍線代表 formula_168 軸，而兩條藍線之間代表長度 formula_66，是在做快速摺積時的週期當在做快速摺積時formula_145，是把訊號視為週期 formula_66，在時域上為迴圈摺積分,而在一開始前 formula_98 點所得到的值，是 formula_173 和 formula_174 內積的值，然而 formula_175 這 formula_98 個值應該要為零，以往在做快速摺積時長度為 formula_99 時不會遇到這些問題，而今天因為在做快速摺積時長度為 formula_66 才會把這 formula_98 點算進來，因此我們要丟棄這 formula_98 點內積的結果為了要丟棄這 formula_98 點內積的結果，位移 formula_182 formula_98 點，並把位移以後內積合的值才算有效。應用時機.以上三種方法皆可用來計算卷積，其差別在於所需總體乘法量不同。基於運算量以及效率的考量，在計算卷積時，通常會選擇所需總體乘法量較少的方法。以下根據formula_43和formula_38的長度分成5類，並列出適合使用的方法：基本上，以上只是粗略的分類。在實際應用時，最好還是算出三種方法所需的總乘法量，再選擇其中最有效率的方法來計算卷積。例子.Q1：當formula_192，適合用哪種方法計算卷積?Ans：方法1：所需乘法量為formula_193方法2：formula_194，而2016點的DFT最少乘法數formula_195，所以總乘法量為formula_196方法3：若切成8塊，則formula_198。選formula_199，則總乘法量為formula_200，比方法1和2少了很多。但是若要找到最少的乘法量，必須依照以下步驟(1)先找出formula_66:解formula_202 : formula_203(2)由formula_204算出點數在formula_58附近的DFT所需最少的乘法量，選擇DFT的點數(3)最後由formula_206算出formula_207因此，(1)由運算量對formula_66的偏微分為0而求出formula_209(2)formula_210，所以選擇101點DFT附近點數乘法量最少的點數formula_211或formula_212。(3-1)當formula_213，總乘法量為formula_214。(3-2)當formula_215，總乘法量為formula_216。由此可知，切成20塊會有較好的效率，而所需總乘法量為21480。Q2：當formula_218，適合用哪種方法計算卷積?Ans：方法1：所需乘法量為formula_219方法2：formula_220，選擇1026點DFT附近點數乘法量最少的點數，formula_221。因此，所需乘法量為formula_222方法3：(1)由運算量對formula_66的偏微分為0而求出formula_224(2)formula_225，所以選擇7點DFT附近點數乘法量最少的點數formula_226或formula_227或formula_228。(3-1)當formula_229，總乘法量為formula_230。(3-2)當formula_231，總乘法量為formula_232。(3-3)當formula_233，總乘法量為formula_234。由此可知，切成171塊會有較好的效率，而所需總乘法量為5476。Q3：當formula_237，適合用哪種方法計算卷積?Ans：方法1：所需乘法量為formula_238方法2：formula_239，選擇1026點DFT附近點數乘法量最少的點數，formula_240。因此，所需乘法量為formula_196方法3：(1)由運算量對formula_66的偏微分為0而求出formula_243(2)formula_244，所以選擇1623點DFT附近點數乘法量最少的點數formula_245。(3)當formula_246，總乘法量為formula_247。由此可知，此時切成一段，就跟方法2一樣，所需總乘法量為44232。多元函式卷積.按照翻轉、平移、積分的定義，還可以類似的定義多元函式上的積分：formula_249性質.各種卷積運算元都滿足下列性質：formula_250formula_251formula_252formula_253其中formula_254為任意實數。formula_255其中D"f"表示"f"的微分，如果在離散域中則是指差分運算元，包括前向差分與後向差分兩種：卷積定理.卷積定理指出，函式卷積的傅立葉變換是函式傅立葉變換的乘積。即，一個域中的卷積相當於另一個域中的乘積，例如時域中的卷積就對應於頻域中的乘積。formula_258其中formula_259表示"f"的傅立葉變換。這一定理對拉普拉斯變換、雙邊拉普拉斯變換、Z變換、Mellin變換和Hartley變換等各種傅立葉變換的變體同樣成立。在調和分析中還可以推廣到在區域性緊緻的阿貝爾群上定義的傅立葉變換。利用卷積定理可以簡化卷積的運算量。對於長度為formula_260的序列，按照卷積的定義進行計算，需要做formula_261組對位乘法，其計算複雜度為formula_262；而利用傅立葉變換將序列變換到頻域上後，只需要一組對位乘法，利用傅立葉變換的快速演算法之後，總的計算複雜度為formula_263。這一結果可以在快速乘法計算中得到應用。在群上的卷積.若"G"是有某"m" 測度的群，對於"G"上"m"-勒貝格可積的實數或複數函式"f"和"g"，可定義它們的卷積：formula_264對於這些群上定義的卷積同樣可以給出諸如卷積定理等性質，但是這需要對這些群的表示理論以及調和分析的彼得-外爾定理。應用.卷積在科學、工程和數學上都有很多應用：