WiMAX(Worldwide Interoperability for Microwave Access全球互通微波存取)技術建立於IEEE 802.16標準上，而Wi-Fi無線相容認證技術建立於IEEE 802.11標準上的，其中IEEE 802.11n標準支援多重輸入多重輸出技術。WiMAX/IEEE 802.16標準及Wi-Fi/IEEE 802.11標準皆採用正交分頻多工(ODFM)技術，其擁有極佳的頻寬使用效率以及對抗非理想通道的能力，而在諸多調變方式中被視為熱門選擇。
快速傅立葉轉換處理器為所有正交分頻多工系統中的關鍵模組，為了適應不同應用，WiMAX中的規範主要有可調頻率及可變點數，而Wi-Fi需支援多重輸入多重輸出。然而這些技術的規範也為其關鍵模組的設計－一個支援雙重標準且可變點數與合理硬體成本的快速傅立葉轉換處理器，帶來極大挑戰。

在本論文中，我們提出一個擁有可變點數且高功率效率的快速傅立葉轉換處理器，主要是由4-path 128-point SDF(Single Delay Feedback) 模組與Multibutterfly模組所組合而成。Multibutterfly模組可以根據不同的快速傅立葉轉換的長度而操作radix-2、radix-2^2、radix-2^3、或radix-2^4的蝴蝶圖運算。4-path-SDF模組可以同時處理四個128點的快速傅立葉轉換，而且它有較快的操作速度與較高的輸出率以支援Wi-Fi標準。同時，一個有效率的記憶體存取方式被提出以及以常數乘法為基礎之乘法單元也被利用，可以有效地降低電路的複雜度、硬體面積及功率消耗。再者，一個新的多資料進位(Dynamic scaling)方法也在本論文中被使用，可以適時地截斷較長的字元長度而使資料的字元長度不會連續地增加。

整個可支援WiMAX與Wi-Fi雙重標準之快速傅立葉轉換處理器是使用UMC 90奈米製程所實現。面積是1,105,584 um^2。在20 MHz操作頻率下可運算12位元快速傅立葉轉換，而其功率消耗為6.84 mW，具有很高的功率效率。在2048點的快速傅立葉轉換下，SQNR為33.9247dB。而且只需要1.325N-word two-port的記憶體來完成連續流程的設計。因此，我們提出的快速傅立葉轉換處理器，針對未來同時支援全球互通微波存取系統及無線相容認證雙模式之實現，是一個極佳的解決方案。

WiMAX(Worldwide Interoperability for Microwave Access) and Wi-Fi are based on the IEEE 802.16 standard and the IEEE 802.11 standard, respectively with that the IEEE 802.11n standard supports Multiple-Input Multiple-Output (MIMO) technology. Both the WiMAX/IEEE 802.16 and the Wi-Fi/IEEE 802.11n standards have employed orthogonal frequency division multiplexing (OFDM) technology, that is regarded as a prospective modulation strategy, with great bandwidth efficiency and invulnerability to non-ideal channels.
FFT processor is the key module in the all OFDM communication systems. The specifications of WiMAX, scalable channel bandwidths by adjusting FFT size are employed for different applications, and Wi-Fi standard supports MIMO technology. However, it imposes a great challenge on the design of the key component, a dual mode Fast Fourier Transform (FFT) processor with acceptable hardware cost.

In this thesis, we propose a configurable and power-efficient FFT processor that is composed of the 4-path-SDF module and the multibutterfly module. The multibutterfly module can operate the radix-2, radix-2^2, radix-2^3, or radix-2^4 butterfly according to different FFT sizes. The 4-path-SDF module can deal with simultaneously the four 128-point FFTs with faster operation speed and higher throughput. Besides, an efficient memory-accessing scheme is proposed and a constant-based multiplier unit is adopted to achieve low complexity, small hardware area, and lower power consumptions. Also, the dynamic scaling method is adopted in the proposed architecture, which can truncate timely the longer word-length such that the word-lengths of data are not increased continuously.

The proposed FFT processor, supporting two kinds of wireless communication system standards Wi-Fi (IEEE 802.11n) and WiMAX (802.16e), is implemented by using Faraday 90nm cell library in a UMC 90nm 1P9M CMOS process. The word-length, area in gate level simulation, and power are, respectively, 12 bits, 1,105,584 um^2, and 6.84mW at 20MHz. The SQNR is 33.9247dB when performing the 2048-point FFT. And it only needs 1.325N-word two-port memory, where N is 2048, for continuous flow design. Therefore, the proposed FFT processor is a promising solution to the implementation of OFDM-based WiMAX and Wi-Fi systems in the future.

Chapter 1 Introduction 1
1.1 Introduction 1
1.2 Previous Works 3
1.3 Motivation 3
1.4 Thesis Organization 6
Chapter 2 Algorithms of Fast Fourier Transform 7
2.1 Introduction of Fast Fourier Transform Algorithms 7
2.2 Radix-2 Fast Fourier Transform Algorithm 8
2.2.1 Radix-2 Decimation-In-Frequency Fast Fourier Transform Algorithm 8
2.2.2 Radix-2 Decimation-In-Time Fast Fourier Transform Algorithm 13
2.2.3 Comparison between Decimation-In-Frequency and Decimation-In-Time Fast Fourier Transform Algorithm 16
2.3 Radix-2^2 Fast Fourier Transform Algorithm 16
2.4 Radix-2^3 Fast Fourier Transform Algorithm 18
2.5 Data Order 20
2.6 Algorithm of Proposed FFT Processor 21
2.6.1 DFT of 2048-Point FFT 21
2.6.2 DFT of 16-Point FFT 23
2.6.3 DFT of 128-Point FFT 25
2.7 Summary 28
Chapter 3 Architectures of Fast Fourier Transform 29
3.1 Introduction of Fast Fourier Transform Architectures 29
3.2 Pipelined Fast Fourier Transform Architectures 30
3.2.1 Radix-2 SDF (R2SDF) FFT architecture 30
3.2.2 Radix-2^2 SDF (R2^2SDF) FFT architecture 34
3.2.3 Radix-2^3 SDF (R2^3SDF) FFT architecture 35
3.3 Memory-Based Fast Fourier Transform Architectures 35
3.4 Summary 37
Chapter 4 Proposed FFT Processor 38
4.1 Overview of Proposed FFT Processor 38
4.1.1 Wi-Fi Mode 40
4.1.2 WiMAX Mode 40
4.2 Hardware Architecture of the Proposed FFT Processor 46
4.3 Multibutterfly Unit 49
4.3.1 Radix-2/2^2 Butterfly4 Unit 50
4.3.2 Dynamic Scaling Unit with Exponent (EXP) Unit 53
4.3.3 Fixed Width Canonic Signed Digit (CSD) Multiplier 54
4.3.4 General Complex Multiplier 58
4.3.5 Twiddle Factor Table 59
4.4 4-Path 128-Point Single Data Feedback (SDF) Unit 61
4.5 Memory Access 62
4.5.1 Input and Output Memory 62
4.5.2 Continuous Flow Design 68
4.6 Word-length Assignment of Proposed FFT Processor 76
4.7 Data Order of Proposed FFT Processor 78
4.8 Summary 78
Chapter 5 Simulation Results and Comparisons 80
5.1 Design Flow and Design Tools 80
5.2 Fixed-Point Analysis 81
5.3 Memory Analysis 82
5.4 Comparisons 83
5.5 Specifications of Proposed FFT Processor 84
Chapter 6 Conclusions and Future Works 86
6.1 Conclusions 86
6.2 Future Works 87

[1] M. Simek, I. Mica, J. Kacalek, and R, Burget, “Bandwidth Efficiency of Wireless Networks of WPAN WLAN WMAN and WWAN,” Electrotechnic Magazine ISSN 1213-1539, Aug. 2008.
[2] http://www.wi-fi.org/
[3] http://www.wimaxforum.org/
[4] http://www.ieee802.org/15/pub/TG3a.html
[5] L. G. Johnson, “Conflict free memory addressing for dedicated FFT hardware,” IEEE Trans Circuits Syst. II., Analog Digit. Process., vol39, no. 5, pp. 312-316, May 1992.
[6] B. M. Bass, “A Low-power, High-performance, 1024-point FFT processor,” IEEE Journal of Solid-State Circuits, vol. 34, no.3, pp. 380-387, March. 1999.
[7] D. Veithen, P. Spruyt, T. Pollet, M. Peeters, S. Braet, O. V. D. Wiel, and H. V. D. Weghe, “A 70 Mb/s variable-rate DMT-based modem got VDSL,” in Proc. IEEE Intl. Solid-State Circuits Conf., pp. 248-249, 1999.
[8] B.G. Jo and M.H. Sunwoo, “New Continuous-flow Mixed-radix (CFMR) FFT Using Novel In-place Strategy,” IEEE Trans. on Circuits Syst., vol. 52, no. 5, pp. 911-919, May. 2005.
[9] Y.-W. Lin, H.-Y. Liu, and C.-Y. Lee, “A dynamic scaling FFT processor for DVB-T applications,” IEEE J. Solid-State Circuits, vol. 39, no. 11, pp. 2005–2013, Nov. 2004.
[10] 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.
[11] S. He and M. Torkelson, “Designing pipeline FFT processor for OFDM (de)modulation,” in Proc. URSI Int. Symp. Signals, Systems, and Electronics, vol. 29, pp. 257–262, 1998.
[12] H.-Y. Lee and I.-C. Park, “Balanced Binary-Tree Decomposition for Area-Efficient Pipelined FFT Processing,” IEEE Trans. on Circuits and Systems, Part-I: Regular Papers, vol. 54, no. 4, pp. 889–900, Apr. 2007.
[13] S.-M. Kim, J.-G. Chung and K. K. Parhi, “Low error fixed-width CSD multiplier with efficient sign extension,” IEEE Trans. on Circuits and Systems, Part-II: Analog and Digital Signal Processing, vol. 50, no. 3, pp. 984–993, Dec. 2003.
[14] C.-L. Wey, S.-Y. Lin, W.-C. Tang, and M.-T. Shiue, “High-speed, Low Cost Parallel Memory-Based FFT Processors for OFDM Applications,” in Proc. 14th IEEE Int’l Conf. Electronics, Circuits and Systems (ICECS), pp. 783-787, 2007.
[15] C.-L. Wey, S.-Y. Lin, and W.-C. Tang, “Efficient Memory-Based FFT Processors for OFDM Applications,” in Proc. IEEE Int’l Conf. on EIT, pp.345-350, 2005.
[16] Y. Chen, Y.W. Lin, and C.Y. Lee, “A Block Scaling FFT/IFFT Processor for WiMAX Applications,” in Proc. IEEE Asian Solid-State Circuits Conf., pp. 203-206, 2006.
[17] C.-L. Hung, S.-S. Long, and M.-T. Shiue, “A Low Power and Variable-Length FFT Processor Design for Flexible MIMO OFDM Systems,” in Proc. IEEE Circuits and Syst. Symp., pp.705-708, 2009.
[18] J.-Y. Oh, and M.-S. Lim, “Area and Power Efficient Pipeline FFT Algorithm,” in Proc. IEEE Signal Processing Systems Design and Implementation Workshop, pp. 520-525, 2005.
[19] H. Shousheng and M. Torkelson, “Designing pipeline FFT processor for OFDM (de)modulation,” in Proc. Int’l. Symp. Signals, Syst., and Electronics, vol. 29, pp. 257–262, 1998.
[20] Y.-T. Hwang, Y.-J. Chen, W.-D. Chen," Scalable FFT kernel designs for MIMO OFDM based communication systems ", in Proc. IEEE Region 10 Conf. (TENCON), pp. 1-4, 2007.