With the lifestyle changes, the wireless communication plays an important role in our life. The orthogonal frequency division multiplexing (OFDM) has excellent bandwidth efficiency and invulnerability to non-ideal channels, so it usually applies in the wireless communication system. And the fast Fourier transform (FFT) is the key module for the hardware implementation of OFDM.
In this thesis, a high efficient FFT processor is proposed. The FFT processor supports two systems, WiMAX and WLAN, and resolves the difference of two wireless communication systems in an efficient way. For an efficient transformation of two systems, the multi-path delay feedback (MDF) is introduced into the memory-based architecture. To lower the power consumption, the interleave cache is proposed. With the employed FFT algorithm, interleave cache reduces not only the power consumption but also the hardware cost of non-trivial multiplication. And the main memory, a more complex memory control is used to gain higher hardware efficient and lower power consumption.
The proposed FFT processor is implemented by TSMC 0.18um process, and the area is 4.177mm2. The power consumption is 37.39mW in the WiMAX application, and 69.39mW in the WLAN application. The WiMAX processes two-stream 2048 point FFTs at 20MHz, and the WLAN processes 4-stream 128 point FFTs at 40MHz.

隨著時代的演進，無線通訊在人類生活中占有其重要性。正交分頻多工(OFMD)擁有極佳的頻寬使用效率以及對抗非理想通道的能力，因此經常的使用在無線通訊技術當中。而快速傅立葉轉換(FFT)則是使正交分頻多工在硬體實現方面最重要的關鍵。
在本論文中，提出一個高效率的快速傅立葉轉換處理器。此快速傅立葉轉換處理器支援WiMAX以及WLAN兩種不同的無線通訊系統，也有效率的解決兩個無線通訊系統之間的差異。為了有效率的在兩系統之間轉換，一個多路徑延遲回授(multi-path delay feedback)架構引進於一個以記憶體為基礎(memory-based)的快速傅立葉轉換處理器。在降低功率消耗方面，一個分離式快取(interleave cache)記憶體的提出使用，配合所使用的演算法，不僅僅可降低功率消耗，也可以降低複數乘法器的使用。至於主要記憶體部分，利用較複雜的記憶體存取方式來爭取較高的硬體使用效率以及較低的功率消耗。
此快速傅立葉轉換處理器是使用TSMC 0.18um製程，其面積為4.177mm2。在功率消耗方面， WiMAX的應用是處理操作在20MHz兩路徑2048點FFT運算，其為37.39mW，而WLAN應用是處理操作在40MHz四條路徑128點FFT運算，其為69.39mW。

CONTENT I
List of Figures III
List of Tables V
Chapter 1 Introduction 1
1.1 Introduction 1
1.2 Previous Work 2
1.3 Motivation 5
1.4 Thesis Organization 6
Chapter 2 FFT/IFFT Algorithm 7
2.1 The Algorithm of 2048-point FFT 7
2.1.1 The decomposition of 2048-point DFT 7
2.1.2 The decomposition of inner 64-point DFT 9
2.1.3 The decomposition of outer 32-point DFT 10
2.2 The Algorithm of Inverse FFT (IFFT) 12
2.3 Summary 13
Chapter 3 Proposed Architecture 14
3.1 The Overview of Proposed FFT Architecture 14
3.2 Kernel (processing element) 15
3.2.1 The Implementation of Algorithm 15
3.2.2 The Overview of Kernel 16
3.2.3 4-path MDF 20
3.2.4 The Multiplier Simplification for the Parallel-path 20
3.2.5 Complex multiplication 26
3.2.6 Multi-data scaling 27
3.2.7 The Data Flow of Radix-26 28
3.2.8 The Data Flow of Radix-25 31
3.2.9 The Interleave Cache and Brief Summary 32
3.3 The Main Memory and Control 33
3.3.1 The Overview of Main Memory 33
3.3.2 Memory Type 34
3.3.3 The Analysis of Main Memory 35
3.3.4 The Memory Arrangement 37
3.3.5 Summary 43
3.4 The Transformation of WLAN Mode 44
3.4.1 The WLAN Mode Overview 44
3.4.2 The Implementation of WLAN 45
3.4.3 The Memory Arrangement for WLAN 47
3.5 Summary 48
Chapter 4 Simulation results 50
4.1 Simulation results 50
4.2 Comparisons 52
Chapter 5 Conclusions 55
5.1 Conclusions 55
5.2 Future Works 56
Reference 57

[1] H. Shousheng and M. Torkelson, “Designing pipeline FFT processor for OFDM (de)modulation," URSI International Symposium on Signals, Systems, and Electronics, pp. 257-262, 1998.
[2] J. Y. Oh and M. S. Lim, “Area and power efficient pipeline FFT algorithm," IEEE Workshop on Signal Processing Systems Design and Implementation, pp. 520-525, 2005.
[3] Y. W. Lin, H. Y. Liu, and C. Y. Lee, "A 1-GS/s FFT/IFFT processor for UWB applications," IEEE Journal of Solid-State Circuits, vol. 40, pp. 1726-1735, 2005.
[4] L. Liu, J. Y. Ren, X. J. Wang, and F. Ye, "Design of Low-Power, 1GS/s Throughput FFT Processor for MIMO-OFDM UWB Communication System," IEEE International Symposium on Circuits and Systems, pp. 2594-2597, 2007.
[5] M. Shin and H. H. Lee, "A high-speed four-parallel radix-24 FFT/IFFT processor for UWB applications," IEEE International Symposium on Circuits and Systems, pp. 960-963, 2008.
[6] L. G. Johnson, "Conflict free memory addressing for dedicated FFT hardware," IEEE Transactions on Circuits and Systems II, vol. 39, pp. 312-316, 1992.
[7] D. Veithen, P. Spruyt, T. Pollet, M. Peeters, S. Braet, O. Van de Wiel, and H. Van De Weghe, "A 70 Mb/s variable-rate DMT-based modem for VDSL," IEEE International Solid-State Circuits Conference, pp. 248-249, 1999.
[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, vol. 52, pp. 911-919, 2005.
[9] R. Radhouane, P. Liu, and C. Modlin, "Minimizing the memory requirement for continuous flow FFT implementation: continuous flow mixed mode FFT (CFMM-FFT)," IEEE International Symposium on Circuits and Systems, vol. 1, pp. 116-119 vol.1, 2000.
[10] B. M. Baas, "A low-power, high-performance, 1024-point FFT processor," IEEE Journal of Solid-State Circuits, vol. 34, pp. 380-387, 1999.
[11] C. L. Hung, S. S. Long, and M. T. Shiue, "A low power and variable-length FFT processor design for flexible MIMO OFDM systems," IEEE International Symposium on Circuits and Systems, pp. 705-708, 2009.

[12] S. N. Tang, J. W. Tsai, and T. Y. Chang, "A 2.4-GS/s FFT Processor for OFDM-Based WPAN Applications," IEEE Transactions on Circuits and Systems II, vol. 57, pp. 451-455, 2010.
[13] Y. W. Lin, H. Y. Liu, and C. Y. Lee, "A dynamic scaling FFT processor for DVB-T applications," IEEE Journal of Solid-State Circuits, vol. 39, pp. 2005-2013, 2004.
[14] Y. Chen, Y. W. Lin, and C. Y. Lee, "A Block Scaling FFT/IFFT Processor for WiMAX Applications," IEEE Asian Solid-State Circuits Conference, pp. 203-206, 2006.
[15] Y. Chen, Y. C. Tsao, Y. W. Lin, C. H. Lin, and C. Y. Lee, "An Indexed-Scaling Pipelined FFT Processor for OFDM-Based WPAN Applications," IEEE Transactions on Circuits and Systems II, vol. 55, pp. 146-150, 2008.
[16] H. Y. Lee and I. C. Park, "Balanced Binary-Tree Decomposition for Area-Efficient Pipelined FFT Processing," IEEE Transactions on Circuits and Systems I, vol. 54, pp. 889-900, 2007.
[17] S. M. Kim, J. G. Chung, and K. K. Parhi, "Low error fixed-width CSD multiplier with efficient sign extension," IEEE Transactions on Circuits and Systems II, vol. 50, pp. 984-993, 2003.
[18] G. C. Zhong, F. Xu, and A. N. Willson, Jr., "A power-scalable reconfigurable FFT/IFFT IC based on a multi-processor ring," IEEE Journal of Solid-State Circuits, vol. 41, pp. 483-495, 2006.