臺灣博碩士論文加值系統

本論文先介紹幾種基本DIT和DIF的傅立葉演算法並分析比較其算術複雜度，接著敘述兩種FFT 的結構，包括管道式和以記憶體為基本的FFT結構。因為我們在實現上大部分硬體面積都花費在乘法器上，所以我們除了把每一級的乘法器縮減為一個之外，並且利用CORDIC Operator去簡化所有的”twiddle factor”運算，最後我們提出一個簡化傅立葉轉換器面積的架構，並且在FPGA上面實現它。

This paper introduces several algorithms and compares the computational complexity first. Second, we introduce two FFT (Fast Fourier Transform) architectures and it includes of pipelined based architecture and memory based architecture. Because we cost a lot of area size in multiplication, we reduce the multiplication in each stage. And then we use the CORDIC (Coordinate Rotation Digital Computer) operator to reduce the computation of twiddle factor. Finally, we propose a new architecture to minimize the area size and implement it in FPGA.

CHAPTER 1 INTRODUCTION 3
1.1 Background 3
1.2 Organization of the Thesis 4
CHAPTER 2 Review of FFT Algorithms 5
2.1 Introduction 5
2.2 Basic Concepts of FFT Algorithms 6
2.3 Decimation-in-Time (DIT) FFT Algorithms 8
2.3.1 Radix-2 DIT FFT Algorithm and Complexity 8
2.3.2 Radix-4 DIT FFT Algorithm and Complexity 13
2.4 Decimation-in- Frequency (DIF) FFT Algorithms 14
2.4.1 Radix-2 DIF FFT Algorithm and Complexity 14
IV
2.4.2 Radix-4 DIF FFT Algorithm and Complexity 18
2.5 Comparisons and Summary 19
CHAPTER 3 FFT Processor Architectures 21
3.1 Introduction 21
3.2 Pipeline-Based FFT Architecture 22
3.2.1 Single-Path Delay Feedback Pipeline Architecture 22
3.2.2 Multiple-Path Delay Commutator Pipeline Architecture 24
3.3 Memory-Based Architecture 28
3.4 CORIC multipliers 29
3.5 Summary 33
CHAPTER 4 Proposed FFT Design 34
4.1 Introduction 34
4.2 Area-efficient FPGA-based FFT processor 34
CHAPTER 5 Conclusions 40
5.1 Conclusion 40
5.2 Future Work 41
REFERENCE

[1] J. W. Cooley and J. W. Tukey, “An Algorithm for Machine Computation of Complex Fourier Series,” Math. Computation, Vol. 19,pp. 297-301,April 1965.
[2] A. V. Oppenheim R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall Inc., 1999.
[3] Szedo, G. and Yang, V. and Dick, C,” High-performance FFT processing using reconfigurable logic” Signals, Systems and Computers Vol. 2 , P 1353 - 1356 Nov., 2001.
[4] Sansaloni, T. and Perez-Pascual and A.; Valls, J.” Area-efficient FPGA-based FFT processor ”Electronics Letters , Vol 39 , Issue: 19 , 18 P1369 – 1370 Sept. 2003
[5] Son, B.S. and Jo, B.G.; Sunwoo, M.H. and Yong Serk Kim , ” A high-speed FFT processor for OFDM systems” IEEE International Symposium on Circuits and Systems
pp.III-281 - III-284 vol.3 26-29 May 2002
[6] Sadat, A. and Mikhael, W.B.”Fast Fourier Transform for high speed OFDM wireless multimedia system” Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems, P938 - 942 vol.2 14-17 Aug. 2001
[7] Chao-Kai Chang and Chung-Ping Hung and Sau-Gee Chen”An efficient memory-based FFT architecture” Proceedings of the 2003 International Symposium on Circuits and Systems, Pages:II-129 - II-132 Vol 2 , 25-28 May 2003
[8] Perez-Pascual, A. and Sansaloni, T. and Valls, J.”FPGA-based radix-4 butterflies for HIPERLAN/2” IEEE International Symposium on Circuits and Systems, Pages:III-277 - III-280 vol.3 May 2002

42
[9] Shousheng He and Mats Torkelson, “A New Approach to Pipeline FFT Processor,” Parallel Processing Symposium, The 10th International, pp.766-770,1996.
[10] E. H. Wold and A. M. Despain, “Pipeline and Parallel-Pipeline FFT Processors for VLSI Implementation ,”IEEE Transactions on Computers, Vol. 33 No. 5, pp.414-426, May 1984.
[11] A. M. Despain, “Fast Fourier Transform Using CORDIC Iterations,” IEEE Trans. Comput., Vol. C-23 No. 10 pp. 993-1001, Oct. 1974.