# 卷积

## 定义

${\displaystyle (f*g)(t)\triangleq \int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,\mathrm {d} \tau }$

${\displaystyle (f*g)(t)}$仍为可积函数，并且有着：

${\displaystyle (f*g)(t)\triangleq \int _{-\infty }^{\infty }f(t-\tau )g(\tau )\,d\tau =(g*f)(t)}$

${\displaystyle (f*g)(t)=\int _{0}^{t}f(\tau )g(t-\tau )\,d\tau \quad }$对于${\displaystyle \ f,g:[0,\infty )\to \mathbb {R} }$

{\displaystyle {\begin{aligned}(f*g)(t_{1},t_{2},\cdots ,t_{n})&\triangleq \int \int \cdots \int _{\mathbb {R} ^{n}}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}\\&\triangleq \int _{\mathbb {R} ^{n}}f(\tau )g(t-\tau )\,d^{n}\tau \end{aligned}}}

${\displaystyle f(t)*g(t)\triangleq \underbrace {\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau } _{(f*g)(t)}}$

## 历史

“卷积”这个术语早在1903年就出现了，然而其定义在早期使用中是相当生僻的[6][7]，直到1950年代或1960年代之前都未曾广泛使用。

## 简介

${\displaystyle \|{f}*g\|_{p}\leq \|f\|_{1}\|g\|_{p}}$

${\displaystyle p=1}$的特殊情况下，这显示出${\displaystyle L^{1}}$是在卷积下的巴拿赫代数（并且如果${\displaystyle f}$${\displaystyle g}$几乎处处非负则两边间等式成立）。

${\displaystyle (f\star g)(\tau )\triangleq \int _{-\infty }^{\infty }{\overline {f(t-\tau )}}g(t)\,dt={\overline {f(-\tau )}}*g(\tau )}$

${\displaystyle (\delta *h)(t)=\int _{-\infty }^{\infty }\delta (\tau )h(t-\tau )\,d\tau =h(t)}$

${\displaystyle y(t)=(x*h)(t)\ \triangleq \ \int \limits _{-\infty }^{\infty }x(t-\tau )\cdot h(\tau )\,\mathrm {d} \tau =\int \limits _{-\infty }^{\infty }x(\tau )\cdot h(t-\tau )\,\mathrm {d} \tau }$

${\displaystyle f_{U+V}(x)=\int _{-\infty }^{\infty }f_{U}(y)f_{V}(x-y)\,dy=\left(f_{U}*f_{V}\right)(x)}$

## 图解

 已知右侧第一行图中两个函数${\displaystyle f(t)}$和${\displaystyle g(t)}$。 首先將兩個函數都用约束变量${\displaystyle \tau }$來表示，并将${\displaystyle g(\tau )}$翻转至纵轴另一侧，从而得到右侧第二行图中${\displaystyle f(\tau )}$和${\displaystyle g(-\tau )}$。 向函数${\displaystyle g(-\tau )}$增加一个时间偏移量${\displaystyle t}$，得到函数${\displaystyle g(-(\tau -t))=g(t-\tau )}$。${\displaystyle t}$不是常数而是自由变量，当${\displaystyle t}$取不同值时，${\displaystyle g(t-\tau )}$能沿着${\displaystyle \tau }$轴“滑动”。如果${\displaystyle t}$是正值，则${\displaystyle g(t-\tau )}$等于${\displaystyle g(-\tau )}$沿着${\displaystyle \tau }$轴向右（朝向${\displaystyle +\infty }$）滑动数量${\displaystyle t}$。如果${\displaystyle t}$是负值，则${\displaystyle g(t-\tau )}$等价于${\displaystyle g(-\tau )}$向左（朝向${\displaystyle -\infty }$）滑动数量${\displaystyle |t|}$。 讓${\displaystyle t}$從${\displaystyle -\infty }$变化至${\displaystyle +\infty }$，当兩個函數交會時，計算交會範圍中兩個函數乘積的積分值。換句話說，在时间${\displaystyle t}$，计算函数${\displaystyle f(\tau )}$经过权重函数${\displaystyle g(t-\tau )}$施以权重后其下的面积。右侧第三、第四和第五行图中，分别是${\displaystyle t=0}$、${\displaystyle t=2.5}$和${\displaystyle t=5.5}$时的情况，从${\displaystyle t>1}$时开始有交会，例如在第四行图中，${\displaystyle \tau =0}$则${\displaystyle g(t-\tau )=g(2.5)}$，${\displaystyle \tau =1.5}$则${\displaystyle g(t-\tau )=g(1)}$，对于${\displaystyle \tau \notin [0,1.5]}$有着${\displaystyle f(\tau )g(t-\tau )=0}$。 最後得到的波形（未包含在此圖中）就是${\displaystyle f}$和${\displaystyle g}$的捲積。 两个矩形脈衝波的捲積。其中函数${\displaystyle g}$首先对${\displaystyle \tau =0}$反射，接著平移${\displaystyle t}$，成為${\displaystyle g(t-\tau )}$。那么重叠部份的面积就相当于${\displaystyle t}$处的卷积，其中橫坐標代表待变量${\displaystyle \tau }$以及新函數${\displaystyle f\ast g}$的自變量${\displaystyle t}$。 矩形脈衝波和指數衰減脈衝波的捲積（後者可能出現於RC電路中），同樣地重疊部份面積就相當於${\displaystyle t}$處的捲積。注意到因為${\displaystyle g}$是對稱的，所以在這兩張圖中，反射並不會改變它的形狀。

## 周期卷积

${\displaystyle \int _{t_{0}}^{t_{0}+T}h_{_{T}}(\tau )x_{_{T}}(t-\tau )\,d\tau }$

${\displaystyle s_{_{P}}(t)\triangleq \sum _{m=-\infty }^{\infty }s(t+mP)=\sum _{m=-\infty }^{\infty }s(t-mP),\quad m\in \mathbb {Z} }$

${\displaystyle (h*x_{_{T}})(t)\ \triangleq \ \ \int _{-\infty }^{\infty }h(\tau )x_{_{T}}(t-\tau )\,d\tau \ =\ \int _{t_{0}}^{t_{0}+T}h_{_{T}}(\tau )x_{_{T}}(t-\tau )\,d\tau }$
${\displaystyle (h*x_{_{T}})(t)=(x*h_{_{T}})(t)}$

${\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} }$

${\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )x((t-\tau )_{\mathrm {mod} \ T})\ d\tau }$

## 离散卷积

${\displaystyle (f*g)[n]\ \ \triangleq \ \sum _{m=-\infty }^{\infty }{f[m]g[n-m]}=\sum _{m=-\infty }^{\infty }f[n-m]\,g[m]}$

${\displaystyle g[n]}$支撐集為有限長度的${\displaystyle \{-M,-M+1,\dots ,M-1,M\}}$之时，上式會變成有限求和

${\displaystyle (f*g)[n]=\sum _{m=-M}^{M}f[n-m]g[m]}$

### 多维离散卷积

${\displaystyle y(n_{1},n_{2},...,n_{_{M}})=h(n_{1},n_{2},...,n_{_{M}})*{\overset {M}{\cdots }}*x(n_{1},n_{2},...,n_{_{M}})}$

${\displaystyle \sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }...\sum _{k_{_{M}}=-\infty }^{\infty }h(k_{1},k_{2},...,k_{_{M}})x(n_{1}-k_{1},n_{2}-k_{2},...,n_{_{M}}-k_{_{M}})}$

### 离散周期卷积

${\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}\ =\ \sum _{m=0}^{N-1}\left(\sum _{k=-\infty }^{\infty }{h}[m-kN]\right)x_{_{N}}[n-m]}$

${\displaystyle (h*x_{_{N}})[n]=\sum _{m=0}^{N-1}h[m]x_{_{N}}[n-m]=\sum _{m=0}^{N-1}h[m]x[(n-m)_{\bmod {N}}]}$

${\displaystyle {\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{_{N-1}}\end{bmatrix}}={\begin{bmatrix}h_{0}&h_{_{N-1}}&\cdots &h_{1}\\h_{1}&h_{0}&\cdots &h_{2}\\\vdots &\vdots &\ddots &\vdots \\h_{_{N-1}}&h_{_{N-2}}&\cdots &h_{0}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\\vdots \\x_{_{N-1}}\end{bmatrix}}}$

## 性质

### 代数

${\displaystyle f*g=g*f\,}$

${\displaystyle f*(g*h)=(f*g)*h\,}$

${\displaystyle f*(g+h)=(f*g)+(f*h)\,}$

${\displaystyle a(f*g)=(af)*g=f*(ag)\,}$

${\displaystyle {\overline {f*g}}={\overline {f}}*{\overline {g}}}$

${\displaystyle (f*g)'=f'*g=f*g'}$

${\displaystyle (F*g)(t)=(f*G)(t)=\int _{-\infty }^{t}(f*g)(\tau )\,d\tau }$

### 积分

${\displaystyle \int _{\mathbb {R} ^{n}}(f*g)(t)\,d^{n}t=\left(\int _{\mathbb {R} ^{n}}f(t)\,d^{n}t\right)\left(\int _{\mathbb {R} ^{n}}g(t)\,d^{n}t\right)}$

### 微分

${\displaystyle {\frac {d}{dt}}(f*g)={\frac {df}{dt}}*g=f*{\frac {dg}{dt}}}$

${\displaystyle {\frac {\partial }{\partial t_{i}}}(f*g)={\frac {\partial f}{\partial t_{i}}}*g=f*{\frac {\partial g}{\partial t_{i}}}}$

${\displaystyle \Delta (f*g)=(\Delta f)*g=f*(\Delta g)}$

## 卷积定理

{\displaystyle {\begin{aligned}G(s)&\triangleq {\mathcal {F}}\{g\}(s)=\int _{-\infty }^{\infty }g(x)e^{-i2\pi sx}\,dx,\quad s\in \mathbb {R} \\H(s)&\triangleq {\mathcal {F}}\{h\}(s)=\int _{-\infty }^{\infty }h(x)e^{-i2\pi sx}\,dx,\quad s\in \mathbb {R} \end{aligned}}}

${\displaystyle {\mathcal {F}}\{g*h\}(s)=G(s)H(s),\quad s\in \mathbb {R} }$
${\displaystyle {\mathcal {F}}\{g\cdot h\}(s)=G(s)*H(s),\quad s\in \mathbb {R} }$

${\displaystyle (g*h)(s)={\mathcal {F}}^{-1}\{G\cdot H\},\quad s\in \mathbb {R} }$
${\displaystyle (g\cdot h)(s)={\mathcal {F}}^{-1}\{G*H\},\quad s\in \mathbb {R} }$

### 周期卷积

{\displaystyle {\begin{aligned}g_{_{P}}(x)\ &\triangleq \sum _{m=-\infty }^{\infty }g(x-mP),\quad m\in \mathbb {Z} \\h_{_{P}}(x)\ &\triangleq \sum _{m=-\infty }^{\infty }h(x-mP),\quad m\in \mathbb {Z} \end{aligned}}}

{\displaystyle {\begin{aligned}G[k]&\triangleq {\mathcal {F}}\{g_{_{P}}\}[k]={\frac {1}{P}}\int _{P}g_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \\H[k]&\triangleq {\mathcal {F}}\{h_{_{P}}\}[k]={\frac {1}{P}}\int _{P}h_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \end{aligned}}}

${\displaystyle {\mathcal {F}}\{g_{_{P}}\cdot h_{_{P}}\}[k]=(G*H)[k]}$

${\displaystyle {\mathcal {F}}\{g_{_{P}}*h\}[k]=\ P\cdot G[k]\ H[k]}$

### 离散卷积

{\displaystyle {\begin{aligned}G(s)&\triangleq {\mathcal {F}}\{g\}(s)=\sum _{n=-\infty }^{\infty }g[n]\cdot e^{-i2\pi sn}\;,\quad s\in \mathbb {R} \\H(s)&\triangleq {\mathcal {F}}\{h\}(s)=\sum _{n=-\infty }^{\infty }h[n]\cdot e^{-i2\pi sn}\;,\quad s\in \mathbb {R} \end{aligned}}}

${\displaystyle {\mathcal {F}}\{g*h\}(s)=\ G(s)H(s)}$

### 离散周期卷积

{\displaystyle {\begin{aligned}g_{_{N}}[n]\ &\triangleq \sum _{m=-\infty }^{\infty }g[n-mN],\quad m,n\in \mathbb {Z} \\h_{_{N}}[n]\ &\triangleq \sum _{m=-\infty }^{\infty }h[n-mN],\quad m,n\in \mathbb {Z} \end{aligned}}}

${\displaystyle {\mathcal {F}}\{g_{_{N}}*h\}[k]=\ \underbrace {{\mathcal {F}}\{g_{_{N}}\}[k]} _{G(k/N)}\cdot \underbrace {{\mathcal {F}}\{h_{_{N}}\}[k]} _{H(k/N)},\quad k,n\in \mathbb {Z} }$

${\displaystyle (g_{_{N}}*h)[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{g_{_{N}}\}\cdot {\mathcal {F}}\{h_{_{N}}\}\}}$

${\displaystyle (g_{_{N}}*h)[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{g\}\cdot {\mathcal {F}}\{h\}\}}$

## 推广

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

${\displaystyle (f*g)(x)=\int _{G}f(y)g(xy^{-1})\,dm(y)\,}$

## 离散卷積的計算方法

1. 直接計算（Direct Method）
2. 快速傅立葉轉換（FFT）
3. 分段卷積（sectioned convolution）

### 方法1：直接計算

• 作法：利用卷積的定義
${\displaystyle y[n]=f[n]*g[n]=\sum _{m=0}^{M-1}f[n-m]g[m]}$
• ${\displaystyle f[n]}$${\displaystyle g[n]}$皆為實數信號，則需要${\displaystyle MN}$個乘法。
• ${\displaystyle f[n]}$${\displaystyle g[n]}$皆為更一般性的複數信號，不使用複數乘法的快速演算法，會需要${\displaystyle 4MN}$個乘法;但若使用複數乘法的快速演算法，則可簡化至${\displaystyle 3MN}$個乘法。

### 方法2：快速傅立葉轉換

• 概念：由於兩個離散信號在時域（time domain）做卷積相當於這兩個信號的離散傅立葉轉換在頻域（frequency domain）做相乘：
${\displaystyle y[n]=f[n]*g[n]\leftrightarrow Y[f]=F[f]G[f]}$
，可以看出在頻域的計算較簡單。
• 作法：因此這個方法即是先將信號從時域轉成頻域：
${\displaystyle F[f]=DFT_{P}(f[n]),G[f]=DFT_{P}(g[n])}$
，於是
${\displaystyle Y[f]=DFT_{P}(f[n])DFT_{P}(g[n])}$
，最後再將頻域信號轉回時域，就完成了卷積的計算：
${\displaystyle y[n]=IDFT_{P}{DFT_{P}(f[n])DFT_{P}(g[n])}}$

• 特別注意DFT和IDFT的點數${\displaystyle P}$要滿足${\displaystyle P\geq M+N-1}$
• 由於DFT有快速演算法FFT，所以運算量為${\displaystyle O(P\log _{2}P)}$
• 假設${\displaystyle P}$點DFT的乘法量為${\displaystyle a}$${\displaystyle f[n]}$${\displaystyle g[n]}$為一般性的複數信號，並使用複數乘法的快速演算法，則共需要${\displaystyle 3a+3P}$個乘法。

### 方法3：分段卷積

• 概念：將${\displaystyle f[n]}$切成好幾段（section），每一段分別和${\displaystyle g[n]}$做卷積後，再將結果相加。
• 作法：先將${\displaystyle f[n]}$切成每段長度為${\displaystyle L}$的區段（${\displaystyle L>M}$），假設共切成S段：
${\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: ${\displaystyle f_{1}[n]=f[n],n=0,1,...,L-1}$
Section 2: ${\displaystyle f_{2}[n]=f[n+L],n=0,1,...,L-1}$
${\displaystyle \vdots }$
Section r: ${\displaystyle f_{r}[n]=f[n+(r-1)L],n=0,1,...,L-1}$
${\displaystyle \vdots }$
Section S: ${\displaystyle f_{S}[n]=f[n+(S-1)L],n=0,1,...,L-1}$
${\displaystyle f[n]}$為各個section的和
${\displaystyle f[n]=\sum _{r=1}^{S}f_{r}[n+(r-1)L]}$

${\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]=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 P}$點FFT ${\displaystyle 2S+1}$次，因為${\displaystyle g[n]}$只需要做一次FFT。
• 假設${\displaystyle P}$點DFT的乘法量為${\displaystyle a}$${\displaystyle f[n]}$${\displaystyle g[n]}$為一般性的複數信號，並使用複數乘法的快速演算法，則共需要${\displaystyle (2S+1)a+3SP}$個乘法。
• 運算量：${\displaystyle {\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}$
• 運算複雜度：${\displaystyle O(N)}$，和${\displaystyle N}$呈線性，較方法2小。
• 分為 Overlap-Add 和 Overlap-Save 兩種方法。

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

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

Step 3: 把 ${\displaystyle h[n]}$ 添加 ${\displaystyle L-1}$個零，變成長度 ${\displaystyle L+M-1}$${\displaystyle h'[n]}$

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

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

Step 6: 會發現在每一段的後面 ${\displaystyle M-1}$ 點有重疊，將所有點都相加起來，顧名思義 Overlap-Add，最後得到結果

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

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

${\displaystyle L=5}$

${\displaystyle L=5}$ 切成三段，分別為 ${\displaystyle x_{0}[n],x_{1}[n],x_{2}[n]}$, 每段填 ${\displaystyle M-1}$ 個零，並將 ${\displaystyle h[n]}$ 填零至長度 ${\displaystyle L+M-1}$

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

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

Step 3: 把 ${\displaystyle h[n]}$ 添加 ${\displaystyle L-M}$ 個零，變成長度 ${\displaystyle L}$${\displaystyle h'[n]}$

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

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

Step 6: 將所有保留的點合再一起，得到最後結果

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

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

${\displaystyle L=7}$

${\displaystyle x[n]}$ 前面填 ${\displaystyle M-1}$ 個零以後，按照 Step 2 的方式分段，可以看到每一段都重複上一段的 ${\displaystyle M-1}$

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

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

### 應用時機

1. ${\displaystyle M}$為一非常小的整數 - 直接計算
2. ${\displaystyle M\ll N}$ - 分段卷积
3. ${\displaystyle M\approx N}$ - 快速傅里叶变换
4. ${\displaystyle M\gg N}$ - 分段卷积
5. ${\displaystyle N}$為一非常小的整數 - 直接計算

### 例子

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

Ans：

(1)先找出${\displaystyle L}$:解${\displaystyle L}$ : ${\displaystyle {\frac {\partial {{\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}}{\partial L}}=0}$
(2)由${\displaystyle P\geq L+M-1}$算出點數在${\displaystyle P}$附近的DFT所需最少的乘法量，選擇DFT的點數
(3)最後由${\displaystyle L=P+1-M}$算出${\displaystyle L_{opt}}$

(1)由運算量對${\displaystyle L}$的偏微分為0而求出${\displaystyle L=85}$
(2)${\displaystyle P\geq L+M-1=101}$，所以選擇101點DFT附近點數乘法量最少的點數${\displaystyle P=96}$${\displaystyle P=120}$
(3-1)當${\displaystyle P=96\to a=280,L=P+1-M=80\to S=25}$，總乘法量為${\displaystyle (2S+1)a+3SP=21480}$
(3-2)當${\displaystyle P=120\to a=380,L=P+1-M=104\to S=20}$，總乘法量為${\displaystyle (2S+1)a+3SP=22780}$

• 因此，當${\displaystyle N=2000,M=17}$，所需總乘法量：分段卷積<快速傅立葉轉換<直接計算。故，此時選擇使用分段卷積來計算卷積最適合。

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

Ans：

(1)由運算量對${\displaystyle L}$的偏微分為0而求出${\displaystyle L=5}$
(2)${\displaystyle P\geq L+M-1=7}$，所以選擇7點DFT附近點數乘法量最少的點數${\displaystyle P=8}$${\displaystyle P=6}$${\displaystyle P=4}$
(3-1)當${\displaystyle P=8\to a=4,L=P+1-M=6\to S=171}$，總乘法量為${\displaystyle (2S+1)a+3SP=5476}$
(3-2)當${\displaystyle P=6\to a=4,L=P+1-M=4\to S=256}$，總乘法量為${\displaystyle (2S+1)a+3SP=6660}$
(3-3)當${\displaystyle P=4\to a=0,L=P+1-M=2\to S=512}$，總乘法量為${\displaystyle (2S+1)a+3SP=6144}$

• 因此，當${\displaystyle N=1024,M=3}$，所需總乘法量：分段卷積<直接計算<快速傅立葉轉換。故，此時選擇使用分段卷積來計算卷積最適合。
• 雖然當${\displaystyle M}$是個很小的正整數時，大致上適合使用直接計算。但實際上還是將3個方法所需的乘法量都算出來，才能知道用哪種方法可以達到最高的效率。

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

Ans：

(1)由運算量對${\displaystyle L}$的偏微分為0而求出${\displaystyle L=1024}$
(2)${\displaystyle P\geq L+M-1=1623}$，所以選擇1623點DFT附近點數乘法量最少的點數${\displaystyle P=2016}$
(3)當${\displaystyle P=2016\to a=12728,L=P+1-M=1417\to S=1}$，總乘法量為${\displaystyle (2S+1)a+3SP=44232}$

• 因此，當${\displaystyle N=1024,M=600}$，所需總乘法量：快速傅立葉轉換 = 分段卷積<直接計算。故，此時選擇使用分段卷積來計算卷積最適合。

## 引用

1. ^ Smith, Stephen W. 13.Convolution. The Scientist and Engineer's Guide to Digital Signal Processing 1. California Technical Publishing. 1997 [22 April 2016]. ISBN 0-9660176-3-3. （原始内容存档于2023-06-26）.
2. ^ Irwin, J. David. 4.3. The Industrial Electronics Handbook 1. Boca Raton, FL: CRC Press. 1997: 75. ISBN 0-8493-8343-9.
3. ^ Dominguez-Torres, p 2
4. ^ on page 505 of his book entitled Treatise on differences and series, which is the last of 3 volumes of the encyclopedic series: Traité du calcul différentiel et du calcul intégral, Chez Courcier, Paris, 1797–1800. Dominguez-Torres, p 4
5. ^ R. N. Bracewell, Early work on imaging theory in radio astronomy, W. T. Sullivan (编), The Early Years of Radio Astronomy: Reflections Fifty Years After Jansky's Discovery, Cambridge University Press: 172, 2005, ISBN 978-0-521-61602-7
6. ^ John Hilton Grace and Alfred Young, The algebra of invariants, Cambridge University Press: 40, 1903
7. ^ Leonard Eugene Dickson, Algebraic invariants, J. Wiley: 85, 1914
8. ^ Stein & Weiss 1971，Theorem 1.3）
9. ^ Crutchfield, Steve, The Joy of Convolution, Johns Hopkins University, October 12, 2010 [November 21, 2010], （原始内容存档于2013-09-11）
10. ^ Jeruchim, Michel C.; Balaban, Philip; Shanmugan, K. Sam. Simulation of Communication Systems: Modeling, Methodology and Techniques 2nd. New York: Kluwer Academic Publishers. October 2000: 73–74. ISBN 0-30-646267-2.
11. Udayashankara, V. Real Time Digital Signal Processing. India: Prentice-Hall. June 2010: 189. ISBN 978-8-12-034049-7.
12. ^ Priemer, Roland. Introductory Signal Processing. Advanced Series in Electrical and Computer Engineering 6. Teaneck,N.J.: World Scientific Pub Co Inc. July 1991: 286–289 [2023-10-26]. ISBN 9971-50-919-9. （原始内容存档于2023-10-11）.
13. ^ Damelin & Miller 2011，第219頁
14. ^ Weisstein, Eric W. Convolution. mathworld.wolfram.com. [2021-09-22]. （原始内容存档于2002-01-14） （英语）.
15. ^ Weisstein, Eric W. From MathWorld--A Wolfram Web Resource. [2023-10-23]. （原始内容存档于2000-07-11）.
16. ^ Zhang, Yingjie; Soon, Hong Geok; Ye, Dongsen; Fuh, Jerry Ying Hsi; Zhu, Kunpeng. Powder-Bed Fusion Process Monitoring by Machine Vision With Hybrid Convolutional Neural Networks. IEEE Transactions on Industrial Informatics. September 2020, 16 (9): 5769–5779 [2023-10-24]. ISSN 1941-0050. S2CID 213010088. doi:10.1109/TII.2019.2956078. （原始内容存档于2023-07-31）.
17. ^ Chervyakov, N.I.; Lyakhov, P.A.; Deryabin, M.A.; Nagornov, N.N.; Valueva, M.V.; Valuev, G.V. Residue Number System-Based Solution for Reducing the Hardware Cost of a Convolutional Neural Network. Neurocomputing. September 2020, 407: 439–453 [2023-10-24]. S2CID 219470398. doi:10.1016/j.neucom.2020.04.018. （原始内容存档于2023-06-29） （英语）. Convolutional neural networks represent deep learning architectures that are currently used in a wide range of applications, including computer vision, speech recognition, time series analysis in finance, and many others.
18. ^ Atlas, Homma, and Marks. An Artificial Neural Network for Spatio-Temporal Bipolar Patterns: Application to Phoneme Classification (PDF). Neural Information Processing Systems (NIPS 1987). （原始内容存档 (PDF)于2021-04-14）.