## 摺積與離散傅立葉轉換

\begin{aligned} p(t)&=a_0+a_1t+\cdots+a_{n-1}t^{n-1},\\ q(t)&=b_0+b_1t+\cdots+b_{n-1}t^{n-1},\end{aligned}

$p(t)q(t)=c_0+c_1t+\cdots+c_{2n-2}t^{2n-2}$

$k$ 次項由 $(a_jt^j)(b_{k-j}t^{k-j})$ 構造而成，其係數為

$\displaystyle c_k=\sum_{j=0}^ka_{j}b_{k-j},~~k=0,1,\ldots,2n-2$

$\mathbf{a}=\begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{n-1} \end{bmatrix},~~\mathbf{b}=\begin{bmatrix} b_0\\ b_1\\ \vdots\\ b_{n-1} \end{bmatrix},$

$\mathbf{a}\circledast\mathbf{b}\overset{\underset{\mathrm{def}}{}}{=}\begin{bmatrix} a_0b_0\\ a_0b_1+a_1b_0\\ a_0b_2+a_1b_1+a_2b_0\\ \vdots\\ a_{n-2}b_{n-1}+a_{n-1}b_{n-2}\\ a_{n-1}b_{n-1}\\ 0 \end{bmatrix}_{2n\times 1}$

$\displaystyle (\mathbf{a}\circledast\mathbf{b})_k=\sum_{j=0}^ka_jb_{k-j},~~k=0,1,\ldots,2n-1$

$k=0:$

$\begin{matrix} ~&~&~&~&a_0&a_1&a_2&\cdots&a_{n-1}\\ ~&~&~&~&\times&~&~&~&~\\ b_{n-1}&\cdots&b_2&b_1&b_0&~&~&~&~ \end{matrix}$

$k=1:$

$\begin{matrix} ~&~&~&~&a_0&a_1&a_2&\cdots&a_{n-1}\\ ~&~&~&~&\times&\times&~&~&~\\ ~&b_{n-1}&\cdots&b_2&b_1&b_0&~&~&~ \end{matrix}$

$k=2:$

$\begin{matrix} ~&~&~&~&a_0&a_1&a_2&\cdots&a_{n-1}\\ ~&~&~&~&\times&\times&\times&~&~\\ ~&~&b_{n-1}&\cdots&b_2&b_1&b_0&~&~ \end{matrix}$

$\vdots$
$k=2n-2:$

$\begin{matrix} a_0&a_1&a_2&\cdots&a_{n-1}&~&~&~&~\\ ~&~&~&~&\times&~&~&~&~\\ ~&~&~&~&b_{n-1}&\cdots&b_2&b_1&b_0 \end{matrix}$

(1) 交換律：$\mathbf{a}\circledast\mathbf{b}=\mathbf{b}\circledast\mathbf{a}$

(2) 分配律：$(\mathbf{a}+\mathbf{b})\circledast\mathbf{c}=\mathbf{a}\circledast\mathbf{c}+\mathbf{b}\circledast\mathbf{c}$

(3) 純量結合律：$\alpha(\mathbf{a}\circledast\mathbf{b})=(\alpha\mathbf{a})\circledast\mathbf{b}=\mathbf{a}\circledast(\alpha\mathbf{b})$

$T(\mathbf{x}+\mathbf{y})=(\mathbf{x}+\mathbf{y})\circledast\mathbf{h}=(\mathbf{x}\circledast\mathbf{h})+(\mathbf{y}\circledast\mathbf{h})=T(\mathbf{x})+T(\mathbf{y})$

$T(\alpha\mathbf{x})=(\alpha\mathbf{x})\circledast\mathbf{h}=\alpha(\mathbf{x}\circledast\mathbf{h})=\alpha T(\mathbf{x})$

$T(\mathbf{e}_i)=\mathbf{e}_i\circledast\mathbf{h}=\begin{bmatrix} 0\\ \vdots\\ h_0\\ h_1\\ \vdots\\ h_{n-1}\\ \vdots\\ 0 \end{bmatrix}_{2n\times 1},$

\begin{aligned} T(\mathbf{x})&=T(x_0\mathbf{e}_0+x_1\mathbf{e}_1+\cdots+x_{n-1}\mathbf{e}_{n-1})\\ &=x_0T(\mathbf{e}_0)+x_1T(\mathbf{e}_1)\cdots+x_{n-1}T(\mathbf{e}_{n-1})\\ &=\begin{bmatrix} T(\mathbf{e}_0)&T(\mathbf{e}_1)&\cdots&T(\mathbf{e}_{n-1}) \end{bmatrix}\begin{bmatrix} x_0\\ x_1\\ \vdots\\ x_{n-1} \end{bmatrix}\\ &=H\mathbf{x},\end{aligned}

$H=\begin{bmatrix} h_0&0&\cdots&0\\ h_1&h_0&\cdots&0\\ h_2&h_1&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ h_{n-1}&h_{n-2}&\cdots&h_0\\ 0&h_{n-1}&\cdots&h_1\\ 0&0&\cdots&h_2\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&h_{n-1}\\ 0&0&\cdots&0 \end{bmatrix}_{2n\times n}$

$\mathbf{x}\longrightarrow\boxed{~~\mathbf{h}~~}\longrightarrow\mathbf{x}\circledast\mathbf{h}$

$\mathbf{x}\longrightarrow\boxed{~~H~~}\longrightarrow H\mathbf{x}$

$T(\mathbf{x})=H\mathbf{x}=\begin{bmatrix} 2&0&0&0\\ 1&2&0&0\\ 1&1&2&0\\ 1&1&1&2\\ 0&1&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}\begin{bmatrix} 1\\ 2\\ 0\\ 0 \end{bmatrix}=1\begin{bmatrix} 2\\ 1\\ 1\\ 1\\ 0\\ 0\\ 0\\ 0 \end{bmatrix}+2\begin{bmatrix} 0\\ 2\\ 1\\ 1\\ 1\\ 0\\ 0\\ 0 \end{bmatrix}=\begin{bmatrix} 2\\ 5\\ 3\\ 3\\ 2\\ 0\\ 0\\ 0 \end{bmatrix}$

$\mathbf{a}\circ\mathbf{b}=\begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{n-1} \end{bmatrix}\circ\begin{bmatrix} b_0\\ b_1\\ \vdots\\ b_{n-1} \end{bmatrix}\overset{\underset{\mathrm{def}}{}}{=}\begin{bmatrix} a_0b_0\\ a_1b_1\\ \vdots\\ a_{n-1}b_{n-1} \end{bmatrix}$

$\hat{\mathbf{x}}$$\hat{\mathbf{h}}$ 表示加入 $n$ 個零元的 $2n$ 維增廣向量：

$\hat{\mathbf{x}}=\begin{bmatrix} x_0\\ \vdots\\ x_{n-1}\\ 0\\ \vdots\\ 0 \end{bmatrix}_{2n\times 1},~~\hat{\mathbf{h}}=\begin{bmatrix} h_0\\ \vdots\\ h_{n-1}\\ 0\\ \vdots\\ 0 \end{bmatrix}_{2n\times 1}$

$F$$2n\times 2n$ 階傅立葉矩陣 (見“離散傅立葉轉換”)：

$F=\begin{bmatrix} 1&1&1&\cdots&1\\ 1&w&w^2&\cdots&w^{2n-1}\\ 1&w^2&w^4&\cdots&w^{2(2n-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&w^{2n-1}&w^{2(2n-1)}&\cdots&w^{(2n-1)^2} \end{bmatrix}$

$F(\mathbf{x}\circledast\mathbf{h})=(F\hat{\mathbf{x}})\circ(F\hat{\mathbf{h}})$

$\mathbf{f}_p\circ\mathbf{f}_q=\mathbf{f}_{p+q},~~p,q=0,1,\ldots,n-1$

\displaystyle \begin{aligned} (F\hat{\mathbf{x}})\circ(F\hat{\mathbf{h}})&=\left(x_0\mathbf{f}_0+x_1\mathbf{f}_1+\cdots+x_{n-1}\mathbf{f}_{n-1}\right)\circ\left(h_0\mathbf{f}_0+h_1\mathbf{f}_1+\cdots+h_{n-1}\mathbf{f}_{n-1}\right)\\ &=\sum_{k=0}^{2n-2}\left(\sum_{j=0}^kx_jh_{k-j}\right)\mathbf{f}_k\\ &=\sum_{k=0}^{2n-2}(\mathbf{x}\circledast\mathbf{h})_k\mathbf{f}_k\\ &=F(\mathbf{x}\circledast\mathbf{h})\end{aligned}

$\displaystyle\mathbf{x}\circledast\mathbf{h}=F^{-1}\left((F\hat{\mathbf{x}})\circ(F\hat{\mathbf{h}})\right)$

### 12 Responses to 摺積與離散傅立葉轉換

1. Watt Lin 說道：

請問老師：
能否簡短說明，或需另外寫個長篇文章？
謝謝！

• ccjou 說道：

好的，我再找時間寫一篇離散傅立葉轉換與頻域分析的基本原理簡介。

• Watt Lin 說道：

感謝老師的回答。
我是外行人，好像也問得不恰當，
發問後，看見老師答案之前，自己思考，
淡入淡出，在時域應該可以處理，不必轉換到頻域作處理。
我所好奇的，頻域分析，有沒有日常生活經常遇到的應用，能否作些初步簡介？

• ccjou 說道：

好的，但我不是訊號處理專家，還要花點時間研究一下。

• 秦紀維 說道：

醫療影像學。將影像轉換到頻域後，取高頻域再做逆轉換會凸顯細節，相對的取低頻域做逆轉換會忽略掉細節。後者用處不大，畢竟近視眼、注意力短缺、阿茲海默症就有類似功能（不正經）。

• ccjou 說道：

JPEG 壓縮的量化歩驟就是保留低頻忽略高頻細節。

2. Watt Lin 說道：

請問老師：摺積運算，有沒有卡通動畫影片?
我在wiki看到簡單的幾張圖與動畫， http://en.wikipedia.org/wiki/Convolution
不知外國的其他網站，有沒有更仔細的動畫方式解說？

3. Watt Lin 說道：

http://en.wikipedia.org/wiki/Convolution
在wiki，摺積有幾張圖可供想像，還有個簡單動畫。
請問老師：國外其他網站，對於摺積，有沒有更仔細的卡通動畫？

• ccjou 說道：

謝謝你提供的動畫訊息。我所知道的動畫模擬也都很類似，例如，
http://mathworld.wolfram.com/Convolution.html
基本原理就是上文所述，兩列迎向對駛的火車內積。

不知道為甚麼你的迴響被系統當作垃圾。原本我選擇的設定是「如果一則迴響中超過 3條鏈結，即判斷為垃圾，必須審核通過才可以發表。」

• Watt Lin 說道：

老師提供MathWorld這個網頁連結，也很有幫助。
我從好幾年前，偶爾看一點點有關傅立葉轉換的介紹，一直看不懂摺積。
到了2012年，購買交通大學出版社的「訊號與系統」光碟，
謝世福教授採取幽默的解說，我才開始懂摺積。
他說：「吃一粒米，第一天很有力氣，第二天還剩餘一些力氣，第三天力氣微弱，並且在黑板畫上三條不同高度的線條。然後又說，第二天也吃一粒米，第二天的力氣，是第二粒米的力氣，加上第一天剩餘的力氣。第三天又吃一粒米，便有三天個別力氣的總和。」
這種比喻法，聽起來很誇張，但我很喜歡這樣的幽默，幫助理解！

• ccjou 說道：

哈哈，謝老師的每天吃米粒的譬喻比我的兩列迎向對駛的火車更傳神。

• Watt Lin 說道：

如果有人講，吃一顆藥，第一天血液中藥物濃度高，第二天降至一半左右，第三天仍有一點點藥物濃度。
第二天又吃相同的一顆藥，血中濃度，不僅受第二天藥物影響，也要加上第一天的剩餘影響。
這樣的比喻法，沒有誇張，而且聽起來近乎學理。
但是，藥理學的研究，好像不會用到摺積這種觀念。