# 6.2 卷積定理

## 核心概念

一句話概括: **一個域的乘積等於在另一個域的卷積**。
所以時域上如果是兩個信號相乘，頻域上兩個信號就是互相卷積的。

以下將這句話展開成四種變換下的樣子。這些式子在[4.5 傅立葉級數的性質](/0kCppWeyRt-XpKVl1THSiw)和[5.4 傅立葉轉換的性質](/gf4iICrzT-KQQ1ZX7kxf3A)都出現過。值得注意的點有兩個:
1. 常數放的位置不一樣。這是因為FS和FT本身的式子對於常數的擺放位置就不同，這裡顯示的公式是照著本書的慣例走，採角頻率、非么正轉換。
2. 在某些部分，式子雖然長得很像卷積，但其積分、求和上下界不是正負無限大之間。

### 時域乘積=頻域卷積
:::danger
令$x\leftrightarrow a_k$，$y\leftrightarrow b_k$:
**CTFS**
$$
x(t)\,y(t)\leftrightarrow\sum_{m=-\infty}^{\infty} a_mb_{k-m}
$$
**DTFS** (假設$x,y$基本週期相同)
$$
x[n]\,y[n]\leftrightarrow\sum_{m=\langle N_0 \rangle} a_mb_{k-m}
$$
令$x\leftrightarrow X(\omega)$，$y\leftrightarrow Y(\omega)$:
**CTFT**
$$
x(t)\,y(t)\leftrightarrow \frac{1}{2\pi} X(\omega)*Y(\omega)
$$
**DTFT**
$$
x[n]\,y[n]\leftrightarrow \frac{1}{2\pi} \int_{2\pi} X(\omega)Y(\theta-\omega) d\theta
$$
:::

### 頻域乘積=時域卷積
:::danger
**CTFS**
$$
\int_{T_0} x(\tau)y(t-\tau)\,d\tau\leftrightarrow T_0a_kb_k
$$
**DTFS** (假設$x,y$基本週期相同)
$$
\sum_{r=\langle N_0 \rangle} x[r]y[n-r] \leftrightarrow N_0a_kb_k
$$
**CTFT**
$$
x(t)*y(t)\leftrightarrow X(\omega)Y(\omega)
$$
**DTFT** $$
x[n]*y[n]\leftrightarrow X(\omega)Y(\omega)
$$
:::

## 它為什麼重要?
很簡單，如果你忘記卷積有多痛苦，可以回想一下[3.2](/L6mx9GInQYqZk95NY4RDNQ)的時候，我們計算了一個看起來超簡單的卷積，結果答案超醜。想像一下，我現在要你手算那些東西，再找那個東西的頻域，你大概會去報復社會。

如果我已經知道兩個簡單東西的頻域，接下來他們乘積的頻域，和卷積的頻域，都可以利用定理簡化，那不是非常美妙嗎?

再來，我們有很多的性質在講，如果我對時域怎樣怎樣，頻域會發生什麼變化。這是非常重要的。假設我在設計一個系統，而我需要在頻域上做一個操作，那麼我得知道它時域上是在幹什麼，我才能去實作這個系統。
反之，我知道這個系統在時域上一通操作，但我看不懂它想幹嘛，有時候我得借助頻域的圖來看懂。而卷積是一個非常基礎的操作: 它是LTI系統的輸出。回想一下，任何LTI系統的輸出都可以寫成輸入和其脈衝響應的卷積:
$$
y=x*h
$$現在我們知道了，對於LTI系統，在頻域上:
$$
Y=XH
$$
其中$H$因為是**頻**域上的脈衝**響應**，所以稱為**頻率響應(frequency response)**。根據上面的式子，我們可以把LTI系統想得更簡單: **對於每個不同頻率的信號而言，系統給出不一樣的增益**(gain)。(p.s. 增益就是對信號乘以一個倍數。) 而每個頻率對應的增益就是頻率響應。我想這會比脈衝響應和卷積來的直觀。

## 它為什麼正確?
我們知道它很厲害，然後呢? 這東西看起來完全不直觀啊。什麼時域卷積=頻域乘積聽起來跟唬爛一樣。這大概就是我第一次看到這些定理時候的想法: 不管了，直接背。考試都會照抄，但心裡面從來沒被說服過。

想說明它為什麼正確，我可以直接丟證明給你，就像我們之前學的那樣。要說到更本質的原因，我也可以直接說因為$\chi(x+y)=\chi(x)\chi(y)$ (WTF?)，這種證明也是附在下面了。但我想講一種更直觀的方式，希望可以說服你。

我們其實學過卷積定理，在國二的時候。我們在[3.2](/L6mx9GInQYqZk95NY4RDNQ)的時候有提到過，**多項式的乘法**是一個卷積。而我們不要把傅立葉轉換想的那麼複雜，其實它就是一個級數展開而已嘛，所以多項式也長得很像不是嗎?
:::info
**CTFS合成公式**
$$
x(t) = \sum_{k=-\infty}^{\infty} a_k e^{jk\omega_0t}\
$$
**多項式**
$$
x(t) = \sum_{k=0}^{\infty} a_k t^k
$$
:::
好，現在考慮以下這個例子: 求$(t^2+t+1)(t-1)$。這大概會是你上大學以來遇到最白癡的課本習題，答案就是$t^3-1$。至於你應該怎麼做呢:
> [!Note] **解1**
> 乘開: $(t^2+t+1)(t-1)=t^3+(1-1)t^2+(1-1)t+1=t^3-1$

> [!Note] **解2**
> 我認得$(t^2+t+1)$和$(t-1)$乘在一起是什麼，它的多項式是$t^3-1$。

多數人應該會選擇解2，而恭喜你用了卷積定理。考慮這樣一組對應: 傅立葉轉換=寫下多項式的係數，而多項式(時域)相乘=係數(頻域)的卷積。這就是了。事實上，卷積定理不只在傅立葉轉換上有效，對於多項式展開也有效。甚至我們可以將它拓展到泰勒級數上:
- $sin(x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\,...$
- $cos(x)=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\,...$

你可以試試不要看下面的解答，直接利用多項式乘法，也就是對逐項做卷積在化簡，來體驗一下沒有卷積定理是多麼痛苦。
$$
(x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\,...)(1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\,...)
$$$$
=x-(\frac{1}{3!}+\frac{1}{2!})x^3+(\frac{1}{5!}+\frac{1}{3!2!}+\frac{1}{4!})x^5+...
$$$$
=(\frac{1}{1!0!})x-(\frac{1}{3!0!}+\frac{1}{1!2!})x^3+(\frac{1}{5!0!}+\frac{1}{3!2!}+\frac{1}{1!4!})x^5+...
$$$$
=(\frac{1!}{1!0!})x-\frac{1}{3!}(\frac{3!}{3!0!}+\frac{3!}{1!2!})x^3+\frac{1}{5!}(\frac{5!}{5!0!}+\frac{5!}{3!2!}+\frac{5!}{1!4!})x^5+...
$$$$
\text{注意到: }\frac{n!}{n!0!}+\frac{n!}{(n-2)!2!}+\frac{n!}{(n-4)!4!}+...=\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+...=2^{n-1}
$$$$
=\sum_{k=0}^{\infty} (-1)^k\frac{1}{(2k+1)!}(2^{k-1})x^k
$$$$
=\frac{1}{2}\sum_{k=0}^{\infty} (-1)^k\frac{1}{(2k+1)!}(2x)^k
$$$$
=\frac{1}{2}\sin(2x)
$$

有了卷積定理:
> 兩函數的泰勒級數相乘(係數卷積)，等於兩函數相乘的泰勒級數。

所以:
$$
\sin(x)\cos(x)=\frac{1}{2}\sin(2x)=\frac{1}{2}\sum_{k=0}^{\infty} (-1)^k\frac{(2x)^k}{(2k+1)!}
$$就是這麼簡單。
<!--
以上說明留下兩個延伸讓我們探討:
1. 如果我要對兩個毫不相關的多項式，可能各有$N$項($N$很大)，求他們的乘積，我得要做$N^2$次乘法再相加。那如果我可以轉成頻域呢? 是不是可以在頻域做簡單的點對點乘法，再轉回多項式? 答案是可以。因此我們需要一種足夠快的算法處理傅立葉轉換。
2. 為什麼傅立葉轉換和多項式展開同樣有卷積定理? 因為$t^m t^n=t^{m+n}$，且$e^{j\omega t}e^{j\omega' t}=e^{j(\omega + \omega')t}$，兩者都具有$\chi(x+y)=\chi(x)\chi(y)$的形式。-->

## 證明
對於四種變換，證明的方式一視同仁: 爆開。全部爆開。這是最簡單的證明方式。

在前面講性質的小節裡面，我分別證明過CTFS和CTFT的雙向定理成立。

### *一般性的證明

在上一小節的最後，有個很瘋狂的理論可以一次解決四種變換。於是在這邊就秀一下怎麼用抽象的方式一次證完。注意它除了很簡潔很漂亮以外，對於理解沒有什麼幫助，而且可能造成你腦袋過載，請酌量服用。

首先我們先定義Pontryagin理論下的傅立葉變換(照抄6.1)，以及重新定義各個群上面的卷積:
:::info
**定義** 傅立葉變換: $G\to \widehat{G}$
$$
\hat{f}(\chi)=\int_{G}f(t)\overline{\chi(t)}\,d\mu(t),\,\,\chi\in\widehat{G}
$$
卷積
$$
(f*g)(t)=\int_{G}f(s)y(t-s)\,d\mu(s)
$$
:::
然後我們要求$x,y,(x*y)\in L^1(G)$，以使他們都有良好定義的傅立葉轉換。

接著考慮$\widehat{x*y}$，直接將兩個定義合併，即可得到:
$$
\widehat{x*y}=\int_{G}\left(\int_{G}x(s)y(t-s)\,d\mu(s)\right)\overline{\chi(t)}\,d\mu(t)
$$
接下來是一貫的伎倆，我們要拆掉這個二重積分。在積分裡面我們用的是Fubini Theorem，但現在我們得用它的進階版: Fubini–Tonelli Theorem。概念完全一樣，只是拓展到了任意可測函數上面，不再限制是實數上的函數。

首先得證明它適用，所以必須證明
$$
\int_{G}\int_{G}|x(s)y(t-s)\overline{\chi(t)}|\,d\mu(s)\,d\mu(t)
$$是有限的。我們直接對它來個變數變換: $u=t-s$，或$t=s+u$。哈爾測度跟我們學過(?)的勒貝格測度一樣，具有**平移不變性**。因此$d\mu(s+u)=d\mu(u)$。現在上式會變成:
$$
=\int_{G}\int_{G}|x(s)||y(u)||\overline{\chi(s+u)}|\,d\mu(s)\,d\mu(u)
$$
仔細觀察可以發現，根據6.1對$\chi$的定義，$|\chi|=1$。剩下的部分因為$s,u$獨立，所以可以拆成:
$$
=\int_{G}|x(s)|\,d\mu(s)\int_{G}|y(u)|\,d\mu(u)
$$根據$L^1$的假設，這兩個積分都有限。因此乘積有限。

回到最一開始的式子，我們已經證明了Fubini–Tonelli Theorem可用。所以我們大膽的將原式拆成雙重積分，且繼續套用$u=t-s$這個變換，變成:
$$
=\int_{G}\int_{G}x(s)y(u)\overline{\chi(s+u)}\,d\mu(s)\,d\mu(u)
$$
最後用上最關鍵的部分，根據定義，$\chi(x+y)=\chi(x)\chi(y)$。所以$\overline{\chi(s+u)}=\overline{\chi(s)}\,\overline{\chi(u)}$。這樣一來，積分可以被拆成$s,u$獨立的樣子:
$$
=\int_{G}\int_{G}x(s)y(u)\overline{\chi(s)}\,\overline{\chi(u)}\,d\mu(s)\,d\mu(u)
$$$$
=\left(\int_{G}x(s)\overline{\chi(s)}\,d\mu(s)\right)\left(\int_{G}y(u)\overline{\chi(u)}\,d\mu(u)\right)
$$$$
=\hat{x}\cdot\hat{y}
$$
雖然看起來跟我們做的前兩次差不多，但因為這次用了一般性的定義去做，所以得到的結果也不再局限於特定的變換，而是對四種變換都成立。

{%hackmd @seanyih/signal-main %}