本論文針對幾種傅立葉演算法去分析比較其算術複雜度，並對不同的架構做硬體效率、硬體成本和速度上的比較分析。最後整合提出一個適用於各種正交分頻多工調變系統的快速傅立業處理器架構，即可變長度單一處理單元架構。其可提供足夠的效能並且可用於所有2n點數的快速傅立業轉換。除此之外，我們亦介紹使用幾種設計技巧可用來簡化硬體複雜度，如：位元長度的模擬、快速傅立業與反快速傅立業處理器的硬體共用、係數暫存器的縮小等等。

In order to design a general efficient FFT/IFFT core suitable for various OFDM communication systems, the thesis first investigates possible design solutions from algorithm level to architecture level. Following that, a variable-length memory-based FFT/IFFT architecture is proposed. The FFT/IFFT core can be applied to all the current OFDM-based FFT computation with sufficient throughput rate. Besides, the thesis also introduces some design methodologies for low hardware complexity realization that include word length simulation, complex multiplier design, ROM table size reduction and hardware sharing of FFT and IFFT, and etc.

Chapter 1 Introduction 1
1.1 Background 1
1.2 Organization of this thesis 3
Chapter 2 Review of FFT Algorithms 4
2.1 Introduction 4
2.2 Basic Concepts of FFT Algorithms 5
2.3 The Fixed-Radix FFT Algorithms 8
2.3.1 Radix-2 FFT Algorithm and Complexity 8
2.3.2 Radix-4 FFT Algorithm and Complexity 12
2.3.3 Radix-8 FFT Algorithm and Complexity 15
2.4 The Split-Radix FFT (SRFFT) Algorithms 18
2.4.1 Split-Radix 2/4 FFT Algorithm and Complexity 19
2.4.2 Split-Radix 2/8 FFT Algorithm and Complexity 21
2.5 Comparisons and Summary 22
Chapter 3 Review of FFT Architectures 24
3.1 Introduction 24
3.2 Pipeline-Based FFT Architectures 25
3.2.1 Introduction 25
3.2.2 Single-Path Delay Feedback Pipeline Architecture 26
3.2.3 Multiple-Path Delay Commutator Pipeline Architecture 32
3.2.4 Comparison of Pipeline Structures 36
3.3 Memory-Based FFT Architectures 39
3.3.1 Introduction 39
3.3.2 Efficient Method for Memory Partition 41
3.3.3 Performance Analysis 42
3.4 Summary 43
Chapter 4 FFT/IFFT Hardware Design for OFDM Communication System 45
4.1 OFDM Basics 45
4.2 FFT/IFFT Hardware Design 47
4.2.1 Algorithm and Architecture Selection 47
4.2.2 Arithmetic Module Design 50
4.2.3 ROM Table Size Reduction 51
4.2.4 Hardware Sharing of FFT and IFFT 53
4.3 Variable-Length FFT Module Design 54
4.4 FFT Outputs Reordering 58
4.5 Summary 60
Chapter 5 Implementation of a VL Memory-Based FFT Architecture 61
5.1 Design Consideration 61
5.2 Complete Architecture 64
5.2.1 Input Buffer and Main Memory 64
5.2.2 Processing Element 65
5.2.3 VL Address Generator (VL_AG) 66
5.2.4 Commutators on Both Sides of The Main Memory Banks 68
5.3 Word Length Optimization 69
5.4 Summary 73
Chapter 6 Conclusion and Future Work 74
6.1 Conclusion 74
6.2 Future Work 74
Bibliography 76

[1] Yeong-Terng Lin, Design and Implementation of a Variable-Length FFT Processor for OFDM Systems, NTU, Master Thesis, June 2001.
[2] 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.
[3] A. V. Oppenheim R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall Inc., 1999.
[4] Pierre Duhamel, “Implementation of Split-Radix FFT Algorithms for Complex, Real, and Real-Symmetric Data,” IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-34 No. 2, April 1986.
[5] Jun-Jie Fang, Design of FFT Processor, NCTU, Master Thesis, August 2001.
[6] P. Dunamel, H. Hollmann, “Split Radix FFT Algorithm,” Electronics Letters 5th Vol. 20 No. 1, January 1984.
[7] Shousheng He and Mats Torkelson, “A New Approach to Pipeline FFT Processor,” Parallel Processing Symposium, The 10th International, pp. 766-770, 1996.
[8] Shousheng He and Mats Torkelson, “Designing Pipeline FFT Processor for OFDM (de) Modulation,” URSI International Symposium on Signals, Systems and Electronics, pp. 257-262, 1998.
[9] Shousheng He and Mats Torkelson, “Design and Implementation of a 1024-point FFT Processor” in Proc. IEEE Custom Integrated Circuit Conference, pp. 131-134, 1998.
[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] L. G. Johnson, “Conflict Free Memory Addressing for Dedicated FFT Hardware,” IEEE Transactions on Circuit and System-II: Analog and Digital Signal Processing, Vol. 39 No.5, pp.312-316, May 1992.
[12] Hsin-Fu Lo, Ming-Der Shieh, and Chien-Ming Wu, “Design of an Efficient FFT Processor for DAB System,” IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 654 —657, 2001.
[13] Yutai Ma, “An Effective Memory Addressing Scheme for FFT Processors,” IEEE Transactions on Signal Processing, Vol. 47 Issue: 3, pp. 907-911, March 1999.
[14] Yutai Ma and Lars Wanhammar, “A Hardware Efficient Control of Memory Addressing for High-Performance FFT Processors,” IEEE Transactions on Signal Processing, Vol. 48 Issue: 3, pp. 917-921, March 2000.
[15] C. H. Chang, C. L. Wang and Y. T. Chang, “Efficient VLSI Architectures for Fast Computation of the Discrete Fourier Transform and Its Inverse,” IEEE Transactions on Signal Processing, Vol. 48 Issue: 11, pp. 3206-3216, Nov. 2000.
[16] C. L. Wang and C. H. Chang, “A New Memory-Based FFT Processor for VDSL Transceivers,” IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 670 —673, 2001.
[17] Wen-Chang Yeh, Arithmetic Module Design and its Application to FFT, NCTU, Doctor Thesis, August 2001.
[18] Lihong Jia, Yonghong Gao and Hannu Tenhunen, “ A Pipelined Shared-Memory Architecture for FFT Processors,” 42nd Midwest Symposium on Circuits and Systems, Vol. 2 pp. 804 —807, 2000.
[19] A. M. Despain, “Fast Fourier Transform Using CORDIC Iterations,” IEEE Trans. Comput., Vol. C-23 No. 10 pp. 933-1001, Oct. 1974.
[20] G. Bi and E. V. Jones, “A Pipelined FFT Processor for Word Sequential Data,” IEEE Trans. Acoust., Speech, Signal Processing, Vol. 37 No. 12, pp. 1982-1985, Dec. 1989.
[21] L. R. Rabiner and B. Gold, Theory and Application of Digital Signal Processing, Prentice-Hall Inc., 1975.
[22] B. S. Kim and L. S. Kim, “Low Power Pipelined FFT Architecture for Synthetic Aperture Radar Signal Processing,” in Proc. IEEE Midwest Symposium on Circuits and Systems, Vol.3, pp. 1367-1370, 1996.
[23] M. M. Jamali, S. C. Kwatra and D. H. Shetty, “ Module Generation Based VLSI Implementation of A Demultiplexer for Satellite Communications,” in Proc. IEEE International Symposium on Circuits and Systems, Vol.4, pp. 364-367, 1996.
[24] A. Delaruelle, j. huisken, J. van Loon, F. Welten, “A Channel Demodulator IC for Digital Audio Broadcasting” in Proc. IEEE Custom Integrated Circuits Conference, pp. 47-50, 1994.
[25] Ediz Cetin, Richard C. S. Morling and Izzet Kale, “An Integrated 256-point Complex FFT Processor for Real-time Spectrum Analysis and Measurement,” IEEE Instrumentation and Measurement Technology Conference, Ottawa, Canada, May 19-21, 1997.
[26] M. C. Pease, “Organization of Large Scale Fourier Processors,” J. Assoc. Mach. Comput., Vol. 16, pp. 474-482, July 1969.
[27] D. Cohen, “Simplified Control of FFT Hardware,” IEEE Trans. Acoust., Speech Signal Processing, Vol. ASSP-24, pp. 577-579, Dec. 1976.
[28] L. K. Tan and H. Samueli, “A 200 MHz Quadrature Digital Synthesizer/Mixer in 0.8 um COMS,” IEEE Journal of Solid-State Circuits, Vol. 30 No. 30, pp. 193-200, Mar. 1995.
[29] R. Radhouane, P. Liu, c. Modlin, “Minimizing the Memory Requirement for Continuous Flow FFT Implementation: Continuous Flow Mixed Mode FFT (CFMM-FFT)” Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. Vol. 1, pp. 116-119, 2000.