以樹狀重組技術實現高延展性數位傅立葉轉換器之研究

Abstract

近幾年來快速傅立葉轉換與反快速傅立葉轉換已經被廣泛的被提出並應用在xDSL上。文獻上可考之快速傅立葉轉換演算法很多，如:radix-2、radix-4 與split-radix 等。這些演算法各有各的優點以符合應用的需求。已有很多論文針對其中一種演算法來實現硬體，但是很少有論文能提出彈性的方法或是硬體架構能允許設計者充分且適當探索分析演算法的平行度與元件配置可能。在本篇論文中，提出用樹狀的架構來詮釋各種演算法並充分呈現演算法平行化的各種可能性。我們所提的方法可以彈性的實現不同的快速傅立葉轉換運算，而且在硬體架構上也可依使用者所需增加平行度。為了證實我們提出的樹狀FFT架構的可行性，我們用FPGA實現SR-2/4 64點的FFT並完成軟體驗證。

FFT and IFFT have been broadly applied to xDSL technology. There have existed a large number of FFT algorithms, such as radix-2, radix-4 and split-radix. Designers may use any of them to implement FFT/IFFT computations according to system requirements. Papers have presented architectures for implementing specific FFT algorithms; however, few papers propose general architectures for exploring possibilities of parallelization. This thesis proposes a tree-based FFT algorithm that gives designers a good position to view the parallelism of FFT algorithms and hence provides a handy tool for FFT/IFFT architects. The tree-based FFT algorithm is highly scalable in terms of the number of processing elements and pipelining buffers. The scalability makes tradeoffs between memory and processing power tractable. To demonstrate the feasibility of proposed tree-Based FFT architecture and its correctness, we implemented a 64-point SR-2/4 FFT on FPGA platform and verified the functionality using FPGA emulation environment.