利用彈性階層之重組態架構實現快速傅立葉轉換

Implementation of Fast Fourier Transform Using Flexible Level Reconfigurable Architecture

陳智勇(Chih-Yung Chen)

指導教授 ： 黃朝章

元智大學/資訊學院/資訊工程學系/碩士(2008年)

摘要

現今為數位化的時代，為了達成此目的使用數位訊號處理(Digital Signal Process，DSP)法則將類比訊號轉變成數位訊號。其中快速傅立葉轉換(Fast Fourier Transform，FFT)在以正交分頻多工(Orthogonal Frequency Division Multiplexing，ODFM)為基礎的通訊系統上扮演的重要的角色。

　　FFT為離散傅立葉轉換(Discrete Fourier Transform，DFT)的快速演算法，是以2-radix的蝴蝶單元為基本運算模組來達成N-point FFT的運算。本論文以效能和彈性為考量，改以8點FFT運算為基本運算單元來建構N-point FFT之架構。經由控制單元判斷不同階層各蝴蝶單元所需的轉換因子(Twiddle Factor)位址以及資料傳輸路徑，再配合資料位址產生器提取對應計算位址之資料，借此達成運算的彈性及加快運算速度。

　　本論文實作方面是採用Xilinx ISE 9.1i以Verilog 硬體描述語言來完成此架構，之後以FPGA進行功能模擬和計算數值驗證。其模擬結果再與Matlab中FFT運算的結果進行比較，並探討此架構經過連續乘加運算後其產生結果之精確度所造成的影響。

關鍵字

快速傅立葉轉換 ； 重組態架構

並列摘要

Nowadays is a digital life, to success this goal we must use digital signal process’s algorithm to transform analogy signal to digital signal. Which fast fourier transforms (FFT) play an important role in orthogonal frequency division multiplexing (OFDM) based communication system.

FFT is a fast algorithm of discrete foruier transform (DFT), using radix-2 butterfly unit to be a basic computing module to complete N-point FFT computation. In the present thesis, performance and flexible are considered, and 8-point FFT are used to be a basic process element to construct N-point FFT architecture. The control unit will decide which butterfly unit in different level requires twiddle factor’s address and data path. Then cooperate with data address generation to get corresponding computing data address. Follow this method will reach computing flexible and improve performance.

In the present thesis, we use the Verilog HDL within Xilinx ISE 9.1i design tool to complete this architecture. After that, we use FPGA for function simulation and verify computation data, and the result will be compared with FFT result within Matlab. At the end we will discuss the effect of this architecture result’s precision after continue multiplier and adder.

並列關鍵字

FFT ； Reconfigurable Architecture ； FPGA

參考文獻

[2]J. W. Cooley and J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series”, Math. Comput., vol. 19, pp. 297-301, 1965.

[4]Petrovsky, A.A.and Shkredov, S.L., “Automatic Generation of Split-Radix 2-4 Parallel-Pipeline FFT Processors: Hardware Reconfiguration and Core Optimizations”, International Symposium on Parallel Computing in Electrical Engineering, pp. 181-186, 13-17 Sep. 2006

[5]W. C. Yeh and C. W. Jen, “High-speed and low-power split-radix FFT”, IEEE Transactions on Signal Processing, vol. 51, Issue 3, pp. 864-874, March 2003

[1]C. P. Hung, S. G. Chen and K. L. Chen, “Design of an Efficient Variable-Length FFT Processor”, International Symposium on Circuits and Systems, vol. 2, pp. II-833-6, 23-26 May 2004.

[3]Bouguezel, S., Ahmad, M.O. and Swamy, M.N.S., “Improved radix-4 and radix-8 FFT algorithms”, International Symposium on Circuits and Systems, vol. 3, pp.III-561-4, 23-26 May 2004.