快速傅氏轉換法則重組態架構之設計

Design of Reconfigurable Architecture of Fast Fourier Transform Algorithm

詹松諭(Sung-Yu Chan)

指導教授 ： 黃朝章

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

https://doi.org/10.6838/YZU.2006.00049

摘要

快速傅立葉轉換(Fast Fourier Transform，FFT)是實現數位信號處理系統的一個重要法則。在FFT的運算過程中需要應用複雜的記憶體定址模式計算，在做蝴蝶運算(Butterfly Computation)時，必須正確地從記憶體位址中讀取資料與轉換因子(Twiddle Factor)，然後再進一步作乘法與加減法之運算，並且將運算完的結果回存到該記憶體中，做為下一階段蝴蝶運算所需的資料。
對一固定序列的FFT而言，其蝴蝶運算所存取的資料與轉換因子位址，會因處理資料個數與所執行之階段不同而有所改變，所以我們提供了一個位址產生器，採用精簡的算術邏輯位移單元來簡化記憶體定址的計算單元，並且可支援非固定序列之N-Point FFT所需的各種記憶體序列位址，而組態成所需的N-Point FFT。另外在蝴蝶運算中所產生的硬體複雜度，則使用回授位移-加法元件來簡化硬體，並且透過位址產生器所產生的資料與轉換因子位址的傳送順序，達到乘法器共用與位移-加法元件共用，以降低其硬體複雜度。
在實作方面則是採用Xilinx ISE Foundation以Verilog語法來完成此架構，並搭配ModelSim來做功能之模擬，最後再透過Xilinx VirtexII-XC2V1000 FPGA來實現N-Point FFT，以驗證本論文所提的快速傅氏轉換法則重組態架構之設計。

關鍵字

離散傅立葉轉換,快速傅立葉轉換,蝴蝶運算

並列摘要

Fast Fourier transform is an important to implement a digital signal processing system. In the operation of FFT, it need to do complicated calculation. In each two-point butterfly computation, it need to read the correct data and twiddle factor from the memory address, then do the computation of multiplication and addition, and store the result in the memory, and provide the data for the next stage butterfly computation.
For a fix length sequence butterfly computation, the address sequence of data and twiddle factor, depend on the data's number and Different processing stages. So we provide an address generator using the arithmetic logic unit to simplify the computation of the memory address. It can also support various length N-Point FFT, and configure the address generator for the N-Point FFT. Because of the hardware complexity of the butterfly computation, we use the shift-add device to simply hardware implement, and share between multipliers. We can change the data sequences to decrease the numbers of the multipliers and ahift-add device and reduce the hardware complexity.
In implementation, we use Xilinx ISE Foundation to build this structure with Verilog syntax, and to simulate the function with Modelsim. We implement N-Point FFT on Xilinx VirtexII-XC2V1000 FPGA, and verify the design of reconfigurable architecture with fast Fourier transform algorithm.

並列關鍵字

DFT,FFT,FPGA,Twiddle Factor,Butterfly

參考文獻

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

[3] C. H. Yang, “The Design of Address Sequence Generator in DSP Processor”, Computer Science of Yuan-Ze University, Dec. 2000.

[6] B. M. Baas, “A Low-Power, High-Performance, 1024-Point FFT Processor”, IEEE Journal of Solid-State Circuits, Vol. 34, Issue 3, pp.380-387, March 1999.

[13] Y. Jiang, T. Zhou, Y. Tang and Y, Wang, “Twiddle-Factor-Based FFT Algorithm with Reduced Memory Access”, Proceedings of the International Parallel and Distributed Processing Symposium, IPDPS 2002, pp. 70-77, April 2002.

[15] W. R. Knight and R. Kaiser, “A Simple Fixed-Point Error Bound for the Fast Fourier Transform”, IEEE Trans. Acoustics, Speech and Signal Processing, Vol. 27, Issue 6, pp. 615-620, Dec. 1979.