亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

簡單介紹

卷積是分析數(shù)學(xué)中一種重要的運算。設(shè)：f(x){\displaystyle f(x)},g(x){\displaystyle g(x)}是R{\displaystyle \mathbb {R} }上的兩個可積函數(shù)，作積分：

可以證明，關(guān)于幾乎所有的x∈ ∈ -->(? ? -->∞ ∞ -->,∞ ∞ -->){\displaystyle x\in (-\infty ,\infty )}，上述積分是存在的。這樣，隨著x{\displaystyle x}的不同取值，這個積分就定義了一個新函數(shù)h(x){\displaystyle h(x)}，稱為函數(shù)f{\displaystyle f}與g{\displaystyle g}的卷積，記為h(x)=(f? ? -->g)(x){\displaystyle h(x)=(f*g)(x)}。我們可以輕易驗證：(f? ? -->g)(x)=(g? ? -->f)(x){\displaystyle (f*g)(x)=(g*f)(x)}，并且(f? ? -->g)(x){\displaystyle (f*g)(x)}仍為可積函數(shù)。這就是說，把卷積代替乘法，L1(R1){\displaystyle 巴拿赫1}(R^{1})}空間是一個代數(shù)，甚至是巴拿赫代數(shù)。雖然這里為了方便我們假設(shè) f,g∈ ∈ -->L1(R){\displaystyle \textstyle f,g\in L^{1}(\mathbb {R} )}，不過卷積只是運算符號，理論上并不需要對函數(shù) f,g{\displaystyle f,g} 有特別的限制，雖然常常要求 f,g{\displaystyle f,g} 至少是可測函數(shù)（measurable function）（如果不是可測函數(shù)的話，積分可能根本沒有意義），至于生成的卷積函數(shù)性質(zhì)會在運算之后討論。

卷積與傅里葉變換有著密切的關(guān)系。例如兩函數(shù)的傅里葉變換的乘積等于它們卷積后的傅里葉變換，利用此一性質(zhì)，能簡化傅里葉分析中的許多問題。

由卷積得到的函數(shù)f? ? -->g{\displaystyle f*g}一般要比f{\displaystyle f}和g{\displaystyle g}都光滑。特別當g{\displaystyle g}為具有緊支集的光滑函數(shù)，f{\displaystyle f}為局部可積時，它們的卷積f? ? -->g{\displaystyle f*g}也是光滑函數(shù)。利用這一性質(zhì)，對于任意的可積函數(shù)f{\displaystyle f}，都可以簡單地構(gòu)造出一列逼近于f{\displaystyle f}的光滑函數(shù)列fs{\displaystyle f_{s}}，這種方法稱為函數(shù)的光滑化或正則化。

卷積的概念還可以推廣到數(shù)列、測度以及廣義函數(shù)上去。

定義

函數(shù)f,g{\displaystyle f,g} 是定義在 Rn{\displaystyle \mathbb {R} ^{n}} 上的可測函數(shù)（measurable function），f與g的卷積記作f? ? -->g{\displaystyle f*g}，它是其中一個函數(shù)翻轉(zhuǎn)并平移后與另一個函數(shù)的乘積的積分，是一個對平移量的函數(shù)。，也就是：

如果函數(shù)不是定義在 Rn{\displaystyle \mathbb {R} ^{n}} 上，可以把函數(shù)定義域以外的值都規(guī)定成零，這樣就變成一個定義在 Rn{\displaystyle \mathbb {R} ^{n}} 上的函數(shù)。

離散卷積

對于定義在整數(shù) Z{\displaystyle \mathbb {Z} } 上的函數(shù) f,g{\displaystyle f,g}，卷積定義為

這里一樣把函數(shù)定義域以外的值當成零，所以可以擴展函數(shù)到所有整數(shù)上（如果本來不是的話）。

當g[n]{\displaystyle g[n]} 的支撐集（support）為有限長度M{\displaystyle M}，上式會變成有限和：

計算離散卷積的方法

計算卷積f[n]? ? -->g[n]{\displaystyle f[n]*g[n]}有三種主要的方法，分別為

直接計算（Direct Method）

快速傅里葉變換（FFT）

分段卷積（sectioned convolution）

方法1是直接利用定義來計算卷積，而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法，如使用數(shù)論變換。

方法1：直接計算

作法：利用卷積的定義

若f[n]{\displaystyle f[n]}和g[n]{\displaystyle g[n]}皆為實數(shù)信號，則需要MN{\displaystyle MN}個乘法。

若f[n]{\displaystyle f[n]}和g[n]{\displaystyle g[n]}皆為更一般性的復(fù)數(shù)信號，不使用復(fù)數(shù)乘法的快速算法，會需要4MN{\displaystyle 4MN}個乘法;但若使用復(fù)數(shù)乘法的快速算法，則可簡化至3MN{\displaystyle 3MN}個乘法。

方法2：快速傅里葉變換（FFT）

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

作法：因此這個方法即是先將信號從時域轉(zhuǎn)成頻域：

特別注意DFT和IDFT的點數(shù)P{\displaystyle P}要滿足P≥ ≥ -->M+N? ? -->1{\displaystyle P\geq M+N-1}。

由于DFT有快速算法FFT，所以運算量為O(Plog2? ? -->P){\displaystyle O(P\log _{2}P)}

假設(shè)P{\displaystyle P}點DFT的乘法量為a{\displaystyle a}，f[n]{\displaystyle f[n]}和g[n]{\displaystyle g[n]}為一般性的復(fù)數(shù)信號，并使用復(fù)數(shù)乘法的快速算法，則共需要3a+3P{\displaystyle 3a+3P}個乘法。

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

概念：將f[n]{\displaystyle f[n]}切成好幾段，每一段分別和g[n]{\displaystyle g[n]}做卷積后，再將結(jié)果相加。

作法：先將f[n]{\displaystyle f[n]}切成每段長度為L{\displaystyle L}的區(qū)段（L>M{\displaystyle L>M}），假設(shè)共切成S段：

總共只需要做P{\displaystyle P}點FFT 2S+1{\displaystyle 2S+1}次，因為g[n]{\displaystyle g[n]}只需要做一次FFT。

假設(shè)P{\displaystyle P}點DFT的乘法量為a{\displaystyle a}，f[n]{\displaystyle f[n]}和g[n]{\displaystyle g[n]}為一般性的復(fù)數(shù)信號，并使用復(fù)數(shù)乘法的快速算法，則共需要(2S+1)a+3SP{\displaystyle (2S+1)a+3SP}個乘法。

運算量：NL3(L+M? ? -->1)[log2? ? -->(L+M? ? -->1)+1]{\displaystyle {\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}

運算復(fù)雜度：O(N){\displaystyle O(N)}，和N{\displaystyle N}呈線性，較方法2小。

分為 Overlap-Add 和 Overlap-Save 兩種方法。

分段卷積: Overlap-Add

欲做x[n]? ? -->h[n]{\displaystyle x[n]*h[n]}的分段卷積分，x[n]{\displaystyle x[n]} 長度為 N{\displaystyle N}，h[n]{\displaystyle h[n]} 長度為 M{\displaystyle M},

Step 1: 將x[n]{\displaystyle x[n]}每 L{\displaystyle L} 分成一段

Step 2: 再每段 L{\displaystyle L} 點后面添加 M? ? -->1{\displaystyle M-1} 個零，變成長度 L+M? ? -->1{\displaystyle L+M-1}

Step 3: 把 h[n]{\displaystyle h[n]} 添加 L? ? -->1{\displaystyle L-1}個零，變成長度 L+M? ? -->1{\displaystyle L+M-1}的 h′[n]{\displaystyle h"[n]}

Step 4: 把每個 x[n]{\displaystyle x[n]} 的小段和 h′[n]{\displaystyle h"[n]} 做快速卷積，也就是IDFTL+M? ? -->1{DFTL+M? ? -->1(x[n])DFTL+M? ? -->1(h′[n])}{\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h"[n])}\}}，每小段會得到長度 L+M? ? -->1{\displaystyle L+M-1} 的時域信號

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

Step 6: 會發(fā)現(xiàn)在每一段的后面 M? ? -->1{\displaystyle M-1} 點有重疊，將所有點都相加起來，顧名思義 Overlap-Add，最后得到結(jié)果

舉例來說:

x[n]=[1,2,3,4,5,? ? -->1,? ? -->2,? ? -->3,? ? -->4,? ? -->5,1,2,3,4,5]{\displaystyle x[n]=[1,2,3,4,5,-1,-2,-3,-4,-5,1,2,3,4,5]}, 長度 N=15{\displaystyle N=15}

h[n]=[1,2,3]{\displaystyle h[n]=[1,2,3]}, 長度 M=3{\displaystyle M=3}

令 L=5{\displaystyle L=5}

x[n]和h[n]

令 L=5{\displaystyle L=5} 切成三段，分別為 x0[n],x1[n],x2[n]{\displaystyle x_{0}[n],x_{1}[n],x_{2}[n]}, 每段填 M? ? -->1{\displaystyle M-1} 個零，并將 h[n]{\displaystyle h[n]} 填零至長度 L+M? ? -->1{\displaystyle L+M-1}

分段x[n]

將每一段做IDFTL+M? ? -->1{DFTL+M? ? -->1(x[n])DFTL+M? ? -->1(h′[n])}{\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h"[n])}\}}

分段運算結(jié)果

若將每小段擺在一起，可以注意到第一段的范圍是 0～ ～ -->6{\displaystyle 0\thicksim 6} ，第二段的范圍是 5～ ～ -->11{\displaystyle 5\thicksim 11}，第三段的范圍是 10～ ～ -->16{\displaystyle 10\thicksim 16}，三段的范圍是有重疊的

合并分段運算結(jié)果

最后將三小段加在一起，并將結(jié)果和未分段的卷積做比較，上圖是分段的結(jié)果，下圖是沒有分段并利用快速卷積所算出的結(jié)果，驗證兩者運算結(jié)果相同。

結(jié)果比較圖

分段卷積: Overlap-Save

欲做x[n]? ? -->h[n]{\displaystyle x[n]*h[n]}的分段卷積分，x[n]{\displaystyle x[n]} 長度為 N{\displaystyle N}，h[n]{\displaystyle h[n]} 長度為 M{\displaystyle M},

Step 1: 將 x[n]{\displaystyle x[n]} 前面填 M? ? -->1{\displaystyle M-1} 個零

Step 2: 第一段 i=0{\displaystyle i=0}, 從新的 x[n]{\displaystyle x[n]} 中 L× × -->i? ? -->(M? ? -->1)× × -->i{\displaystyle L\times i-(M-1)\times i} 取到 L× × -->(i+1)? ? -->(M? ? -->1)× × -->i? ? -->1{\displaystyle L\times (i+1)-(M-1)\times i-1} 總共 L{\displaystyle L} 點當做一段，因此每小段會重復(fù)取到前一小段的 M? ? -->1{\displaystyle M-1} 點，取到新的一段全為零為止

Step 3: 把 h[n]{\displaystyle h[n]} 添加 L? ? -->M{\displaystyle L-M} 個零，變成長度 L{\displaystyle L} 的 h′[n]{\displaystyle h"[n]}

Step 4: 把每個 x[n]{\displaystyle x[n]} 的小段和 h′[n]{\displaystyle h"[n]} 做快速卷積，也就是IDFTL{DFTL(x[n])DFTL(h′[n])}{\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h"[n])}\}}，每小段會得到長度 L{\displaystyle L} 的時域信號

Step 5: 對于每個 i{\displaystyle i} 小段，只會保留末端的 L? ? -->(M? ? -->1){\displaystyle L-(M-1)} 點，因此得名 Overlap-Save

Step 6: 將所有保留的點合再一起，得到最后結(jié)果

舉例來說:

x[n]=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]{\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}, 長度 N=15{\displaystyle N=15}

h[n]=[1,2,3]{\displaystyle h[n]=[1,2,3]}, 長度 M=3{\displaystyle M=3}

令 L=7{\displaystyle L=7}

x[n]和h[n]

將 x[n]{\displaystyle x[n]} 前面填 M? ? -->1{\displaystyle M-1} 個零以后，按照 Step 2 的方式分段，可以看到每一段都重復(fù)上一段的 M? ? -->1{\displaystyle M-1} 點

分段x[n]

再將每一段做 IDFTL{DFTL(x[n])DFTL(h′[n])}{\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h"[n])}\}}以后可以得到

分段運算結(jié)果

保留每一段末端的 L? ? -->(M? ? -->1){\displaystyle L-(M-1)} 點，擺在一起以后，可以注意到第一段的范圍是 0～ ～ -->4{\displaystyle 0\thicksim 4} ，第二段的范圍是 5～ ～ -->9{\displaystyle 5\thicksim 9}，第三段的范圍是 10～ ～ -->14{\displaystyle 10\thicksim 14}，第四段的范圍是 15～ ～ -->16{\displaystyle 15\thicksim 16}，四段的范圍是沒有重疊的

合并分段運算結(jié)果

將結(jié)果和未分段的卷積做比較，下圖是分段的結(jié)果，上圖是沒有分段并利用快速卷積所算出的結(jié)果，驗證兩者運算結(jié)果相同。

結(jié)果比較圖

至于為什么要把前面 M? ? -->1{\displaystyle M-1} 丟掉?

以下以一例子來闡述:

x[n]=[1,2,3,4,5,6,7,8,9,10]{\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10]}, 長度 L=10{\displaystyle L=10}，

h[n]=[1,2,3,4,5]{\displaystyle h[n]=[1,2,3,4,5]}, 長度 M=5{\displaystyle M=5},

第一條藍線代表 y{\displaystyle y} 軸，而兩條藍線之間代表長度 L{\displaystyle L}，是在做快速卷積時的周期

x[n]和h[n]

當在做快速卷積時IDFTL{DFTL(x[n])DFTL(h′[n])}{\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h"[n])}\}}，是把信號視為周期 L{\displaystyle L}，在時域上為循環(huán)卷積分,

而在一開始前 M? ? -->1{\displaystyle M-1} 點所得到的值，是 h[0],h[6],h[7],h[8],h[9]{\displaystyle h[0],h[6],h[7],h[8],h[9]} 和 x[0],x[6],x[7],x[8],x[9]{\displaystyle x[0],x[6],x[7],x[8],x[9]} 內(nèi)積的值，

然而 h[6],h[7],h[8],h[9]{\displaystyle h[6],h[7],h[8],h[9]} 這 M? ? -->1{\displaystyle M-1} 個值應(yīng)該要為零，以往在做快速卷積時長度為 L+M? ? -->1{\displaystyle L+M-1} 時不會遇到這些問題，

而今天因為在做快速卷積時長度為 L{\displaystyle L} 才會把這 M? ? -->1{\displaystyle M-1} 點算進來，因此我們要丟棄這 M? ? -->1{\displaystyle M-1} 點內(nèi)積的結(jié)果

循環(huán)卷積

為了要丟棄這 M? ? -->1{\displaystyle M-1} 點內(nèi)積的結(jié)果，位移 h[? ? -->n]{\displaystyle h[-n]}M? ? -->1{\displaystyle M-1} 點，并把位移以后內(nèi)積合的值才算有效。

位移以后內(nèi)積

應(yīng)用時機

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

以下根據(jù)f[n]{\displaystyle f[n]}和g[n]{\displaystyle g[n]}的長度（N,M{\displaystyle N,M}）分成5類，并列出適合使用的方法：

M{\displaystyle M}為一非常小的整數(shù) - 直接計算

M? ? -->N{\displaystyle M\ll N} - 分段卷積

M≈ ≈ -->N{\displaystyle M\approx N} - 快速傅里葉變換

M? ? -->N{\displaystyle M\gg N} - 分段卷積

N{\displaystyle N}為一非常小的整數(shù) - 直接計算

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

例子

Q1：當N=2000,M=17{\displaystyle N=2000,M=17}，適合用哪種方法計算卷積?

Ans：

因此，當N=2000,M=17{\displaystyle N=2000,M=17}，所需總乘法量：分段卷積

Q2：當N=1024,M=3{\displaystyle N=1024,M=3}，適合用哪種方法計算卷積?

Ans：

因此，當N=1024,M=3{\displaystyle N=1024,M=3}，所需總乘法量：分段卷積

雖然當M{\displaystyle M}是個很小的正整數(shù)時，大致上適合使用直接計算。但實際上還是將3個方法所需的乘法量都算出來，才能知道用哪種方法可以達到最高的效率。

Q3：當N=1024,M=600{\displaystyle N=1024,M=600}，適合用哪種方法計算卷積?

Ans：

因此，當N=1024,M=600{\displaystyle N=1024,M=600}，所需總乘法量：快速傅里葉變換 = 分段卷積

多元函數(shù)卷積

按照翻轉(zhuǎn)、平移、積分的定義，還可以類似的定義多元函數(shù)上的積分：

性質(zhì)

各種卷積算子都滿足下列性質(zhì)：

其中a{\displaystyle a}為任意實數(shù)（或復(fù)數(shù)）。

其中Df表示f的微分，如果在離散域中則是指差分算子，包括前向差分與后向差分兩種：

前向差分：D+f(n)=f(n+1)? ? -->f(n){\displaystyle {\mathcal {D}}^{+}f(n)=f(n+1)-f(n)}

后向差分：D? ? -->f(n)=f(n)? ? -->f(n? ? -->1){\displaystyle {\mathcal {D}}^{-}f(n)=f(n)-f(n-1)}

卷積定理

卷積定理指出，函數(shù)卷積的傅里葉變換是函數(shù)傅里葉變換的乘積。即，一個域中的卷積相當于另一個域中的乘積，例如時域中的卷積就對應(yīng)于頻域中的乘積。

其中F(f){\displaystyle {\mathcal {F}}(f)}表示f的傅里葉變換。

這一定理對拉普拉斯變換、雙邊拉普拉斯變換、Z變換、Mellin變換和Hartley變換（參見Mellin inversion theorem（英語：Mellin inversion theorem））等各種傅里葉變換的變體同樣成立。在調(diào)和分析中還可以推廣到在局部緊致的阿貝爾群上定義的傅里葉變換。

利用卷積定理可以簡化卷積的運算量。對于長度為n{\displaystyle n}的序列，按照卷積的定義進行計算，需要做2n? ? -->1{\displaystyle 2n-1}組對位乘法，其計算復(fù)雜度為O(n2){\displaystyle {\mathcal {O}}(n^{2})}；而利用傅里葉變換將序列變換到頻域上后，只需要一組對位乘法，利用傅里葉變換的快速算法之后，總的計算復(fù)雜度為O(nlog? ? -->n){\displaystyle {\mathcal {O}}(n\log n)}。這一結(jié)果可以在快速乘法計算中得到應(yīng)用。

在群上的卷積

若G是有某m測度的群（例如豪斯多夫空間上哈爾測度下局部緊致的拓撲群），對于G上m-勒貝格可積的實數(shù)或復(fù)數(shù)函數(shù)f和g，可定義它們的卷積：

對于這些群上定義的卷積同樣可以給出諸如卷積定理等性質(zhì)，但是這需要對這些群的表示理論以及調(diào)和分析的彼得-外爾定理。

應(yīng)用

卷積在科學(xué)、工程和數(shù)學(xué)上都有很多應(yīng)用：

圖像處理中，用作圖像模糊、銳化、邊緣檢測。

統(tǒng)計學(xué)中，加權(quán)的滑動平均是一種卷積。

概率論中，兩個統(tǒng)計獨立變量X與Y的和的概率密度函數(shù)是X與Y的概率密度函數(shù)的卷積。

聲學(xué)中，回聲可以用源聲與一個反映各種反射效應(yīng)的函數(shù)的卷積表示。

電子工程與信號處理中，任一個線性系統(tǒng)的輸出都可以通過將輸入信號與系統(tǒng)函數(shù)（系統(tǒng)的沖激響應(yīng)）做卷積獲得。

物理學(xué)中，任何一個線性系統(tǒng)（符合疊加原理）都存在卷積。

參見

反卷積

傅里葉變換

免責聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。