本章總結、習題與參考資料

# 本章總結

本書的最後一章介紹四種傅立葉分析環境裡面的其中一種 DTFS 之特化版 DFT，因為不論時域還是頻域，它們在計算機都必須以離散形式呈現，這個環境才變成大家的首選，它的好處其實在文中一直都有強調，就是程式語言的封裝性加上 $\mathcal O(N\log N)$的運算速度，使得它變成主流，第四節是很經典的例子。

第二節所介紹的 DFT 特性非常重要 (必須熟悉)，第三節快速傅立葉轉換，如果只是單純用來處理訊號的話確實不用弄懂細節，然而如果要實作出第五節所提到的大數乘法時，當然你就必須知道原理，最後第六節所提的大規模線性摺積，只是因為大部分的訊號處理課本都會寫，筆者才放在這裡，初學者通常不會碰到所以是選讀章節。

# 延伸習題

1. 在第三節我們知道 Radix-2 DIT 的時間複雜度是為 $T(n) = 2T(n/2) + \mathcal{O}(n)$，其中 $\mathcal O(n)$包含了什麼運算？讓 $N=N_1N_2$，那一起使用 DIT 和 DIF 之一般化方法的計算時間遞迴式又該如何表示？假設在這個情況$N=b^{(2^m)}$，而且採一般化方法分解時總是選擇$N_1=N_2=b^{(2^{m-1})}$的拆解方式，整體的時間複雜度為何？會快過 Radix-2 DIT 的 $\mathcal O(N\log N)$嗎？這個世界上是否已經存在總是快過$\mathcal O(N\log N)$，也就是 $\mathcal o(N\log N)$的演算法？

2. 在第四節有提到使用 DFT 來分析離散訊號可以獲得 FFT 所帶來的好處。讀者是否可以自行設計實驗，量測不同點數和計算時間的關係，分別以 (手刻 DFT)、(MATLAB 的 fft 內建函式) 兩種方式執行？

3. 在第五節有提到使用 DFT 計算小規模線性摺積亦可以獲得 FFT 所帶來的好處。讀者是否可以自行設計實驗，量測不同點數和計算時間的關係，分別以 (手刻線性摺積)、(手刻 DFT)、(MATLAB 的 fft 內建函式) 三種方式執行？

4. 第四節利用 DFT 分析離散訊號，你可能會發現它的頻譜解析度過低，至少和第三章第二節的圖比起來的確是這樣沒錯，原本應該要有的 sidelobes 都不見了，為什麼？當然如果我們希望有自動展延週期性效果的話那是最好；相反地如果我們希望擬真，請問在不多給訊號源的情況下，你能用第二節所介紹的性質去解決這個問題嗎？

5. 在第五節介紹多項式乘法的時候，因為它和線性摺積有著極為直接的關係，筆者認為按照這樣的順序說明會讓印象比較深刻，如果讀者廣泛閱讀網路資料應該會發現還有另外一種廣為流傳的解釋，它把訊號視為多項式係數，旋轉因子視為自變數，而 DFT 則是從自變數算出應變數的過程 (函數的概念)，多項式次數愈高、點數就要愈多，用 DFT 把兩個待乘多項式都轉為數值後相乘再作 IDFT 轉回係數，這背後需要代數基本定理 [9] 的支持。有興趣的讀者可以試著理解這種想法。

# 參考資料

1. https://dsp.stackexchange.com/questions/16586/difference-between-discrete-time-fourier-transform-and-discrete-fourier-transform。網路論壇問 DTFS 和 DFT 的差別。

2. https://www.youtube.com/watch?v=eOvMUtMoQG8&t=2m27s。DFT 循環摺積特性的證明。

3. https://en.wikipedia.org/wiki/Fast_Fourier_transform#Algorithms。維基百科列舉各種 FFT 演算法。

4. http://mattsdsp.blogspot.com/2014/11/fft-cooley-tukey-algorithm-for-general.html。部落格描述一般化的 Cooley-Tukey 演算法。

5. Cooley, J. W., & Tukey, J. W. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of computation, 19(90), 297-301.。Cooley-Tukey 在當年所發表的 paper。

6. https://www.wolframalpha.com/input/?i=Expand+%281-4x%2B2x%5E2%29%285%2B7x-x%5E5%29 用 WolframAlpha 展開 $(1-4x+2x^2)(5+7x-x^5)$。

7. Manolakis, D. G., & Ingle, V. K. (2011). Applied digital signal processing: theory and practice. Cambridge University Press.。筆者撰寫數位訊號處理相關內容的參考書。

8. https://www.youtube.com/watch?v=AsVX2CxviWI。介紹 overlap-save 演算法的圖解。

9. https://zh.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86。維基百科介紹代數基本定理。