高效能之快速傅利葉運算法

Abstract

這論文主要的目的在於為了不同的應用問題, 發展有效率的FFT演算法. 在不同的環境情況之下, 藉由縮短運算時間和使用較少的主記憶體, 使FFT的運算行為盡可能達成極致的目標,. 在一般的狀況下, 我們所接受的輸入或要求的輸出, 都存在著某些特定的形態, 可以很有效的利用這些性質, 設計出比較好的方式來完成它, 如input/output pruning 的策略可以減少不必要的計算和針對輸入資料有實數特性或複數對稱特性加以處理節省運算時間. 而且我們也提到了關於使用moving FFT有效率的處理STFT的方式, 讓計算STFT變得比較聰明一些. 然而在這篇報告中, 我們覺得有兩個主題是很具有建設性的, 一個就是tunnel FFT的觀念和實作, 另一個是2D svr-FFT (split-vector-radix FFT)的實踐. 關於tunnel FFT, 我們主要的觀點在於當需求不多時,可以利用較少的空間去完成很大空間的運算, 這種論點尤其對於高維度的訊號更顯得重要; 至於2D svr-FFT, 我們首先探索它的結構, 推導出一理論, 這理論能夠在給定的stage中, 指出DFT blocks的位置, 而且我們發現DFT blocks的分佈呈現碎形的結構, 即是大家所熟之的Sierpinski triangle. 利用此理論, 讓我們也能夠實際實現出2D svr-FFT. 更重要的是, 這些討論皆可推廣到任意維度, 不只如此, 對於運算量的分析, 也提供了和傳統上利用遞迴運算式不大相同的方法. 這個方法是非常直接而且容易瞭解. 總而言之, 如何使用最少的電腦資源完成想完成之事, 是這論文最重要的精神所在.

The main purpose of this dissertation is to develop efficient fast-Fourier-transform (FFT) algorithms for different applications. These algorithms are designed to best enhance the performance of FFT computation, in different conditions, mainly by reducing the arithmetic operations and reducing the storage requirement. Better FFT algorithms can be designed by using some particular properties of the computational architecture. For example, the input/output pruning strategy can be employed to reduce unnecessary computations; and the symmetrical property for real input data can be explored to save computational time. In addition, we discuss an efficient approach for computing the running spectra based on short-time Fourier transform (STFT). The approach is competitive in computing the moving-windowed STFT’s. Two constructive subjects in this research are: 1) the concept and implementation of tunnel FFT, and 2) realization of 2D svr-FFT (split-vector-radix FFT). In tunnel FFT, the main idea is to efficiently utilize the memory space to accomplish heavy FFT computations. The idea is important especially for multidimensional signal. In 2D svr-FFT, we, for the first time, explore its structure, derive a theorem to identify the DFT blocks at a given stage, and discover the phenomenon that the distribution of DFT blocks (DFT image) exhibits fractal structure—— the well-known Sierpinski triangle. The result enables us to develop an efficient algorithm that actually implements the concept of 2D svr-FFT. Most importantly, it can be easily extended to higher-dimensional svr-FFT algorithms. This research work also proposes an unconventional method, instead of the widely-used recursive approach, for analyzing the number of arithmetic operations required by FFT algorithms. The proposed method is straightforward and more comprehensible. In summary, the dissertation is mainly focused on how to accomplish a given FFT computation by utilizing the minimum computer resources. 1.1 Beginning 1.2 Organization of this Dissertation 2 Background 2.1 Defintion and View of DFT 2.2 Beginning of FFT 2.3 Basic Architecture of FFT 2.4 Basic Programming Skill 3 Split-Radix FFT 3.1 Background 3.2 The Relation between DFT Blocks 3.3 Programming Aspects for 1D and 2D DIT sr-FFT 3.4 Computational Complexity 3.4.1 Theoretical Analysis 3.4.2 Computer Simulation 4 Real-Time Shift-Pruning FFT 4.1 Background 4.2 Input/Output Pruning FFT 4.3 Moving FFT 4.4 Real-Time FFT 4.5 Real-Time Shift-Pruning FFT 4.6 Computational Complexity 4.6.1 Theoretical Analysis 4.6.2 Computer Simulation 5 2D Vector-Radix FFT for Real and Conjugate-Symmetric Data 5.1 Background 5.2 Data Layout of the 2D DFT Block 5.3 Computational Complexity 5.3.1 Theoretical Analysis 5.3.2 Computer Simulation 6 Tunnel FFT 6.1 Background 6.2 Tunnel FFT and Tunnel IFFT 6.3 Computational Complexity 6.3.1 Theoretical Analysis 6.3.2 Computer Simulation 7 Conclusion Appendix A 1D sr-FFT Code Appendix B 2D svr-FFT Pseudo Code Appendix C Computational Scheme for 2D Real Input Appendix D Computational Scheme for 2D Conjugate-Symmetric Input