卷积 |
您所在的位置：网站首页 › 算法的定义是 › 卷积 |
卷积
 图示两个方形脈衝波的捲積。其中函数"g"首先对
τ
=
0
{\displaystyle \tau =0}
反射，接著平移"t"，成為
g
(
t
−
τ
)
{\displaystyle g(t-\tau )}
。那么重叠部份的面积就相当于"t"处的卷积，其中橫坐標代表待变量
τ
{\displaystyle \tau }
以及新函數
f
∗
g
{\displaystyle f\ast g}
的自變量"t"。
 圖示方形脈衝波和指數衰退的脈衝波的捲積（後者可能出現於RC電路中），同樣地重疊部份面積就相當於"t"處的捲積。注意到因為"g"是對稱的，所以在這兩張圖中，反射並不會改變它的形狀。
在泛函分析中，捲積（又称疊積（convolution）、褶積或旋積），是透過两个函数 f 和 g 生成第三个函数的一种数学算子，表徵函数 f 与经过翻转和平移的 g 的乘積函數所圍成的曲邊梯形的面積。如果将参加卷积的一个函数看作区间的指示函数，卷积还可以被看作是“滑動平均”的推廣。 目录 1 简单介绍 2 定义 3 离散卷积 3.1 計算离散卷積的方法 3.1.1 方法1：直接計算 3.1.2 方法2：快速傅立葉轉換（FFT） 3.1.3 方法3：分段卷積（sectioned convolution） 3.1.4 應用時機 3.1.4.1 例子 4 多元函数卷积 5 性质 6 卷积定理 7 在群上的卷积 8 应用 9 参见 10 外部链接 简单介绍[编辑]卷积是数学分析中一种重要的运算。设： f ( x ) {\displaystyle f(x)} 、 g ( x ) {\displaystyle g(x)} 是 R {\displaystyle \mathbb {R} } 上的两个可积函数，作积分： ∫ − ∞ ∞ f ( τ ) g ( x − τ ) d τ {\displaystyle \int _{-\infty }^{\infty }f(\tau )g(x-\tau )\,\mathrm {d} \tau }可以证明，关于几乎所有的 x ∈ ( − ∞ , ∞ ) {\displaystyle x\in (-\infty ,\infty )} ，上述积分是存在的。这样，随着 x {\displaystyle x} 的不同取值，这个积分就定义了一个新函数 h ( x ) {\displaystyle h(x)} ，称为函数 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)} 仍为可积函数。这就是说，把卷积代替乘法， L 1 ( R 1 ) {\displaystyle L^{1}(R^{1})} 空间是一个代数，甚至是巴拿赫代数。雖然這裡為了方便我們假設 f , g ∈ L 1 ( R ) {\displaystyle \textstyle f,g\in L^{1}(\mathbb {R} )} ，不過捲積只是運算符號，理論上並不需要對函數 f , g {\displaystyle f,g} 有特別的限制，雖然常常要求 f , g {\displaystyle f,g} 至少是可測函數（measurable function）（如果不是可測函數的話，積分可能根本沒有意義），至於生成的卷積函數性質會在運算之後討論。 卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换，利用此一性質，能簡化傅里叶分析中的许多问题。 由卷积得到的函数 f ∗ g {\displaystyle f*g} 一般要比 f {\displaystyle f} 和 g {\displaystyle g} 都光滑。特别当 g {\displaystyle g} 为具有紧支集的光滑函数， f {\displaystyle f} 为局部可积时，它们的卷积 f ∗ g {\displaystyle f*g} 也是光滑函数。利用这一性质，对于任意的可积函数 f {\displaystyle f} ，都可以简单地构造出一列逼近于 f {\displaystyle f} 的光滑函数列 f s {\displaystyle f_{s}} ，这种方法称为函数的光滑化或正则化。 卷积的概念还可以推广到数列、测度以及广义函数上去。 定义[编辑]函数 f , g {\displaystyle f,g} 是定義在 R n {\displaystyle \mathbb {R} ^{n}} 上的可測函數（measurable function）， f {\displaystyle f} 与 g {\displaystyle g} 的卷积记作 f ∗ g {\displaystyle f*g} ，它是其中一个函数反轉（reverse），並平移后，与另一个函数的乘积的积分，是一个对平移量的函数，也就是： ( f ∗ g ) ( t ) = d e f ∫ R n f ( τ ) g ( t − τ ) d τ {\displaystyle (f*g)(t)\ \ \,{\stackrel {\mathrm {def} }{=}}\ \int _{\mathbb {R} ^{n}}f(\tau )g(t-\tau )\,d\tau } 。如果函數不是定義在 R n {\displaystyle \mathbb {R} ^{n}} 上，可以把函數定義域以外的值都規定成零，這樣就變成一個定義在 R n {\displaystyle \mathbb {R} ^{n}} 上的函數。 圖解摺積 已知两函数f(t)和g(t)。右图第一行两图分别为f(t)和g(t)。 首先將兩個函數都用 τ {\displaystyle \tau } 來表示，从而得到f( τ {\displaystyle \tau } )和g( τ {\displaystyle \tau } )。将函数g( τ {\displaystyle \tau } )向左移动t个单位，得到函数g( τ {\displaystyle \tau } +t)的图像。将g( τ {\displaystyle \tau } +t)翻转至纵轴另一侧，得到g(t- τ {\displaystyle \tau } )的图像。右图第二行两图分别为f( τ {\displaystyle \tau } )和g(t- τ {\displaystyle \tau } )。 由于t非常数（实际上是时间变量），当时间变量（以下简称“时移”）取不同值时， g ( t − τ ) {\displaystyle g(t-\tau )} 能沿着 τ {\displaystyle \tau } 轴“滑动”。右图第三四五行可理解为“滑动”。 讓t從-∞滑動到+∞。兩函數交會時，計算交會範圍中兩函數乘積的積分值。換句話說，我們是在計算一個滑動的的加權總和(weighted-sum)。也就是使用 g ( t − τ ) {\displaystyle g(t-\tau )} 當做加權函數，來對 f ( τ ) {\displaystyle f(\tau )} 取加權值。 最後得到的波形（未包含在此圖中）就是f和g的摺積。如果f（t）是一個單位脈衝，我們得到的乘積就是g（t）本身，稱為衝激響應。
离散卷积[编辑]
对于定义在整數 Z {\displaystyle \mathbb {Z} } 上的函数 f , g {\displaystyle f,g} ，卷积定义为 ( f ∗ g ) [ n ] = d e f ∑ m = − ∞ ∞ f [ m ] g [ n − m ] {\displaystyle (f*g)[n]\ \ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }{f[m]g[n-m]}} = ∑ m = − ∞ ∞ f [ n − m ] g [ m ] . {\displaystyle =\sum _{m=-\infty }^{\infty }f[n-m]\,g[m].}這裡一樣把函數定義域以外的值當成零，所以可以擴展函數到所有整數上（如果本來不是的話）。 當 g [ n ] {\displaystyle g[n]} 的支撐集（support）為有限長度 M {\displaystyle M} ，上式會變成有限和： ( f ∗ g ) [ n ] = ∑ m = − M M f [ n − m ] g [ m ] . {\displaystyle (f*g)[n]=\sum _{m=-M}^{M}f[n-m]g[m].} 計算离散卷積的方法[编辑]計算卷積 f [ n ] ∗ g [ n ] {\displaystyle f[n]*g[n]} 有三種主要的方法，分別為 直接計算（Direct Method） 快速傅立葉轉換（FFT） 分段卷積（sectioned convolution）方法1是直接利用定義來計算卷積，而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法，如使用數論轉換。 方法1：直接計算[编辑] 作法：利用卷積的定義 y [ n ] = f [ n ] ∗ g [ n ] = ∑ m = 0 M − 1 f [ n − m ] g [ m ] {\displaystyle y[n]=f[n]*g[n]=\sum _{m=0}^{M-1}f[n-m]g[m]} 若 f [ n ] {\displaystyle f[n]} 和 g [ n ] {\displaystyle g[n]} 皆為實數信號，則需要 M N {\displaystyle MN} 個乘法。 若 f [ n ] {\displaystyle f[n]} 和 g [ n ] {\displaystyle g[n]} 皆為更一般性的複數信號，不使用複數乘法的快速演算法，會需要 4 M N {\displaystyle 4MN} 個乘法;但若使用複數乘法的快速演算法，則可簡化至 3 M N {\displaystyle 3MN} 個乘法。 因此，使用定義直接計算卷積的複雜度為 O ( M N ) {\displaystyle O(MN)} 。 方法2：快速傅立葉轉換（FFT）[编辑] 概念：由於兩個離散信號在時域（time domain）做卷積相當於這兩個信號的離散傅立葉轉換在頻域（frequency domain）做相乘： y [ n ] = f [ n ] ∗ g [ n ] ↔ Y [ f ] = F [ f ] G [ f ] {\displaystyle y[n]=f[n]*g[n]\leftrightarrow Y[f]=F[f]G[f]} ，可以看出在頻域的計算較簡單。 作法：因此這個方法即是先將信號從時域轉成頻域： F [ f ] = D F T P ( f [ n ] ) , G [ f ] = D F T P ( g [ n ] ) {\displaystyle F[f]=DFT_{P}(f[n]),G[f]=DFT_{P}(g[n])} ，於是 Y [ f ] = D F T P ( f [ n ] ) D F T P ( g [ n ] ) {\displaystyle Y[f]=DFT_{P}(f[n])DFT_{P}(g[n])} ，最後再將頻域信號轉回時域，就完成了卷積的計算： y [ n ] = I D F T P D F T P ( f [ n ] ) D F T P ( g [ n ] ) {\displaystyle y[n]=IDFT_{P}{DFT_{P}(f[n])DFT_{P}(g[n])}} 總共做了2次DFT和1次IDFT。 特別注意DFT和IDFT的點數 P {\displaystyle P} 要滿足 P ≥ M + N − 1 {\displaystyle P\geq M+N-1} 。 由於DFT有快速演算法FFT，所以運算量為 O ( P log 2 P ) {\displaystyle O(P\log _{2}P)} 假設 P {\displaystyle P} 點DFT的乘法量為 a {\displaystyle a} ， f [ n ] {\displaystyle f[n]} 和 g [ n ] {\displaystyle g[n]} 為一般性的複數信號，並使用複數乘法的快速演算法，則共需要 3 a + 3 P {\displaystyle 3a+3P} 個乘法。 方法3：分段卷積（sectioned convolution）[编辑] 概念：將 f [ n ] {\displaystyle f[n]} 切成好幾段，每一段分別和 g [ n ] {\displaystyle g[n]} 做卷積後，再將結果相加。 作法：先將 f [ n ] {\displaystyle f[n]} 切成每段長度為 L {\displaystyle L} 的區段（ L > M {\displaystyle L>M} ），假設共切成S段： f [ n ] ( n = 0 , 1 , . . . , N − 1 ) → f 1 [ n ] , f 2 [ n ] , f 3 [ n ] , . . . , f S [ n ] ( S = ⌈ N L ⌉ ) {\displaystyle 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 {\displaystyle f_{1}[n]=f[n],n=0,1,...,L-1} Section 2: f 2 [ n ] = f [ n + L ] , n = 0 , 1 , . . . , L − 1 {\displaystyle f_{2}[n]=f[n+L],n=0,1,...,L-1} ⋮ {\displaystyle \vdots } Section r: f r [ n ] = f [ n + ( r − 1 ) L ] , n = 0 , 1 , . . . , L − 1 {\displaystyle f_{r}[n]=f[n+(r-1)L],n=0,1,...,L-1} ⋮ {\displaystyle \vdots } Section S: f S [ n ] = f [ n + ( S − 1 ) L ] , n = 0 , 1 , . . . , L − 1 {\displaystyle f_{S}[n]=f[n+(S-1)L],n=0,1,...,L-1} ， f [ n ] {\displaystyle f[n]} 為各個section的和 f [ n ] = ∑ r = 1 S f r [ n + ( r − 1 ) L ] {\displaystyle f[n]=\sum _{r=1}^{S}f_{r}[n+(r-1)L]} 。 因此， y [ n ] = f [ n ] ∗ g [ n ] = ∑ r = 1 S ∑ m = 0 M − 1 f r [ n + ( r − 1 ) L − m ] g [ m ] {\displaystyle 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 ] = I D F T ( ∑ r = 1 S ∑ m = 0 M − 1 D F T P ( f r [ n + ( r − 1 ) L − m ] ) D F T P ( g [ m ] ) ) , P ≥ M + L − 1 {\displaystyle 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\geq M+L-1} 。 總共只需要做 P {\displaystyle P} 點FFT 2 S + 1 {\displaystyle 2S+1} 次，因為 g [ n ] {\displaystyle g[n]} 只需要做一次FFT。 假設 P {\displaystyle P} 點DFT的乘法量為 a {\displaystyle a} ， f [ n ] {\displaystyle f[n]} 和 g [ n ] {\displaystyle g[n]} 為一般性的複數信號，並使用複數乘法的快速演算法，則共需要 ( 2 S + 1 ) a + 3 S P {\displaystyle (2S+1)a+3SP} 個乘法。 運算量： N L 3 ( L + M − 1 ) [ log 2 ( L + M − 1 ) + 1 ] {\displaystyle {\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]} 運算複雜度： 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]} 做快速卷積，也就是 I D F T L + M − 1 { D F T L + M − 1 ( x [ n ] ) D F T L + 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 , . . . , ⌈ N L ⌉ − 1 {\displaystyle i=0,1,...,\lceil {\frac {N}{L}}\rceil -1} Step 6: 會發現在每一段的後面 M − 1 {\displaystyle M-1} 點有重疊，將所有點都相加起來，顧名思義 Overlap-Add，最後得到結果 舉例來說: 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]](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fc/Data_overlap_add.png/300px-Data_overlap_add.png)
x[n]和h[n] 令 L = 5 {\displaystyle L=5} 切成三段，分別為 x 0 [ n ] , x 1 [ n ] , x 2 [ 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]](http://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Seperate_x_overlap_add.png/300px-Seperate_x_overlap_add.png)
分段x[n] 將每一段做 I D F T L + M − 1 { D F T L + M − 1 ( x [ n ] ) D F T L + M − 1 ( h ′ [ n ] ) } {\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])}\}} 
分段運算結果 若將每小段擺在一起，可以注意到第一段的範圍是 0 ∼ 6 {\displaystyle 0\thicksim 6} ，第二段的範圍是 5 ∼ 11 {\displaystyle 5\thicksim 11} ，第三段的範圍是 10 ∼ 16 {\displaystyle 10\thicksim 16} ，三段的範圍是有重疊的 
合併分段運算結果 最後將三小段加在一起，並將結果和未分段的卷積做比較，上圖是分段的結果，下圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。 
結果比較圖 分段卷積: 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} 點當做一段，因此每小段會重複取到前一小段的 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]} 做快速卷積，也就是 I D F T L { D F T L ( x [ n ] ) D F T L ( 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: 將所有保留的點合再一起，得到最後結果 舉例來說: 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]](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Data_overlap_save.png/300px-Data_overlap_save.png)
x[n]和h[n] 將 x [ n ] {\displaystyle x[n]} 前面填 M − 1 {\displaystyle M-1} 個零以後，按照 Step 2 的方式分段，可以看到每一段都重複上一段的 M − 1 {\displaystyle M-1} 點 ![分段x[n]](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Seperate_x_overlap_save.png/300px-Seperate_x_overlap_save.png)
分段x[n] 再將每一段做 I D F T L { D F T L ( x [ n ] ) D F T L ( h ′ [ n ] ) } {\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}} 以後可以得到 
分段運算結果 保留每一段末端的 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} ，四段的範圍是沒有重疊的 
合併分段運算結果 將結果和未分段的卷積做比較，下圖是分段的結果，上圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。 
結果比較圖 至於為什麼要把前面 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]](http://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Original_ov_extra.png/300px-Original_ov_extra.png)
x[n]和h[n] 當在做快速摺積時 I D F T L { D F T L ( x [ n ] ) D F T L ( h ′ [ n ] ) } {\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}} ，是把訊號視為週期 L {\displaystyle L} ，在時域上為循環摺積分, 而在一開始前 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]} 內積的值， 然而 h [ 6 ] , h [ 7 ] , h [ 8 ] , h [ 9 ] {\displaystyle h[6],h[7],h[8],h[9]} 這 M − 1 {\displaystyle M-1} 個值應該要為零，以往在做快速摺積時長度為 L + M − 1 {\displaystyle L+M-1} 時不會遇到這些問題， 而今天因為在做快速摺積時長度為 L {\displaystyle L} 才會把這 M − 1 {\displaystyle M-1} 點算進來，因此我們要丟棄這 M − 1 {\displaystyle M-1} 點內積的結果 
循環摺積 為了要丟棄這 M − 1 {\displaystyle M-1} 點內積的結果，位移 h [ − n ] {\displaystyle h[-n]} M − 1 {\displaystyle M-1} 點，並把位移以後內積合的值才算有效。 
位移以後內積 應用時機[编辑]以上三種方法皆可用來計算卷積，其差別在於所需總體乘法量不同。基於運算量以及效率的考量，在計算卷積時，通常會選擇所需總體乘法量較少的方法。 以下根據 f [ n ] {\displaystyle f[n]} 和 g [ n ] {\displaystyle g[n]} 的長度（ N , M {\displaystyle N,M} ）分成5類，並列出適合使用的方法： M {\displaystyle M} 為一非常小的整數 - 直接計算 M ≪ N {\displaystyle M\ll N} - 分段卷积 M ≈ N {\displaystyle M\approx N} - 快速傅里叶变换 M ≫ N {\displaystyle M\gg N} - 分段卷积 N {\displaystyle N} 為一非常小的整數 - 直接計算基本上，以上只是粗略的分類。在實際應用時，最好還是算出三種方法所需的總乘法量，再選擇其中最有效率的方法來計算卷積。 例子[编辑]Q1：當 N = 2000 , M = 17 {\displaystyle N=2000,M=17} ，適合用哪種方法計算卷積? Ans： 方法1：所需乘法量為 3 M N = 102000 {\displaystyle 3MN=102000} 方法2： P ≥ M + N − 1 = 2016 {\displaystyle P\geq M+N-1=2016} ，而2016點的DFT最少乘法數 a = 12728 {\displaystyle a=12728} ，所以總乘法量為 3 ( a + P ) = 44232 {\displaystyle 3(a+P)=44232} 方法3： 若切成8塊（ S = 8 {\displaystyle S=8} ），則 L = 250 , P ≥ M + L − 1 = 266 {\displaystyle L=250,P\geq M+L-1=266} 。選 P = 288 {\displaystyle P=288} ，則總乘法量為 ( 2 S + 1 ) a + 3 S P = 26632 {\displaystyle (2S+1)a+3SP=26632} ，比方法1和2少了很多。 但是若要找到最少的乘法量，必須依照以下步驟 (1)先找出 L {\displaystyle L} :解 L {\displaystyle L} : ∂ N L 3 ( L + M − 1 ) [ log 2 ( L + M − 1 ) + 1 ] ∂ L = 0 {\displaystyle {\frac {\partial {{\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}}{\partial L}}=0} (2)由 P ≥ L + M − 1 {\displaystyle P\geq L+M-1} 算出點數在 P {\displaystyle P} 附近的DFT所需最少的乘法量，選擇DFT的點數 (3)最後由 L = P + 1 − M {\displaystyle L=P+1-M} 算出 L o p t {\displaystyle L_{opt}} 因此， (1)由運算量對 L {\displaystyle L} 的偏微分為0而求出 L = 85 {\displaystyle L=85} (2) P ≥ L + M − 1 = 101 {\displaystyle P\geq L+M-1=101} ，所以選擇101點DFT附近點數乘法量最少的點數 P = 96 {\displaystyle P=96} 或 P = 120 {\displaystyle P=120} 。 (3-1)當 P = 96 → a = 280 , L = P + 1 − M = 80 → S = 25 {\displaystyle P=96\to a=280,L=P+1-M=80\to S=25} ，總乘法量為 ( 2 S + 1 ) a + 3 S P = 21480 {\displaystyle (2S+1)a+3SP=21480} 。 (3-2)當 P = 120 → a = 380 , L = P + 1 − M = 104 → S = 20 {\displaystyle P=120\to a=380,L=P+1-M=104\to S=20} ，總乘法量為 ( 2 S + 1 ) a + 3 S P = 22780 {\displaystyle (2S+1)a+3SP=22780} 。 由此可知，切成20塊會有較好的效率，而所需總乘法量為21480。 因此，當 N = 2000 , M = 17 {\displaystyle N=2000,M=17} ，所需總乘法量：分段卷積 1 = 1026 {\displaystyle P\geq M+N-1=1026} ，選擇1026點DFT附近點數乘法量最少的點數， → P = 1152 , a = 7088 {\displaystyle \to P=1152,a=7088} 。 因此，所需乘法量為 3 ( a + P ) = 24342 {\displaystyle 3(a+P)=24342} 方法3： (1)由運算量對 L {\displaystyle L} 的偏微分為0而求出 L = 5 {\displaystyle L=5} (2) P ≥ L + M − 1 = 7 {\displaystyle P\geq L+M-1=7} ，所以選擇7點DFT附近點數乘法量最少的點數 P = 8 {\displaystyle P=8} 或 P = 6 {\displaystyle P=6} 或 P = 4 {\displaystyle P=4} 。 (3-1)當 P = 8 → a = 4 , L = P + 1 − M = 6 → S = 171 {\displaystyle P=8\to a=4,L=P+1-M=6\to S=171} ，總乘法量為 ( 2 S + 1 ) a + 3 S P = 5476 {\displaystyle (2S+1)a+3SP=5476} 。 (3-2)當 P = 6 → a = 4 , L = P + 1 − M = 4 → S = 256 {\displaystyle P=6\to a=4,L=P+1-M=4\to S=256} ，總乘法量為 ( 2 S + 1 ) a + 3 S P = 6660 {\displaystyle (2S+1)a+3SP=6660} 。 (3-3)當 P = 4 → a = 0 , L = P + 1 − M = 2 → S = 512 {\displaystyle P=4\to a=0,L=P+1-M=2\to S=512} ，總乘法量為 ( 2 S + 1 ) a + 3 S P = 6144 {\displaystyle (2S+1)a+3SP=6144} 。 由此可知，切成171塊會有較好的效率，而所需總乘法量為5476。 因此，當 N = 1024 , M = 3 {\displaystyle N=1024,M=3} ，所需總乘法量：分段卷積 1 = 1623 {\displaystyle P\geq M+N-1=1623} ，選擇1026點DFT附近點數乘法量最少的點數， → P = 2016 , a = 12728 {\displaystyle \to P=2016,a=12728} 。 因此，所需乘法量為 3 ( a + P ) = 44232 {\displaystyle 3(a+P)=44232} 方法3： (1)由運算量對 L {\displaystyle L} 的偏微分為0而求出 L = 1024 {\displaystyle L=1024} (2) P ≥ L + M − 1 = 1623 {\displaystyle P\geq L+M-1=1623} ，所以選擇1623點DFT附近點數乘法量最少的點數 P = 2016 {\displaystyle P=2016} 。 (3)當 P = 2016 → a = 12728 , L = P + 1 − M = 1417 → S = 1 {\displaystyle P=2016\to a=12728,L=P+1-M=1417\to S=1} ，總乘法量為 ( 2 S + 1 ) a + 3 S P = 44232 {\displaystyle (2S+1)a+3SP=44232} 。 由此可知，此時切成一段，就跟方法2一樣，所需總乘法量為44232。 因此，當 N = 1024 , M = 600 {\displaystyle N=1024,M=600} ，所需總乘法量：快速傅立葉轉換 = 分段卷積 , t n ) = ∫ ∫ ⋯ ∫ f ( τ 1 , τ 2 , ⋯ , τ n ) g ( t 1 − τ 1 , t 2 − τ 2 , ⋯ , t n − τ n , ) d τ 1 d τ 2 ⋯ d τ n {\displaystyle (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 {\displaystyle f*g=g*f\,} 结合律 f ∗ ( g ∗ h ) = ( f ∗ g ) ∗ h {\displaystyle f*(g*h)=(f*g)*h\,} 分配律 f ∗ ( g + h ) = ( f ∗ g ) + ( f ∗ h ) {\displaystyle f*(g+h)=(f*g)+(f*h)\,} 数乘结合律 a ( f ∗ g ) = ( a f ) ∗ g = f ∗ ( a g ) {\displaystyle a(f*g)=(af)*g=f*(ag)\,}其中 a {\displaystyle a} 为任意实数（或复数）。 微分定理 D ( f ∗ g ) = D f ∗ g = f ∗ D g {\displaystyle {\mathcal {D}}(f*g)={\mathcal {D}}f*g=f*{\mathcal {D}}g\,}其中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)} 卷积定理[编辑]卷积定理指出，函数卷积的傅里叶变换是函数傅里叶变换的乘积。即，一个域中的卷积相当于另一个域中的乘积，例如时域中的卷积就对应于频域中的乘积。 F ( f ∗ g ) = F ( f ) ⋅ F ( g ) {\displaystyle {\mathcal {F}}(f*g)={\mathcal {F}}(f)\cdot {\mathcal {F}}(g)}其中 F ( f ) {\displaystyle {\mathcal {F}}(f)} 表示f的傅里叶变换。 这一定理对拉普拉斯变换、双边拉普拉斯变换、Z变换、Mellin变换和Hartley变换（参见Mellin inversion theorem（英语：Mellin inversion theorem））等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。 利用卷积定理可以简化卷积的运算量。对于长度为 n {\displaystyle n} 的序列，按照卷积的定义进行计算，需要做 2 n − 1 {\displaystyle 2n-1} 组对位乘法，其计算复杂度为 O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} ；而利用傅里叶变换将序列变换到频域上后，只需要一组对位乘法，利用傅里叶变换的快速算法之后，总的计算复杂度为 O ( n log n ) {\displaystyle {\mathcal {O}}(n\log n)} 。这一结果可以在快速乘法计算中得到应用。 在群上的卷积[编辑]若G是有某m 测度的群（例如豪斯多夫空间上哈尔测度下局部紧致的拓扑群），对于G上m-勒贝格可积的实数或复数函数f和g，可定义它们的卷积： ( f ∗ g ) ( x ) = ∫ G f ( y ) g ( x y − 1 ) d m ( y ) {\displaystyle (f*g)(x)=\int _{G}f(y)g(xy^{-1})\,dm(y)\,}对于这些群上定义的卷积同样可以给出诸如卷积定理等性质，但是这需要对这些群的表示理论以及调和分析的彼得-外尔定理。 应用[编辑]卷积在科学、工程和数学上都有很多应用： 代数中，整数乘法和多项式乘法都是卷积。 图像处理中，用作图像模糊、锐化、边缘检测。 统计学中，加权的滑动平均是一种卷积。 概率论中，两个统计独立变量X与Y的和的概率密度函数是X与Y的概率密度函数的卷积。 声学中，回声可以用源声与一个反映各种反射效应的函数的卷积表示。 电子工程与信号处理中，任一个线性系统的输出都可以通过将输入信号与系统函数（系统的冲激响应）做卷积获得。 物理学中，任何一个线性系统（符合叠加原理）都存在卷积。 参见[编辑] 反卷积 自相关函数 傅里叶变换 外部链接[编辑] Convolution. PlanetMath. Visual convolution Java Applet （页面存档备份，存于互联网档案馆） Lecture notes, Jian-Jiun Ding (2013), Advanced Digital Signal Processing（页面存档备份，存于互联网档案馆） |
反射，接著平移"t"，成為
g
(
t
−
τ
)
{\displaystyle g(t-\tau )}
。那么重叠部份的面积就相当于"t"处的卷积，其中橫坐標代表待变量
τ
{\displaystyle \tau }
以及新函數
f
∗
g
{\displaystyle f\ast g}
的自變量"t"。
、
g
(
x
)
{\displaystyle g(x)}
是
R
{\displaystyle \mathbb {R} }
上的两个可积函数，作积分：
，上述积分是存在的。这样，随着
x
{\displaystyle x}
的不同取值，这个积分就定义了一个新函数
h
(
x
)
{\displaystyle h(x)}
，称为函数
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)}
仍为可积函数。这就是说，把卷积代替乘法，
L
1
(
R
1
)
{\displaystyle L^{1}(R^{1})}
空间是一个代数，甚至是巴拿赫代数。雖然這裡為了方便我們假設
f
,
g
∈
L
1
(
R
)
{\displaystyle \textstyle f,g\in L^{1}(\mathbb {R} )}
，不過捲積只是運算符號，理論上並不需要對函數
f
,
g
{\displaystyle f,g}
有特別的限制，雖然常常要求
f
,
g
{\displaystyle f,g}
一般要比
f
{\displaystyle f}
，这种方法称为函数的光滑化或正则化。
上的可測函數（measurable function），
f
{\displaystyle f}
。
取加權值。
最後得到的波形（未包含在此圖中）就是f和g的摺積。如果f（t）是一個單位脈衝，我們得到的乘積就是g（t）本身，稱為衝激響應。
上的函数
f
,
g
{\displaystyle f,g}
![(f*g)[n]\ \ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }{f[m]g[n-m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24eeb66855fb4048d42b33fc6727fdabf6068a27)
=
∑
m
=
−
∞
∞
f
[
n
−
m
]
g
[
m
]
.
{\displaystyle =\sum _{m=-\infty }^{\infty }f[n-m]\,g[m].}
![=\sum _{m=-\infty }^{\infty }f[n-m]\,g[m].](https://wikimedia.org/api/rest_v1/media/math/render/svg/f067498b1393be11cf4cecfb08f3096f14bdce59)
![g[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c5e1d771a2385e9aeb71838a40425bb07c89525)
的支撐集（support）為有限長度
M
{\displaystyle M}
，上式會變成有限和：
![(f*g)[n]=\sum _{m=-M}^{M}f[n-m]g[m].](https://wikimedia.org/api/rest_v1/media/math/render/svg/fddacde29cbcb3c6fca263493335c31a4d2ebce2)
計算离散卷積的方法[编辑]
![f[n]*g[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/53f78eb841159a85c00fe9a4331825a77341e67c)
有三種主要的方法，分別為
![y[n]=f[n]*g[n]=\sum _{m=0}^{M-1}f[n-m]g[m]](https://wikimedia.org/api/rest_v1/media/math/render/svg/1081139aae46ebd7421e11ec20351dc12688cedd)
若
f
[
n
]
{\displaystyle f[n]}
![f[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/b176b3dbcced447341ad5ab70001ef0e3231062e)
和
g
[
n
]
{\displaystyle g[n]}
個乘法。
若
f
[
n
]
{\displaystyle f[n]}
個乘法;但若使用複數乘法的快速演算法，則可簡化至
3
M
N
{\displaystyle 3MN}
個乘法。
因此，使用定義直接計算卷積的複雜度為
O
(
M
N
)
{\displaystyle O(MN)}
。
方法2：快速傅立葉轉換（FFT）[编辑]
概念：由於兩個離散信號在時域（time domain）做卷積相當於這兩個信號的離散傅立葉轉換在頻域（frequency domain）做相乘：
y
[
n
]
=
f
[
n
]
∗
g
[
n
]
↔
Y
[
f
]
=
F
[
f
]
G
[
f
]
{\displaystyle y[n]=f[n]*g[n]\leftrightarrow Y[f]=F[f]G[f]}
![y[n]=f[n]*g[n]\leftrightarrow Y[f]=F[f]G[f]](https://wikimedia.org/api/rest_v1/media/math/render/svg/27f83ca717dff1b21da43e56127c50874843b8b0)
，可以看出在頻域的計算較簡單。
作法：因此這個方法即是先將信號從時域轉成頻域：
F
[
f
]
=
D
F
T
P
(
f
[
n
]
)
,
G
[
f
]
=
D
F
T
P
(
g
[
n
]
)
{\displaystyle F[f]=DFT_{P}(f[n]),G[f]=DFT_{P}(g[n])}
![F[f]=DFT_{P}(f[n]),G[f]=DFT_{P}(g[n])](https://wikimedia.org/api/rest_v1/media/math/render/svg/af332366ed1070784c006329adcd40833e64c44d)
，於是
Y
[
f
]
=
D
F
T
P
(
f
[
n
]
)
D
F
T
P
(
g
[
n
]
)
{\displaystyle Y[f]=DFT_{P}(f[n])DFT_{P}(g[n])}
![Y[f]=DFT_{P}(f[n])DFT_{P}(g[n])](https://wikimedia.org/api/rest_v1/media/math/render/svg/93ec9e3130dcd720d4d6b1930bd492f29fee0faf)
，最後再將頻域信號轉回時域，就完成了卷積的計算：
y
[
n
]
=
I
D
F
T
P
D
F
T
P
(
f
[
n
]
)
D
F
T
P
(
g
[
n
]
)
{\displaystyle y[n]=IDFT_{P}{DFT_{P}(f[n])DFT_{P}(g[n])}}
![y[n]=IDFT_{P}{DFT_{P}(f[n])DFT_{P}(g[n])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adc12d1e8c9712ca85bf040d7e8573842c545588)
總共做了2次DFT和1次IDFT。
特別注意DFT和IDFT的點數
P
{\displaystyle P}
要滿足
P
≥
M
+
N
−
1
{\displaystyle P\geq M+N-1}
。
由於DFT有快速演算法FFT，所以運算量為
O
(
P
log
2
P
)
{\displaystyle O(P\log _{2}P)}
假設
P
{\displaystyle P}
，
f
[
n
]
{\displaystyle f[n]}
個乘法。
方法3：分段卷積（sectioned convolution）[编辑]
概念：將
f
[
n
]
{\displaystyle f[n]}
的區段（
L
>
M
{\displaystyle L>M}
），假設共切成S段：
f
[
n
]
(
n
=
0
,
1
,
.
.
.
,
N
−
1
)
→
f
1
[
n
]
,
f
2
[
n
]
,
f
3
[
n
]
,
.
.
.
,
f
S
[
n
]
(
S
=
⌈
N
L
⌉
)
{\displaystyle 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 )}
\to f_{1}[n],f_{2}[n],f_{3}[n],...,f_{S}[n](S=\left\lceil {\frac {N}{L}}\right\rceil )](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b2758eba65ad177619e0d9198cc913abf649b9a)
Section 1:
f
1
[
n
]
=
f
[
n
]
,
n
=
0
,
1
,
.
.
.
,
L
−
1
{\displaystyle f_{1}[n]=f[n],n=0,1,...,L-1}
![f_{1}[n]=f[n],n=0,1,...,L-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/22401ad12747eb80e3ec79d0c5b189b3c186d912)
Section 2:
f
2
[
n
]
=
f
[
n
+
L
]
,
n
=
0
,
1
,
.
.
.
,
L
−
1
{\displaystyle f_{2}[n]=f[n+L],n=0,1,...,L-1}
![f_{2}[n]=f[n+L],n=0,1,...,L-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/ccb4f0b33490a5fc67f57cb6d353087f35c3db5d)
⋮
{\displaystyle \vdots }
Section r:
f
r
[
n
]
=
f
[
n
+
(
r
−
1
)
L
]
,
n
=
0
,
1
,
.
.
.
,
L
−
1
{\displaystyle f_{r}[n]=f[n+(r-1)L],n=0,1,...,L-1}
![f_{r}[n]=f[n+(r-1)L],n=0,1,...,L-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0d987ef3bab08edc0d97642435c8f97a1383304)
⋮
{\displaystyle \vdots }
![f_{S}[n]=f[n+(S-1)L],n=0,1,...,L-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/b30b353213c930583b0b65c5598ea334fdfee777)
，
f
[
n
]
{\displaystyle f[n]}
![{\displaystyle f[n]=\sum _{r=1}^{S}f_{r}[n+(r-1)L]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ad8dbc7f1039ba3824c87225b58895e27a85453)
。
因此，
y
[
n
]
=
f
[
n
]
∗
g
[
n
]
=
∑
r
=
1
S
∑
m
=
0
M
−
1
f
r
[
n
+
(
r
−
1
)
L
−
m
]
g
[
m
]
{\displaystyle y[n]=f[n]*g[n]=\sum _{r=1}^{S}\sum _{m=0}^{M-1}f_{r}[n+(r-1)L-m]g[m]}
![{\displaystyle y[n]=f[n]*g[n]=\sum _{r=1}^{S}\sum _{m=0}^{M-1}f_{r}[n+(r-1)L-m]g[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e15254f6bff4b4db4f6899f0bb3e450f75e3625d)
，
每一小段作卷積則是採用方法2，先將時域信號轉到頻域相乘，再轉回時域：
y
[
n
]
=
I
D
F
T
(
∑
r
=
1
S
∑
m
=
0
M
−
1
D
F
T
P
(
f
r
[
n
+
(
r
−
1
)
L
−
m
]
)
D
F
T
P
(
g
[
m
]
)
)
,
P
≥
M
+
L
−
1
{\displaystyle 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\geq M+L-1}
![{\displaystyle 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\geq M+L-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3c1ccb338a07511f8c82bbe1478beb62fafdea6)
。
總共只需要做
P
{\displaystyle P}
次，因為
g
[
n
]
{\displaystyle g[n]}
個乘法。
運算量：
N
L
3
(
L
+
M
−
1
)
[
log
2
(
L
+
M
−
1
)
+
1
]
{\displaystyle {\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}
![{\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4b5d72adc35b450cfcc40c0d13720fa6d6bd070)
運算複雜度：
O
(
N
)
{\displaystyle O(N)}
，和
N
{\displaystyle N}
呈線性，較方法2小。
分為 Overlap-Add 和 Overlap-Save 兩種方法。
![{\displaystyle x[n]*h[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c97358d336f2e21de7913bc46fac6477eef3bc6)
的分段卷積分，
x
[
n
]
{\displaystyle x[n]}
![{\displaystyle x[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/864cbbefbdcb55af4d9390911de1bf70167c4a3d)
長度為
N
{\displaystyle N}
![h[n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/89981bbbb05ffd469eeadb828c18359965985e46)
長度為
M
{\displaystyle M}
個零，變成長度
L
+
M
−
1
{\displaystyle L+M-1}
個零，變成長度
L
+
M
−
1
{\displaystyle L+M-1}
![{\displaystyle h'[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7af9a0c1d0c9753adba0e2e13fc2c45e8d5698f7)
![{\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71884e63653a1501f77c376b182141bd9d8e86ce)
，每小段會得到長度
L
+
M
−
1
{\displaystyle L+M-1}
個小段的起點在位置
L
×
i
{\displaystyle L\times i}
上,
i
=
0
,
1
,
.
.
.
,
⌈
N
L
⌉
−
1
{\displaystyle i=0,1,...,\lceil {\frac {N}{L}}\rceil -1}
![{\displaystyle x[n]=[1,2,3,4,5,-1,-2,-3,-4,-5,1,2,3,4,5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98580fd364a838db6ecc3c27068105c31f81d9a9)
, 長度
N
=
15
{\displaystyle N=15}
![{\displaystyle h[n]=[1,2,3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67fdc55efaef23389bacd0b58cf59865377f46f4)
, 長度
M
=
3
{\displaystyle M=3}
![{\displaystyle x_{0}[n],x_{1}[n],x_{2}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d11383cb60875adb6faaedbf729e5956982bff0)
, 每段填
M
−
1
{\displaystyle M-1}
，第二段的範圍是
5
∼
11
{\displaystyle 5\thicksim 11}
，第三段的範圍是
10
∼
16
{\displaystyle 10\thicksim 16}
，三段的範圍是有重疊的
, 從新的
x
[
n
]
{\displaystyle x[n]}
取到
L
×
(
i
+
1
)
−
(
M
−
1
)
×
i
−
1
{\displaystyle L\times (i+1)-(M-1)\times i-1}
總共
L
{\displaystyle L}
個零，變成長度
L
{\displaystyle L}
![{\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c639c720d3a6a4922220ac66a9c31d6e8eb7987)
，每小段會得到長度
L
{\displaystyle L}
點，因此得名 Overlap-Save
![{\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f54af19067aacc4ba29d8c5a4e661d92c3f2ab24)
, 長度
N
=
15
{\displaystyle N=15}
，第二段的範圍是
5
∼
9
{\displaystyle 5\thicksim 9}
，第三段的範圍是
10
∼
14
{\displaystyle 10\thicksim 14}
，第四段的範圍是
15
∼
16
{\displaystyle 15\thicksim 16}
，四段的範圍是沒有重疊的![{\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/197c03fad73159099a753aa21015d7a410c619ba)
, 長度
L
=
10
{\displaystyle L=10}
，
![{\displaystyle h[n]=[1,2,3,4,5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01382de68d6838f4a938ab33a5ad465fa1ae6d0f)
, 長度
M
=
5
{\displaystyle M=5}
,
軸，而兩條藍線之間代表長度
L
{\displaystyle L}
![{\displaystyle h[0],h[6],h[7],h[8],h[9]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c2e1f7ce57e74223a3049d5d803bd8af91b8019)
和
x
[
0
]
,
x
[
6
]
,
x
[
7
]
,
x
[
8
]
,
x
[
9
]
{\displaystyle x[0],x[6],x[7],x[8],x[9]}
![{\displaystyle x[0],x[6],x[7],x[8],x[9]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f004d095726b6a642d26dd6dc4bef9660ec8c17)
內積的值，
![{\displaystyle h[6],h[7],h[8],h[9]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ccee59494bedbceae16aa4bce150fbcef8b2cf1)
這
M
−
1
{\displaystyle M-1}
![{\displaystyle h[-n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2160e2740fe612954bc0c6d78203d595d29076e3)
M
−
1
{\displaystyle M-1}
）分成5類，並列出適合使用的方法：
- 分段卷积
M
≈
N
{\displaystyle M\approx N}
- 快速傅里叶变换
M
≫
N
{\displaystyle M\gg N}
- 分段卷积
N
{\displaystyle N}
，適合用哪種方法計算卷積?
方法2：
P
≥
M
+
N
−
1
=
2016
{\displaystyle P\geq M+N-1=2016}
，而2016點的DFT最少乘法數
a
=
12728
{\displaystyle a=12728}
，所以總乘法量為
3
(
a
+
P
)
=
44232
{\displaystyle 3(a+P)=44232}
方法3：
若切成8塊（
S
=
8
{\displaystyle S=8}
），則
L
=
250
,
P
≥
M
+
L
−
1
=
266
{\displaystyle L=250,P\geq M+L-1=266}
。選
P
=
288
{\displaystyle P=288}
，則總乘法量為
(
2
S
+
1
)
a
+
3
S
P
=
26632
{\displaystyle (2S+1)a+3SP=26632}
，比方法1和2少了很多。
但是若要找到最少的乘法量，必須依照以下步驟
(1)先找出
L
{\displaystyle L}
![{\frac {\partial {{\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}}{\partial L}}=0](https://wikimedia.org/api/rest_v1/media/math/render/svg/5212be896bcbc7febbe5e992d9650c2b0ea09c6a)
(2)由
P
≥
L
+
M
−
1
{\displaystyle P\geq L+M-1}
算出點數在
P
{\displaystyle P}
算出
L
o
p
t
{\displaystyle L_{opt}}
因此，
(1)由運算量對
L
{\displaystyle L}
(2)
P
≥
L
+
M
−
1
=
101
{\displaystyle P\geq L+M-1=101}
，所以選擇101點DFT附近點數乘法量最少的點數
P
=
96
{\displaystyle P=96}
或
P
=
120
{\displaystyle P=120}
。
(3-1)當
P
=
96
→
a
=
280
,
L
=
P
+
1
−
M
=
80
→
S
=
25
{\displaystyle P=96\to a=280,L=P+1-M=80\to S=25}
，總乘法量為
(
2
S
+
1
)
a
+
3
S
P
=
21480
{\displaystyle (2S+1)a+3SP=21480}
。
(3-2)當
P
=
120
→
a
=
380
,
L
=
P
+
1
−
M
=
104
→
S
=
20
{\displaystyle P=120\to a=380,L=P+1-M=104\to S=20}
，總乘法量為
(
2
S
+
1
)
a
+
3
S
P
=
22780
{\displaystyle (2S+1)a+3SP=22780}
。
由此可知，切成20塊會有較好的效率，而所需總乘法量為21480。
因此，當
N
=
2000
,
M
=
17
{\displaystyle N=2000,M=17}
，選擇1026點DFT附近點數乘法量最少的點數，
→
P
=
1152
,
a
=
7088
{\displaystyle \to P=1152,a=7088}
。
因此，所需乘法量為
3
(
a
+
P
)
=
24342
{\displaystyle 3(a+P)=24342}
方法3：
(1)由運算量對
L
{\displaystyle L}
，所以選擇7點DFT附近點數乘法量最少的點數
P
=
8
{\displaystyle P=8}
或
P
=
6
{\displaystyle P=6}
或
P
=
4
{\displaystyle P=4}
。
(3-1)當
P
=
8
→
a
=
4
,
L
=
P
+
1
−
M
=
6
→
S
=
171
{\displaystyle P=8\to a=4,L=P+1-M=6\to S=171}
，總乘法量為
(
2
S
+
1
)
a
+
3
S
P
=
5476
{\displaystyle (2S+1)a+3SP=5476}
。
(3-2)當
P
=
6
→
a
=
4
,
L
=
P
+
1
−
M
=
4
→
S
=
256
{\displaystyle P=6\to a=4,L=P+1-M=4\to S=256}
，總乘法量為
(
2
S
+
1
)
a
+
3
S
P
=
6660
{\displaystyle (2S+1)a+3SP=6660}
。
(3-3)當
P
=
4
→
a
=
0
,
L
=
P
+
1
−
M
=
2
→
S
=
512
{\displaystyle P=4\to a=0,L=P+1-M=2\to S=512}
，總乘法量為
(
2
S
+
1
)
a
+
3
S
P
=
6144
{\displaystyle (2S+1)a+3SP=6144}
。
由此可知，切成171塊會有較好的效率，而所需總乘法量為5476。
因此，當
N
=
1024
,
M
=
3
{\displaystyle N=1024,M=3}
，所需總乘法量：分段卷積
1
=
1623
{\displaystyle P\geq M+N-1=1623}
，選擇1026點DFT附近點數乘法量最少的點數，
→
P
=
2016
,
a
=
12728
{\displaystyle \to P=2016,a=12728}
。
因此，所需乘法量為
3
(
a
+
P
)
=
44232
{\displaystyle 3(a+P)=44232}
(2)
P
≥
L
+
M
−
1
=
1623
{\displaystyle P\geq L+M-1=1623}
，所以選擇1623點DFT附近點數乘法量最少的點數
P
=
2016
{\displaystyle P=2016}
。
(3)當
P
=
2016
→
a
=
12728
,
L
=
P
+
1
−
M
=
1417
→
S
=
1
{\displaystyle P=2016\to a=12728,L=P+1-M=1417\to S=1}
，總乘法量為
(
2
S
+
1
)
a
+
3
S
P
=
44232
{\displaystyle (2S+1)a+3SP=44232}
。
由此可知，此時切成一段，就跟方法2一樣，所需總乘法量為44232。
因此，當
N
=
1024
,
M
=
600
{\displaystyle N=1024,M=600}
，所需總乘法量：快速傅立葉轉換 = 分段卷積
,
t
n
)
=
∫
∫
⋯
∫
f
(
τ
1
,
τ
2
,
⋯
,
τ
n
)
g
(
t
1
−
τ
1
,
t
2
−
τ
2
,
⋯
,
t
n
−
τ
n
,
)
d
τ
1
d
τ
2
⋯
d
τ
n
{\displaystyle (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
∗
h
)
=
(
f
∗
g
)
∗
h
{\displaystyle f*(g*h)=(f*g)*h\,}
分配律
f
∗
(
g
+
h
)
=
(
f
∗
g
)
+
(
f
∗
h
)
{\displaystyle f*(g+h)=(f*g)+(f*h)\,}
数乘结合律
a
(
f
∗
g
)
=
(
a
f
)
∗
g
=
f
∗
(
a
g
)
{\displaystyle a(f*g)=(af)*g=f*(ag)\,}
后向差分：
D
−
f
(
n
)
=
f
(
n
)
−
f
(
n
−
1
)
{\displaystyle {\mathcal {D}}^{-}f(n)=f(n)-f(n-1)}
卷积定理[编辑]
表示f的傅里叶变换。
的序列，按照卷积的定义进行计算，需要做
2
n
−
1
{\displaystyle 2n-1}
组对位乘法，其计算复杂度为
O
(
n
2
)
{\displaystyle {\mathcal {O}}(n^{2})}
；而利用傅里叶变换将序列变换到频域上后，只需要一组对位乘法，利用傅里叶变换的快速算法之后，总的计算复杂度为
O
(
n
log
n
)
{\displaystyle {\mathcal {O}}(n\log n)}
。这一结果可以在快速乘法计算中得到应用。
【本文地址】
今日新闻 |
推荐新闻 |