正交分頻多工系統(OFDM)近幾年來已被廣泛的應用在許多先進的數位訊號處理應用中。由於它提供一個有效的方法來消除多路徑環境下的衰減，因此正交分頻多工系統的運算複雜度也比傳統的分頻多工系統(FDM)相對的提高。 雖然快速傅立葉轉換處理器在正交分頻多工系統中有很重要的地位，然而它也是在系統中耗費最多硬體資源及擁有高運算複雜度的模組。
在IEEE 802.16 e的規格中，快速傅立葉轉換處理器必需能支援 128、512、1024、2048 點的傅立葉轉換，且能使用在多輸入多輸出(multiple-input multiple output)的系統中。然而隨著天線數的增多，使用傳統的方法將使得快速傅立葉轉換處理器的各數隨著天線數增多，如此將會大幅增加晶片的面積。本篇論文即是將四個平行的傅立葉轉換處理器做了改良，利用資源共享的方式，將原本需要四個處理器的架構變成只需要用一個，不用大幅增加硬體的複雜度，卻可達到減小面積的目標。
此外，我們使用單延遲回授的傅立葉轉換器的架構搭配二的三次方基數演算法以及二的四次方的基數演算法來設計，以減少複數成法器的數目。而在複數乘法器以及記憶體的讀寫上也做了改良，已達到降低面積與功率損耗的目標。

Contents

LIST OF FIGURES……..…………………………………...…………...................III
LIST OF TABLES………………………………………..............................................V
CHAPTER 1 INTRODUCTION………………………......................……….……....1
1.1 OFDM Introduction.........................................................................................1
1.2 The Motivation................................................................................................3
CHAPTER 2 REVIEW OF FFT ALGORITHM AND ARCHITECTURE..............4
2.1 The FFT Algorithm.........................................................................................4
2.1.1 Decimation-in-Time (DIT) FFT Algorithm...............................................4
2.1.1.2 Radix-2 DIT FFT Algorithm..............................................................4
2.1.1.2 Radix-4 DIT FFT Algorithm..............................................................7
2.1.2 Decimation-in-Frequency FFT Algorithm................................................8
2.1.2.1 Radix-2 DIF FFT Algorithm…..........................................................8
2.1.2.2 Radix-4 DIF FFT Algorithm…..........................................................9
2.1.3 Mixed-Radix FFT Algorithm................................................................10
2.2 The Pipelined FFT Architecture................................................................11
2.2.1 The SDF Pipelined FFT Architecture..................................................11
2.2.1.1 Radix-2 SDF Pipelined FFT Architecture (R2SDF).................11
2.2.1.2 Radix- SDF Pipelined FFT Architecture (R SDF)...........12
2.2.1.3 Radix- SDF Pipelined FFT Architecture (R SDF)............13
2.2.2 The MDC Pipelined FFT Architecture................................................13
2.2.2.1 Radix-2 MDC Pipelined FFT Architecture (R2MDC).............13
2.2.2.2 Radix-4 MDC Pipelined FFT Architecture...............................14
2.2.3 Comparison of Various Pipelined FFT Architecture..........................15
CHAPTER 3 THE FFT ALGORITHM FOR WIMAX APPLICATIONS......16
3.1 Introduction.......................................................................................................16
3.2 Radix- DIF Algorithm................................................................................17
3.3 Radix- DIF Algorithm...............................................................................21
3.4 Modified Radix- DIF Algorithm..............................................................25
CHAPTER 4 HARDWARE IMPLEMENTATION...............................................28
4.1 Introduction.....................................................................................................28
4.2 The Proposed Architecture............................................................................29
4.2.1 Parallel-to-Serious With Input Buffer..................................................30
4.2.2 Parallel-to-Serious Without Input Buffer.............................................31
4.2.3 Scalable FFT for Wimax Specification..............................................32
4.3 Hardware implementation.............................................................................34
4.3.1 Constant Multiplier Architecture.............................................34
4.3.2 CSD Constant Multiplier Architecture.....................................36
4.3.3 Complex Multiplier Architecture........................................................39
4.3.3.1 Using in the R SDF Architecture...........................................39
4.3.3.2 Using Between The R SDF and R SDF Architecture.......44
4.3.4 The SDF Architecture Using Two Single-port SRAM...................46
CHAPTER 5 SIMULATION AND IMPLEMENTATION RESULT.................47
5.1 The Effect of Finite Word Length..........................................................47
5.2 Comparison.................................................................................................52
5.3 Conclusion..................................................................................................54



List of Figures

Fig 1.1：Concept for FDM and OFDM signal.................................................................2
Fig 1.2：A simplified model of a OFDM system.............................................................2
Fig 1.3：MIMO-OFDM system.......................................................................................3
Fig 2.1：The butterfly unit of a radix-2 DIT FFT algorithm............................................6
Fig 2.2：SFG of 8-point FFT............................................................................................6
Fig 2.3：The butterfly of radix-4 DIT FFT algorithm......................................................7
Fig 2.4：The butterfly of radix-2 DIF FFT algorithm......................................................9
Fig 2.5：The butterfly of radix-4 DIF FFT algorithm....................................................10
Fig 2.6：Block diagram of 16-point R2SDF pipelined architecture..............................12
Fig 2.7：Block diagram of 16-point R SDF pipelined architecture............................12
Fig 2.8：Block diagram of 64-point R SDF pipelined architecture............................13
Fig 2.9：Block diagram of 16-point R2MDC pipelined architecture.............................14
Fig 2.10：Block diagram of 64-point R4MDC pipelined architecture...........................14
Fig 3.1：The SFG of radix- FFT................................................................................19
Fig 3.2：The SFG of the radix- FFT.........................................................................23
Fig 3.3：The SFG of the modified radix- FFT..........................................................26
Fig 4.1：Parallel FFT architecture..................................................................................29
Fig 4.2：Block diagram of the proposed scalable FFT...................................................29
Fig 4.3：Timing diagram for P/S with input buffer........................................................31
Fig 4.4：Timing diagram for P/S without input buffer..................................................32
Fig 4.5：A block diagram of the simplified architecture...............................................32
Fig 4.6：The block diagram of multiplier.........................................................34
Fig 4.7：The modified block diagram of multiplier..........................................35
Fig 4.8：An example for 1/ multiplication..............................................................35
Fig 4.9：Block diagram of 0.9239 multiplier.................................................................38
Fig 4.10：Block diagram of 0.3827 multiplier................................................................39
Fig 4.11：Two complex multipliers using in the R SDF architecture........................39
Fig 4.12：The type I block diagram of the complex multiplier......................................41
Fig 4.13：Example of modified complex multiplier operations in every time slot........42
Fig 4.14：The type II block diagram of the complex multiplier.....................................43
Fig 4.15：Two complex multipliers using between the R SDF and R SDF
Architecture...................................................................................................44
Fig 4.16：Twiddle factors are separated into eight regions............................................45
Fig 4.17：The radix-2 SDF architecture using dual-port SRAM...................................46
Fig 4.18：The radix-2 SDF architecture using two single-port SRAM.........................47
Fig 5.1：Block diagram of SQNR calculator.................................................................49
Fig 5.2：The SQNR vs Coefficient word length for various input word length
(N = 2048).......................................................................................................50
Fig 5.3：The SQNR vs Coefficient word length for various input word length
(N = 1024).......................................................................................................50
Fig 5.4：The SQNR vs Coefficient word length for various input word length
(N = 512).........................................................................................................51
Fig 5.4：The SQNR vs Coefficient word length for various input word length
(N = 128).........................................................................................................51




List of Tables

Table 2.1：Comparison of the complexity in the pipelined FFT architecture................15
Table 4.1：The operations of the scalable FFT...............................................................33
Table 4.2：Twiddle factor of ..................................................................................36
Table 4.3：CSD representation.......................................................................................37
Table 4.4：Scheduling of the Twiddle factor for Type I.................................................40
Table 4.5：Scheduling of the twiddle factor for type II complex multiplier..................42
Table 4.6：The mapping table used to decide the values of the twiddle factors............45
Table 5.1：Synthesis result..............................................................................................53
Table 5.2：Comparison of various 2048-points FFT processor......................,...............53

[1] Yu-Wei Lin and Chen-Yi Lee, “The Study of FFT Processors for OFDM System,” Institute of Electronics College of Electrical Engineering and Computer Engineering, NCTU, Hsinchu, Taiwain, November 2005

[2] Yu-Wei Lin, Hsuan-Yu Liu, and Chen-Yi Lee, “A Dynamic Scaling FFT processor for DVB-T Applications,” IEEE Journal of Solid-State Circuits, vol. 39 , No. 11, pp 2005-2013 November 2004.

[3] Shousheng He, and M. Torkelson, “Designing pipelined FFT processor for OFDM (de)modulation” USRI International Symposium on Signals, Systems, and Electronics, vol.29, pp.257-262, October 1998.

[4] Ludwig Schwoever and Ernst Zielinski, “Optimized FFT Architecture for MIMO Applications” Nokia Research Center.

[5] Hsieh-Han Chiang, and Jen-Ming Wu, “Low Power and High Speed FFT Design for UWB,” Institute of Communication Engineering NTHU, Hsinchu, Taiwan, July 2006

[6] Yuan Chen, Yu-Wei Lin, and Chen-Yi Lee, “A Block Scaling FFT/IFFT
Processor for WiMAX Applications,” IEEE Solid-State Circuits
Conference, pp.202-206, Nov. 2006.

[7] G. Zhong, F. Xu, and A. N. Willson Jr., “A power-scalable reconfigurable FFT /IFFT IC based on a multi-processor ring,” IEEE J. Solid-State Circuits, vol. 41, pp. 483-495, Feb. 2006.

[8] Y.-T. Lin, P.-Y. Tsai, and T.-D. Chiueh, “Low-power variablelength
fast Fourier transform processor,”In Proc. Comput. Digit. Tech., vol. 152, No. 4, pp. 499-506, July 2005.

[9] B. M. Bass, “A low-power, high-performance, 1024-point FFT processor,” IEEE. Solid-State Circuits, vol. 34, pp. 380-387, Mar. 1999.

[10] K. Maharatna, E. Grass, and U. Jagdhold, “A 64-point Fourier transform chip for high-speed wireless LAN application using OFDM,” IEEE J. Solid-State Circuits, vol. 39, pp. 484-493, Mar. 2003.

[11] Yi-Wei Lin and Chen-Yi Lee, “Design of an FFT/IFFT Processor for MIMO OFDM Systems,” IEEE Transactions on Circuits and Systems, vol. 54, no. 4, April 2007.

[12] C. Huggett, K. Maharatna and K. Paul, “On the implementation of 128-pt FFT/IFFT for high-performance WPAN,”IEEE Circuits and Systems, vol.6 pp 5513-5516, 23-26 Mat 2005.