在目前的無線通訊系統中，快速傅立葉轉換(fast Fourier transformation, FFT)常被使用於正交分頻多工系統(orthogonal frequency division multiplexing, OFDM)中作為訊號處理的機制。而無線通訊系統的規格中，常使用可變長度的快速傅立葉轉換以因應不同的通道環境。因此以較低的硬體成本設計可變長度的傅立葉轉換處理器是值得探討的研究方向。
3GPP-LTE系統是下一代通訊規格中主要的規格之一，然而傳統適用於二的冪次方點數的設計方法並不適用在規格所規範的1536點的傅立葉轉換上。因此本論文提出了以較低成本硬體實現適用於3GPP-LTE規格之可變長度傅立葉轉換處理器的設計。除了針對記憶體位址產生器進行改良以避免1536點的記憶體模組衝突的問題，並且在運算單元上能夠與其他二的冪次方點數的運算達到最大的硬體共用。為了減省運算1536點的傅立葉轉換所需額外使用的旋轉因子，索引編碼(index mapping)的技術也納入設計的考量中。本論文所提出之可變長度傅立葉轉換處理器在TSMC 0.18 μm的製程，且操作頻率為100MHz的條件下所需要的等效邏輯閘數為24k。

Fast Fourier transform (FFT) is the primary digital signal processing operation in orthogonal frequency division multiplexing (OFDM) systems, which have been widely adopted in recent wireless communication systems. According to wireless communication standards, the requirements of variable-length FFT are usually necessary to fit different channel environments. Therefore, how to design a FFT processor with low-cost hardware requirements, especially for variable-length FFT applications, is a very important research issue.
3GPP-LTE has been attracted much attention since it is the candidate for the next generation mobile communication standards; however, conventional variable-length FFT architectures cannot be directly applied since 1536-point FFT, whose FFT size is not power of two, is included in this applications. Therefore, this thesis presents an area-efficient variable-length FFT processor for 3GPP-LTE applications with the following techniques. First, the proposed processor applies a memory-based architecture and designs an address generator unit to solve the memory conflict problems. Then, the hardware sharing method is applied between 1536-point FFT and power-of-two FFTs. Finally, the index mapping technique is also adopted to avoid storing twiddle factors for 1536-point FFT. Synthesis results show that the proposed FFT processor can operate at 100MHz using TSMC 0.18 μm CMOS process and the total area requirement in terms of gate counts is only 24k.

[1] R. van Nee and R. Prasad, OFDM for Wireless Multimedia Communications, Artech House, 2000.
[2] W.-Y. Zou and Y. Wu, “COFDM: an Overview,” IEEE Trans. Broadcasting, vol. 41, no. 1, pp.1-8, Mar. 1995.
[3] 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., Nov. 2006, pp. 203-206.
[4] 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.
[5] 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 Trans. Circuits Syst. II, Exp. Briefs, vol. 55, no. 2, pp. 146-150, Feb. 2008.
[6] H. F. Lo, M. D. Shieh, and C. M. Wu, “Design of an efficient FFT processor for DAB system,” in Proc. IEEE Int. Symp. Circuits Syst., May 2001, pp. 654-657.
[7] 3GPP TS 36.201V 8.3.0, LTE Physical Layer-General Description (Release 8), Nov. 2009.
[8] D. P. Kolba and T. W. Parks, “A prime factor FFT algorithm using high-speed convolution,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 25, no. 4, pp. 281-294, Aug. 1977
[9] C. Burrus, “Index mappings for multidimensional formulation of the DFT and convolution,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 25, no. 3, pp. 239-242, Jun. 1977.

[10] C. F. Hsiao, Y. Chen, and C. Y. Lee, “A generalized mixed-radix algorithm for memory-based FFT processors,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 57, no. 1, pp. 26-30, Jan. 2010.
[11] J. Cooley and J. W. Tukey, “An algorithm for the machine calculation of the complex Fourier series,” Math. Comput., vol. 19, no. 90, pp. 297-301, Apr. 1965
[12] S. He and M. Torkelson, “Designing pipeline FFT processor for OFDM (de)Modulation,” in Proc. IEEE URSI Int. Symp. Signals, Syst., Electron., 1998, pp. 257-262.
[13] 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, no. 3, pp. 484-493, Mar. 2004.
[14] L. G. Johnson, “Conflict free memory addressing for dedicated FFT hardware,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 39, pp. 312-316, May 1992.
[15] D. Reisis and N. Vlassopoulos, “Conflict-free parallel memory accessing techniques for FFT architecture,” IEEE Trans. Circuits Syst. I, Reg. Papers vol. 55, no. 11, pp. 3438-3447, Dec. 2008.
[16] B. G. Jo and M. H. Sunwoo, “New continuous-flow mixed-radix (CFMR) FFT processor using novel in-place strategy,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 52, no. 5, pp. 911-919, May 2005.
[17] Drey Enterprise Inc., Jaguar II Variable-Point (8-1024) FFT/IFFT Specification, 1998.
[18] Amphion, CS2410 8-1024 Point FFT/IFFT, July 2001.
[19] R. Radhouane, P. Liu, and C. Modlin, “Minimizing the memory requirement for continuous flow FFT implementation: continuous flow mixed mode FFT (CFMM-FFT),” in Proc. IEEE Int. Symp. Circuits Syst., May 2000, vol. 1, pp. 116-119.

[20] C. L. Wey, S. Y. Lin, and W. C. Tang, “Efficient memory-based FFT processors for OFDM applications,” in Proc. IEEE Electro/Inf. Technol., May 2007, pp. 345-350.
[21] B. M. Baas, “A low-power, high-performance, 1024-point FFT processor,” IEEE J. Solid-State Circuits, vol. 24, no. 3, pp. 380-387, Mar.1999.
[22] P. Y. Tsai, and C. Y. Lin, “A generalized conflict-free memory addressing scheme for continuous-flow parallel-processing FFT processors with rescheduling,” IEEE Trans. Very Large Scale Integer. (VLSI) Syst., to appear in 2010.
[23] K. M. Aamir, M. A. Maud and A. Loan, “On Cooley-Tukey FFT method for zero padded signals,” in Proc. IEEE Int. Symp. Emerg. Tech., Sep. 2005, pp.41-45.
[24] Y. Ma, “An effective memory addressing scheme for FFT processors,” IEEE Trans. Signal Processing, vol. 47, no. 3, pp. 907-911, Mar. 1999.
[25] Y. Ma and L. Wanhammar, “A hardware efficient control of memory addressing for high-performance FFT processors,” IEEE Trans. Signal Processing, vol. 48, no. 3, pp. 917-921, Mar. 2000.
[26] C. P. Hung, S. G. Chen, and K. L. Chen, “Design of an efficient variable-length FFT processor,” in Proc. IEEE Int. Symp. Circuits Syst., May 2004, pp. 23-26.
[27] Y. Chen, Y.-W. Lin, and C.-Y. Lee, “A block scaling FFT/IFFT processor for Wimax applications,” in Proc. 2nd IEEE Asian Solid-State Circuits Conf., Hangzhou, China, Nov. 2006, pp. 203–206.
[28] J. C. Kuo et al., “VLSI design of a variable-length FFT/IFFT processor for OFDM-based communication systems,” EURASIP J. Appl. Signal Process., no. 13, pp. 1306–1316, Dec. 2003.
[29] 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.
[30] 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.