臺灣博碩士論文加值系統

這篇論文提出一個可用於正交分頻多工通訊系統(OFDM)的低成本和可變長度之快速傅利葉轉換處理器。radix-2/4/8演算法是一個常見及能有效地使運算過程中複數乘法的數量減到最小的快速傅利葉轉換演算法。因為radix-2/4/8演算法有其規律性和較低的硬體電路複雜度，故容易以VLSI實現，尤其是管線式架構的實現。為了要降低儲存旋轉因子的唯讀記憶體及複數乘法器所需佔用的晶片面積，我們使用一個稱為旋轉因子產生器的電路代替傳統的唯讀記憶體並設計一個雙倍工作頻率的複數乘法器。
這篇論文所提出的快速傅利葉轉換處理器是為802.16 (WiMAX) 的應用而設計。雖然它是為2048、1024、256及128點快速傅利葉轉換而設計的，但是透過在電路中增加一些多工器是可以將其變成可用於2048點以下所有點數的快速傅利葉轉換處理器。在最後，我們使用Xilinx Virtex-II FPGA晶片實現這個可變長度的快速傅利葉轉換單一延遲回授管線式架構。

In this paper, we propose a low cost and variable length FFT processor for the Orthogonal Frequency Division Multiplex (OFDM) communication systems. Radix-2/4/8 algorithm which can effectively minimize the number of complex multiplications is a popular split-radix FFT algorithm. Because radix-2/4/8 algorithm has regularity and the lowest hardware circuit complexity, it is easy to be implemented in VLSI, especially in the pipelined architecture. Using a twiddle factor generator instead of the conventional ROM, designing a time sharing complex multiplier and modifying real multiplier, the proposed FFT processor reduce the required chip area.
The proposed FFT processor is used to design for the 802.16(WiMAX) applications. Although it is designed for 2048、1024、256、128 points, it is easy to add the other points of FFT less than 2048 by using some multiplexers. Finally, we use Xilinx XC2V 1000 FG456 FPGA chip to implement this variable length FFT SDF architecture.

ACKNOWLEDGENTS................................................................I
ENGLISH ABSTRACT.............................................................II
CHINESE ABSTRACT............................................................III
TABLE OF CONTENTS............................................................IV
LIST OF TABLES...............................................................VI
LIST OF FIGURES.............................................................VII
CHAPTER
I INTRODUCTION.............................................................1
1.1 Background...........................................................1
1.2 Topics...............................................................6
II REVIEW OF SOME FFT ALGORITHMS...........................................7
2.1 Introduction.........................................................7
2.2 Basic Concepts of FFT Algorithms.....................................8
2.3 Decimation-in-Time (DIT) FFT Algorithms..............................9
2.3.1 Radix-2 DIT FFT Algorithm and Complexity.......................9
2.4 Decimation-in-Frequency (DIF) FFT Algorithms........................17
2.4.1 Radix-2 DIF FFT Algorithm and Complexity......................17
2.4.2 Radix-4/Radix- DIF FFT Algorithm and Complexity..............21
2.4.3 Radix-8/Radix- DIF FFT Algorithm and Complexity..............24
2.5 Split-Radix FFT (SRFFT) Algorithms..............................27
2.5.1 Split-Radix 2/4 FFT Algorithm and Complexity..................27
2.5.2 Split-Radix 2/8 FFT Algorithm and Complexity..................29
2.5.3 Split-Radix 2/4/8 FFT Algorithm and Complexity................32
2.6 Comparison and Summary..............................................34
III THE FFT PROCESSOR ARCHITECTURE........................................36
3.1 Introduction........................................................36
3.2 Pipeline-Based FFT Architecture.....................................36
3.2.1 Multiple-Path Delay Commutator Pipeline Architecture..........39
3.2.1.1 Radix-2 DIF MDC Structure...................................39
3.2.2 Single-Path Delay Feedback Pipeline Architecture..............41
3.2.2.1 Radix-2 DIF SDF Structure.............................41
3.2.3 Comparison of Pipeline Structures.............................43
3.3 Summary.............................................................45
IV PROPOSED FFT DESIGN....................................................46
4.1 Introduction........................................................46
4.2 Variable-length FFT Processor.......................................46
4.3 Radix-2/4/8 SDF architecture........................................49
4.3.1 Reduce the unnecessary complex multiplication.................49
4.3.2 Basic Architecture of Butterfly Unit..........................54
4.3.3 Twiddle Factor Generator......................................56
4.3.4 Design of Time Sharing Complex Multiplier.....................58
4.4 Simulation Result...................................................60
4.4.1 Simulation Result of Real and Complex Multiplication..........60
4.4.2 Simulation Result of Variable-length FFT......................62
4.4.3 Implementation Report of Variable-length FFT..................63
4.4.4 Implementation Result of Variable-length FFT..................66
V Conclusion and Future Work..............................................68
5.1 Conclusion..........................................................68
5.2 Future Work.........................................................68

REFERENCES...................................................................74

[1] A. Sadat and W. B. Mikhael, “Fast Fourier Transform for high speed OFDM
wireless multimedia system,” Proceedings of the 44th IEEE 2001 Midwest
Symposium on Circuits and Systems, pp.938 – 942, Vol.2 14-17, August 2001.
[2] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing,
Prentice-Hall Inc., 1999.
[3] 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.
[4] P. Dunamel and H. Hollmann, “Split Radix FFT Algorithm,” Electronics
Letters 5th Vol. 20 No. 1, January 1984.
[5] D. Takahashi,”An extended split-radix FFT algorithm,” IEEE Signal
Processing Letters, Issue. 5, Vol. 8, pp. 145-147, May 2001.
[6] Y. Jung, Y. Tak, J. Kim, J. Park, D. Kim, and H. Park, “Efficient FFT
Algorithm for OFDM Modulation,” proceedings of IEEE Region 10
International Conference on, Vol. 2 , pp.676-678, August 2001.
[7] L. Jia, Y. Gao, J. Isoaho, and H. Tenhunen, “A New VLSI – Oriented FFT
Algorithm and Implementation,” IEEE ASIC Conference, pp.337-341,
September 1998.
[8] B. G. Jo and M. H. Sunwoo, “New continuous-flow mixed-radix (CFMR) FFT
Processor using novel in-place strategy,” IEEE Transactions on Circuits
and Systems—I: Regular Papers, Vol. 52 pp. 337-341, September 1998.
[9] S. He and M. Torkelson, “A New Approach to Pipeline FFT Processor,”
Parallel Processing Symposium, The 10th International, pp. 766-770, 1996.
[10] S. He and M. Torkelson, “Designing Pipeline FFT Processor for OFDM (de)
Modulation,” URSI International Symposium on Signals, Systems and
Electronics, pp. 257-262, 1998.
[11] 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, February 2005.
[12] L. Dadda, “Some Schemes for Parallel Multipliers,” IEEE Trans. on
Electronic Computers, Vol. EC-13, pp. 14-17, February 1964.
[13] C. P. Hung, Design of Variable-Length FFT Processor, NCTU, Master Thesis,
2003.
[14] L. K. Tan and H. Samueli, “A 200 MHz Quadrature Digital
Synthesizer/Mixer in 0.8 m CMOS,” IEEE Journal of Solid-State Circuits,
vol. 30, No. 3, March 1995.
[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] F. A. Jalil, “M x N Booth Encoded Multiplier Generator Using Optimized
Wallace Trees,” IEEE Transactions on Very Large Scale Integration (VLSI)
Systems, vol. 1, No. 2, June 1993.