現今，無線通訊系統在人們的生活當中扮演非常重要的角色。而因應越來越龐大的多媒體資料傳輸需求，相繼衍生出多種通訊技術，其中多輸入多輸出與正交分頻多工技術，被廣泛的使用。而快速傅立葉轉換處理器在所有多輸入多輸出正交分頻多工的通訊系統中是關鍵性的模組。因而，快速傅立葉轉換處理器必須有處理多個平行資料序列的能力。在傳統上是採用多個快速傅立葉轉換處理器來處理多個平行資料序列，但是會造成較差的硬體效率與較高的功率消耗。因此，將多個快速傅立葉轉換處理器整合在一起，達到硬體資源共享，以提高硬體效率與降低功率消耗是現今的趨勢。
在本篇論文中，我們提出一個基於增強的IEEE 802.11n標準之應用於多輸入多輸出正交分頻多工系統之高硬體效率快速傅立葉轉換處理器。此處理器是採用MRM^2DF(Mixed-Radix Mixed-Multipath Delay Feedback)架構，其使用多資料路徑結構來提供高輸出率，並且採用radix-2和radix-2^3演算法來降低硬體複雜度。此外利用保護區間來增加處理兩條平行資料序列的能力。因此平行路徑的數目從四條延伸至六條，且採用共用硬體資源的方法來降低硬體面積和功率消耗。我們使用UMC 90-nm 1P9M製程實現所提出的處理器，其面積為739 x 734 (um)^2，且在40MHz的操作頻率下消耗功率為5.57 mW，SQNR為40.17dB。此處理器符合增強的IEEE 802.11n標準，能在40MHz的操作頻率下，同時處理在3.2us內的六條獨立的FFT資料序列。

Wireless communication plays a significant role in people’s life nowadays, and the response to an ever-growing demand for multimedia data transmission, have spawned a variety of communications technologies, including multiple-input multiple-output (MIMO), orthogonal frequency division multiplexing (OFDM) technology, has been widely used. The FFT Processor is the key module in the all MIMO OFDM communication systems. Therefore, the FFT processor must have the capacity of dealing with the simultaneous multiple data sequences. Adopting several FFT processors to process the simultaneous multiple data sequences, the traditional approach results in lower hardware efficiency and higher power consumption. Therefore, multiple FFT processors integrated to achieve the sharing of hardware resources in order to increase hardware efficiency and to reduce power consumption are the current trend.
In this thesis, we proposed a hardware-efficient 128-point FFT processor for the applications in a MIMO OFDM based enhancement of IEEE 802.11n standard. Our processor is adopts the mixed-radix mixed-multipath delay feedback (MRM^2DF) architecture, which provides a higher throughput rate by using the multi-data path scheme, and radix-2 and radix-2^3 algorithm are adopted to reduce hardware complexity. Furthermore, it utilizes the guard interval to increase the capacity of dealing with two parallel data sequences. Thus, the number of parallel paths is extended from four to six. The proposed FFT processor is implemented in UMC 90-nm 1P9M process with core area of 739 x 734 (um)^2 including an FFT processor and a test module. The power consumption is 5.57 mW at 40MHz operating frequency, and SQNR is 40.17dB. At the operation clock rate of 40Mhz, our proposed processor can calculate 128-point FFT with six independent data sequences within 3.2 us meeting the enhancement of IEEE 802.11n standard requirements.

中文摘要----I
ABSTRACT----II
致謝----III
CONTENTS----IV
LIST OF FIGURES----VI
LIST OF TABLES----VIII
CHAPTER 1 INTRODUCTION----1
1.1 INTRODUCTION----1
1.2 MOTIVATION----1
1.3 ORGANIZATION OF THE THESIS----2
CHAPTER 2 ALGORITHMS OF FAST FOURIER TRANSFORM----3
2.1 INTRODUCTION----3
2.2 TWIDDLE FACTOR----4
2.3 THE RADIX-2 FFT ALGORITHM----6
2.3.1 The Radix-2 DIT FFT algorithm----6
2.3.2 The Radix-2 DIF FFT algorithm----10
2.3.3 Comparison of the DIT and DIF FFT algorithm----13
2.4 THE RADIX-4 DIF FFT ALGORITHM----13
2.5 THE RADIX-8 DIF FFT ALGORITHM----17
2.6 THE RADIX-22 DIF FFT ALGORITHM----19
2.7 THE RADIX-23 DIF FFT ALGORITHM----22
2.8 THE RADIX-24 DIF FFT ALGORITHM----23
2.9 COMPARISONS AND SUMMARY----24
CHAPTER 3 ARCHITECTURES OF FAST FOURIER TRANSFORM----26
3.1 INTRODUCTION----26
3.2 SINGLE-PATH DELAY FEEDBACK PIPELINED ARCHITECTURE----26
3.2.1 The R2SDF Architecture----26
3.2.2 The R4SDF Architecture----28
3.2.3 The R8SDF Architecture----29
3.2.4 The R22SDF Architecture----30
3.3 MULTIPATH DELAY COMMUTATOR PIPELINED ARCHITECTUR----31
3.3.1 The R2MDC Architecture----32
3.3.2 The R4MDC Architecture----33
3.3.3 The R8MDC Architecture----33
3.3.4 The R22MDC Architecture----34
3.4 COMPARISON OF PIPELINED ARCHITECTURE----34
CHAPTER 4 PROPOSED FFT PROCESSOR FOR MIMO OFDM SYSTEMS----36
4.1 OVERVIEW OF PROPOSED FFT PROCESSOR----36
4.2 ALGORITHM FOR PROPOSED FFT PROCESSOR----37
4.3 CSD CONSTANT MULTIPLIER----40
4.4 MODULE I----42
4.5 MODULE II----44
4.6 MODULE III----51
4.7 MODULE IV----56
4.8 SUMMARY----57
CHAPTER 5 SIMULATION RESULTS AND COMPARISONS----58
5.1 SIMULATION RESULTS----58
5.2 COMPARISONS----61
CHAPTER 6 CONCLUSION AND FUTURE WORK----63
BIBLIOGRAPHY----64

[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]S. Magar, S. Shen, G. Luikuo, M. Fleming, and R. Aguilar, “An Application Specific DSP Chip Set for 100MHz Data Rates,” in Proc. Int. Conf. Acoustics, Speech, and Signal Processing, vol. 4, pp. 1989-1992, Apr. 1988.
[3]H. Shousheng and M. Torkelson, “Designing Pipeline FFT Processor for OFDM (De)modulation,” in Proc. Int. Symp. Signals, Syst., and Electronics, vol. 29, pp. 257-262, Oct. 1998.
[4]J. O’Brien, J. Mather, and B. Holland, “A 200 MIPS Single-Chip 1k FFT Processor,” in Proc. IEEE Int. Solid-State Circuits Conf. Dig. Tech. Papers, vol. 36, pp. 166-167, 1989.
[5]B. M. Bass, ”A Low-Power, High-Performance, 1024-Point FFT Processor,” IEEE J. Solid-State Circuits, vol. 34, no. 3, pp. 380-387, Mar. 1999.
[6]E.H. Wold and A.M. Despain, “Pipeline and Parallel-Pipeline FFT Processors for VLSI Implementation,” IEEE Trans. Comput., vol.C-33, no.5, pp. 414-426, May 1984.
[7]A.M. Despain, “Fourier Transform Computer Using CORDIC Iterations,” IEEE Trans. Comput., vol. C-23, no. 10, pp. 993-1001, Oct. 1974.
[8]A. V. Oppenheim and R. W. Schafer, “Discrete-Time Signal Processing,” Prentice-Hall, Inc., NJ, 1999.
[9]L. R. Rabiner and B.Gold, “Theory and Application of Digital Signal Processing,” Prentice-Hall, Inc., NJ, 1975.
[10]H.T. Wang, “Design of Fast Fourier Transform in MIMO OFDM System,” Master thesis, Dept. EE, National Tsing Hua University, 2007.
[11]S.-M. Kim, J.-G. Chung, and K.K. Parhi, ”Low Error Fixed-Width CSD Multiplier with Efficient Sign Extension,” IEEE Trans. Circuits Syst. II, vol. 50, no. 12, pp. 984-993, Dec. 2003.
[12]Y.W. Lin and C.Y. Lee, “Design of an FFT/IFFT Processor for MIMO OFDM Systems,” IEEE Transactions on Circuits and Systems, vol. 54, no. 4, pp. 807-815, April 2007.
[13]Y.W. Lin, H.Y. Liu, and C.Y. Lee, “A 1GS/s FFT/IFFT Processor for UWB Applications,” IEEE J. Solid-State Circuits, vol.40, no. 8, pp.1726-1735, Aug. 2005.
[14]K. Maharatna, E. Grass, and U. Jagdhold, “A 64-Poing Fourier Transform Chip for High-Speed Wireless Lan Application Using OFDM,”IEEE J. Solid-State Circuits, vol.39, no.3, pp. 484-293, Mar. 2004.