臺灣博碩士論文加值系統

本論文是採用Single-path Delay Feedback 架構來完成一種適用於正交分頻多工通訊系統可變長度的傅立葉處理器並且採用一種新穎的演算法radix-2/4/8/16來完成我們的設計。為了規則性及低複雜度，我們使用了Radix-2/4/8/16演算法來有效的減少複數乘法而，並且也容易以VLSI實現，特別是在管線架構的實現上，此外，我們提出的快速傅立葉處理器是應用於IEEE 802.16 (WiMAX)。
我們介紹幾種快速傅立葉轉換演算法，為了能實現更多不同長度，需要能夠用在所有2的冪次方點數的快速傅立葉轉換系統上，其中mixed-radix 4/2 除了演算法可產生有規律性的硬體結構外，效率也比radix-2 好，所以選擇了mixed-radix 4/2來提昇其對不同長度的適應性與簡易度，並且此傅立葉快速處理器以Verilog硬體語言描述設計及ModelSim和Xilinx ISE模擬其結果。

In this thesis, the proposed design adopts SDF architecture. Moreover, we propose a new variable-length FFT processor with a novel algorithm, radix-2/4/8/16, for OFDM communication system. Due to the regularity and lowest hardware circuit complexity, radix-2/4/8/16 can efficiently minimize the number of complex multiplications and be implemented in VLSI design, especially in pipeline-based architecture. The proposed FFT processor can be used for the required length of IEEE 802.16 (WiMAX) standard.
We have introduced some FFT algorithms. Due to implement more different length, we need a algorithm that can suit all 2n-point systems. In contrast, mixed-radix 4/2 FFT algorithm is capable of producing hardware with structure regularity, and it is more efficient than radix-2 FFT algorithm. It is therefore selected for improving adaptability and facilitation, and this FFT processor has been implemented by using VerilogHDL, ModelSim and Xilinx ISE for circuit design and simulation, respectively.

中文摘要 i
ABSTRACT i
ACKNOWLEDGEMENTS iii
TABLE OF CONTENTS iv
LIST OF FIGURES viii
LIST OF TABLES xiii
CHAPTER 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Objective 3
1.3 Organization of the Thesis 3
CHAPTER 2 BACKGROUND OF FFT ALGORITHMS 5
2.1 Introduction 5
2.2 Basic Concepts of FFT Algorithm 6
2.3 Decimation-In-Frequency (DIF) FFT Algorithm 8
2.3.1 Classification of FFT Algorithms 8
2.3.2 Fixed-Radix FFT Algorithms 8
2.3.2.1 Radix-2 DIF FFT Algorithm 8
2.3.2.2 Radix-4 DIF FFT Algorithm 11
2.3.2.3 Radix- DIF FFT Algorithm 12
2.3.2.4 Radix-8 DIF FFT Algorithm 13
2.3.2.5 Radix- DIF FFT Algorithm 14
2.3.3 Spilt-Radix FFT Algorithms 15
2.3.3.1 Spilt-Radix 2/4 FFT Algorithm 15
2.3.3.2 Spilt-Radix 2/8 FFT Algorithm 17
2.3.3.3 Spilt-Radix 2/16 FFT Algorithm 19
2.3.3.4 Spilt-Radix 2/4/8 FFT Algorithm 22
2.3.4 Mixed-Radix FFT Algorithm 25
CHAPTER 3 ARCHITECTURE OF FFT PROCESSOR 28
3.1 Introduction 28
3.2 Pipeline-Based FFT Architecture 29
3.2.1 Multiple-Path Delay Commutator Pipeline Architecture 31
3.2.1.1 Radix-2 DIF MDC Architecture (R2MDC) 32
3.2.1.2 Radix- DIF MDC Architecture (R MDC) 33
3.2.2 Single-Path Delay Feedback Pipeline Architecture 33
3.2.2.1 Radix-2 DIF SDF Architecture (R2SDF) 34
3.2.2.2 Radix-4 DIF SDF Architecture (R4SDF) 35
3.2.2.3 Radix- DIF SDF Architecture (R SDF) 37
3.3 Comparison of Pipeline Architectures 38
CHAPTER 4 THE DESIGN OF PROPOSED VARIABLE
LENGTH FFT 40
4.1 Introduction 40
4.2 Proposed Algorithm – Radix-2/4/8/16 41
4.3 Proposed Architecture Design 45
4.3.1 Butterfly Unit 53
4.3.2 Complex Multiplication 53
4.3.2.1 Multiplication of 53
4.3.2.2 Multiplication of and 54
4.3.2.3 Multiplication of , , and 56
4.3.2.4 Multiplication of Complex Twiddle Factor 58
4.3.3 Twiddle Factor Generator 59
4.4 Summary 60
CHAPTER 5 SIMULATION RESULTS 61
5.1 Simulation Procedure 61
5.2 Simulation Results 62
5.2.1 Simulation Result of RTL Level Design 62
5.2.2 Simulation Result of Gate Level Design 68
5.3 Summary 70
CHAPTER 6 CONCLUSIONS 76
REFERENCES 77

[1] S. Y. Park, N. I. Cho, S. U. Lee, K. Kim and J. Oh, “Design of 2K/4K/8K-point FFT Processor Based on CORDIC Algorithm in OFDM Receiver,” IEEE Communications, Computers and signal Processing, Vol.2, pp. 457-460, Aug. 2001.
[2] Y. T. Lin, P.Y. Tsai and T.-D. Chiueh, “Low-power Variable-Length Fast Fourier Transform Processor,” IEE Proc.-Comput. Digit. Tech., Vol.152, No. 4, pp. 499-506, July 2005.
[3] H. T. Lin, A New Variable-Length FFT Processor for IEEE 802.16 Standard, Master thesis, the Institute of Electrical Engineering, Tatung University, Taiwan, July 2007.
[4] T. C. Fung, FPGA Design and Implementation of A Memory-Based Mixed-Radix 4/2 FFT Processor, Master thesis, the Institute of Electrical Engineering, Tatung University, Taiwan, July 2005.
[5] J. W. Cooley and J. W. Tuke, “An Algorithm for Machine Computation of Complex Fourier Series,” Math. Computation, Vol. 19, pp. 297-301, April 1965.
[6] S. He and M. Torkelson, “Designing Pipeline FFT Processor for OFDM (de)Modulation, “ IEEE Signals, Systems, and Electronics, pp. 257-262, Oct.1998.
[7] P. Duhamel and H. Hollmann, “Split-radix FFT Algorithm,” Eletronic Letters, Vol. 20, No.1 pp. 14-16, Jan. 1984.
[8] S. Bouguezel, M. Omair Ahmad, and M.N.S. Swamy, “Arithmetic Complexity of the Split-Radix FFT Algorithms,” in Proceedings. IEEE International Conference on. Acoustics, Speech, and Signal Processing, 2005.
[9] L. Jia, Y. Gao, J. Isoaho and H. Tenhunen, “A New VLSI-Oriented FFT Algorithm and Implementation,” in Proceedings. IEEE ASIC Conference, pp.337-341, 1998.
[10] C. P. Hung, S. G. Chen and K.-L. Chen, “Design of an Efficient Variable-length FFT Processor,” IEEE ISCAS, Vol. 2, pp. 833-836, May 2004.
[11] S. He and M. Torkelson, “A New Approach to Pipeline FFT Processor,” in Proceedings. The 10th International, Parallel Processinf Symposium, pp.766-770, 1996.
[12] S. S. Wang and C. S. Li, “An Area Design of Variable-Length Fast Fourier Transform Processor,” Journal Degree Thesis, Institute of Communication Engineering, 2006.
[13] C. C. Wang, J. M. Huang, and H. C. Cheng, “A 2K/8K Mode Small-Area FFT Processor for OFDM Demodulation of DVB-T Receivers,” IEEE Transactions on Consumer Electronics, Vol. 51, no. 1, pp.28-32, Feb. 2005.
[14] B. M. Baas, “A Low-Power, High-Performance, 1024-point FFT Processor,” IEEE J. Solid-State Circuits, Vol. 34, pp.380-387, March 1999.
[15] W. C. Yeh and C. W. Jen, “High-Speed and Low-Power Split-Radix FFT,” IEEE Transactions on Signal Processing, Vol. 51, No. 3, March 2003.
[16] A. V. Oppenheim and R. W. Schafer, Descrite-Time Signal Processing, Prentice-Hall Inc., 1999.
[17] M. Chang, WLAN and WiMAX, Iowa State University lecture notes, 2006.