正交分頻多工系統(OFDM)以其在惡劣通道下的優異表現而聞名，並已在各種有線和無線通訊系統中被廣泛的採用，如無線區域網路、地面數位電視廣播和一些數位用戶迴路系統。正交分頻多工系統使用了許多先進的數位信號處理技術，因此其運算複雜度相當高，其中其調變/解調變的核心 --- 正向/反向傅立葉轉換(FFT/IFFT)就是一個複雜度相當高的功能方塊。雖然在超大型積體電路和自動化設計工具的進步下，其實現上的困難度已大大降低。然而在考慮系統單晶片(SoC)的因素，我們設計出一個可重組化之快速傅立葉處理器，此矽智產將可適用於常見的正交分頻多工通訊系統規格，而不需要因應用系統不同而重複類似的設計流程。此外，在手持行動設備的應用上及晶片的散熱考量，我們也採用了低功率消耗的技巧。
在處理器中，記憶體存取消耗將近50%的功率，因此在硬體架構上，我們採用了快取快速傅立葉轉換的架構，其在核心和主記憶體中加入了快取因而可降低對記憶體存取的次數。而處理器的核心則是蝴蝶處理單元，其動作包和了複數的加法與乘法，我們將採用數位座標旋轉計算器(CORDIC)來取代複數的乘法器，以減低硬體複雜度。在係數的設計上，在數位座標旋轉計算器中採用不同的數字表示法，我們將可選擇低數字變換率的係數組合，而降低功率消耗。
我們採用台積電0.35um 1P4M CMOS製程，設計出來的快速傅立葉處理器面積約為12.25mm2(包含2048x32 bits的記憶體)，其輸入輸出為16位元，晶片可操作在60MHz。

Orthogonal Frequency Division Multiplexing (OFDM) systems are famous for its robustness against frequency selective fading channel. This technique has been widely used in wired and wireless communication systems, such as wireless LAN 802.11a, digital audio/video broadcasting, ADSL, and VDSL systems. OFDM systems contain lots of advanced digital signal processing techniques. Therefore the computation complexity is very high. The modulation/demodulation kernel, fast Fourier Transform (FFT) and inverse FFT (IFFT) is one of them. Also the advances in the Very Large Scale Integrated (VLSI) circuits and CAD tools have made the hardware realization less difficult. Here, we propose a reconfigurable FFT/IFFT processor, which can meet common OFDM communication systems. On the other hand, we also apply low power techniques to elongate the battery life on mobile applications and to relieve the heating problem of the chip.
In the FFT/IFFT processor, the memory access operations consume almost 50% of the power. Hence, we adopt the cached FFT algorithm, which reduce the main memory access times by inserting a cache memory. The processor kernel is the butterfly processing element. This functional block consists of complex additions and multiplications. We can reduce the hardware complexity by replacing complex multiplier with Coordinate Rotational Digital Computer (CORDIC). The number representation is different for CORDIC and general multipliers. Thus, we can choose a coefficient set with lower number of transition to further lower the power dissipation.
We have realized the design with TSMC 0.35um 1P4M CMOS technology. The die area of the FFT/IFFT processor is 12.25 mm2 including 2048x32 bits memory. The input/output wordlength is 16-bits wide. The chip can operate under 60 MHz and meet most standard requirements.

Index
Index i
List of Tables ii
List of Figures iii
Chapter 1 Introduction 1
1.1 Background of OFDM Systems 1
1.1.1 Basics of OFDM 1
1.1.2 Role of FFT/IFFT in OFDM Systems 5
1.2 Motivation and Goal 8
1.3 Thesis Organization 9
Chapter 2 FFT/IFFT Processor Architecture 10
2.1 FFT/IFFT Computation Flow 10
2.2 Review for Existing FFT/IFFT Processor Schemes 13
2.3 Cached FFT Algorithm 16
2.4 Cache FFT Hardware Architecture 20
Chapter 3 Butterfly Processing Element Design 22
3.1 Design of PE Parameters 22
3.2 Review of CORDIC Algorithm 25
3.2.1 Conventional CORDIC 26
3.2.2 AR-CORDIC 27
3.2.3 EEAS-CORDIC 29
3.2.4 Pre-rotation Scheme 33
3.3 CORDIC-Based Butterfly PE 34
Chapter 4 AG, CLU, and MU Designs 36
4.1 Address Generator (AG) Unit Design 36
4.1.1 Traditional FFT/IFFT Address Generation 37
4.1.2 Cached FFT/IFFT Address Generation 38
4.2 Control Logic Unit (CLU) Design 41
4.3 Coefficient ROM Design 43
Chapter 5 VLSI Implementation and Comparison 46
5.1 IC Design Flow 46
5.2 Chip Summary 49
5.3 Comparison 51
Chapter 6 Conclusion 52
Bibliography 53

[1] Irving Kalet, “The multitone channel,” IEEE trans. On communications, pp 119-124, February 1989.
[2] Pter S Chow, Jerry C. Tu, Jhon M. Cioffi, “Performance evaluation of a multichannel transceiver system for ADSL and VHDSL services,” IEEE Journal On communications, pp 909-919, August 1991.
[3] Naofal AI-Dhahir and John M. Cioffi, “Optimum finite-length equalization for multicarrier transceivers,” IEEE trans. On communications, pp 56-64, January 1996.
[4] R. W. Chang, "Synthesis of Band Limited Orthogonal Signals for Multichannel Data Transmission," Bell Sys. Tech. J., Vol. 45, pp. 1775-1796, Dec. 1996.
[5] B. R. Salzberg, "Performance of an efficient parallel data transmission system," IEEE Trans. Comm., Vol. COM-15, pp.805-813, Dec, 1967.
[6] S. B. Weinsten and P. M. Ebert, "Data Tansmission by Frequency Division Multiplexing Using the Discrete Fourier Transform," IEEE Trans. Comm., Vol. COM-19, pp. 628-634, Oct. 1971.
[7] W. Y. Zou and Y. Wu, "COFDM: an overview," IEEE Trans, Broadc., Vol. 41. No. 1, pp 1-8, March 1995.
[8] R. van Nee and R. Prasad, OFDM for Wireless Multimedia Communications, Artech House, 2000.
[9] P. S. Chow, J. C. Tu, and J. M. Cioffi, "Performance Evaluation of a Multichannel Transceiver System for ADSL and VHDSL sevices," IEEE J. Selected Area, Vol. SAC-9, No. 6, pp. 909-919, Aug. 1991.
[10] R. V. Paiement, " Evaluation of Single Carrier and Multicarrier Modulation Techniques for Digital ATV Terrestrial Broadcasting," CRC Report, No. CRC-RP-004, Ottawa, Canada, Dec. 1994.
[11] S. Hara, M. Mori, M. Okadam and N. Morinaga, "Transmission Performance Analysis of Multi-Carrier Modulation in Frequency Selective Fast Rayleigh Fading Channel," Wireless Personal Communications, Kluwer Academic Publishers, Vol. 2, pp. 335-356, 1996.
[12] B.M. Baas, “A Low-Power High-Performance, 1024-Point FFT Processor,” IEEE J. of Solid-State Circuits, vol. 34 no. 3, pp. 380-387, Mar 1999.
[13] A. V. Oppenheim and R.W Schaffer, Discrete-time Signal Processing, 2nd Ed., Prentice-Hall International, 1989.
[14] W. Li and L. Wanhammar, "A Pipeline FFT Processor," IEEE Workshop on Signal Processing Systems, pp. 654-662, 1999.
[15] H. Shousheng and M. Torklson, "Designing pipline FFT processor for OFDM (de)modulation," International symposium on Signals, Systems, and Electronics, pp. 257-262, 1998.
[16] E. Bidet, D. Castelain, et al., "A fast single-chip implementation of 8192 complex point FFT, " IEEE Journal of Solid-State Circuits, Vol. 30, Issue 3, pp. 300-305, March 1995
[17] C. H. Chang, C.L. Wang, and Y. T. Chang, "A novel memory-based FFT processor for DMT/OFDM applications" IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 4, pp. 1921-1924, 1999.
[18] J. E. Volder, “The CORDIC trigonometric computing technique,” IRE Trans. on Electronic Computers, vol. 8, pp. 330-334, Sept. 1959.
[19] J. S. Walther, “A unified algorithm for elementary functions,” Spring Joint Computer Conf., pp. 379-385, 1971.
[20] Y. H. Hu, “CORDIC-based VLSI architectures for digital signal processing,” IEEE Signal Processing Magazine, pp. 16-35, July 1992.
[21] Y. H. Hu and S. Naganathan, “An angle recoding method for CORDIC algorithm implementation,” IEEE Trans. on Computers, vol. 42, pp. 99-102, Jan. 1993.
[22] C. S. Wu and A. Y. Wu, “A novel rotational VLSI architecture based on extended elementary-angle set CORDIC algorithm,” in Proc. IEEE 2nd IEEE Asia Pacific Conference on ASICs, (Cheju, Korea), pp. 111-114, 2000.
[23] C. S. Wu and A. Y. Wu, “Modified vector rotational CORDIC (MVR-CORDIC) algorithm and its application to FFT,” in Proc. IEEE Int. Symp. Circuits and Systems, pp. 529-532, 2000.
[24] M. Hasan and T. Arslan, “Coefficient memory addressing scheme for high performance FFT processors “ Electronics Letters, vol. 37, Issue 22, pp. 1322 —1324, 25 Oct. 2001.
[25] K. Masselos, S. Theoharis, et al., "A novel methodology for power consumption reduction in a class of DSP algorithms," Proc. IEEE International symposium on circuits and Systems, pp. 199-202, 1998.
[26] A. M. Despain, “Fourier transform computers using CORDIC iterations, “ IEEE Trans. on Computers, vol. 23, pp. 993-1001, Oct. 1974.
[27] A. M. Despain, “Very fast Fourier transform algorithms for hardware implementation,” IEEE Trans. on Computers, vol. 28, pp.333-341, May 1979.
[28] P. P. Vaidyanathan, “A unified approach to orthogonal digital filters and wave digital filters based on the LBR two-pair extraction,” IEEE Trans. Circuits Syst., pp. 673-686, July 1985.
[29] A. Madisetti, A. Kwentus, and A. J. Willson, “A sine/cosine direct digital frequency synthesizer using an angle rotation algorithm,” in IEEE International Solid-State Circuits Conference, 1995. Digest of Technical Papers. 41st ISSCC, pp. 262-263, 1995.
[30] A. H. Gray, Jr. and J. D. Karkel, “Digital lattice and ladder filter synthesis,” IEEE trans. on Audio and Electroacoustics, vol. AU-21, pp.259-270, Dec 1973.
[31] Avanindra madisetti, Y. K. Alan, and Alan N. Willson Jr., ”A 100MHz, 16-b, direct digital frequency synthesizer with a 100-dbc spurious-free dynamic range,” IEEE Journal of Solid-State Circuits, vol. 34, no. 8, pp. 1034-1043, Aug. 1999.
[32] A. H. Gray, Jr. and J. D. Karkel, “A Normalized digital filter structure,” IEEE trans. on Acoustics, Speech, and Signal Processing, vol. ASSP-23, pp.268-277, June 1975.
[33] Y. H. Hu and Z. Wu, “An efficient CORDIC array structure for the implementation of discrete cosine transform,” IEEE Trans. on Signal Processing, vol. 43, pp. 331--336, Jan. 1995.
[34] A. Y. Wu, K. J. R. Liu, and A. Raghupathy, “System architecture of an adaptive reconfigurable DSP computing engine,” IEEE Trans. Circuits Syst. Video Technol., vol.8, pp. 54-73, Feb. 1998.
[35] J. H. Hsiao, L. G. Ghen, T. D. Chiueh, and C. T. Chen, “High throughput CORDIC-based systolic array design for the discrete cosine transform,” IEEE Trans. Circuits Syst. Video Technol., vol. 5, pp. 218--225, Jan. 1995.
[36] Ulrich Reimers, “Digital Video Broadcasting (DVB): The future of television,” in Physics World, April 1998.
[37] ETS 300 401, “Radio broadcasting system: Digital Audio Broadcasting (DAB) to Mobile, Portable and Fixed Receivers,” ETSI 2nd edition, May 1997.
[38] Y. Wu and W. Y. Zou, “Orthogonal frequency division multiplexing: A multi-carrier modulation scheme," IEEE Trans. Consumer Electronics, vol. 41, No. 3, Aug. 1995.
[39] John Stott (BBC), “DVB-T and the Magic of COFDM,” Web ssite at URL: http:// www.dvb.org/dvb_articles/dvb_articles.htm
[40] N. Weste and D. J. Skellern, “VLSI for OFDM,” IEEE Communications Magazine, Oct. 1998.
[41] Jacky S. Chow, Jerry C. Tu and John M. Cioffi, “A Discrete Multitone Transceiver System for HDSL Applications,” IEEE Journal on selected areas in Commun., vol. 9, No. 6, pp. 859-908, Aug. 1991.
[42] Lee, J. S. Chou, and J. M. Cioffi, “Performance evaluation of a fast computation algorithm for the DMT in high-speed subscriber loop,” IEEE J. Select. Areas Commun., vol. 13, pp. 1560-1570, Dec. 1995.
[43] Alan V. Oppenheim and Ronald W. Schafer “Discrete time signal processing, 2nd edition,” Prentice Hall.
[44] A. Y. Wu and T. S. Chan, “Cost-efficient parallel lattice VLSI architecture for the IFFT/FFT in DMT transceiver technology,” IEEE Int. Conf. Acoust., Speech, and Signal Processing, vol. 6, pp. 3517-3520, Apr. 1998.
[45] K. J. Ray Liu, C. T. Chiu, R. K. Kolagotla, and J. F. J'aJ'a, “Optimal unified architectures for the real-time computation of time-recursive discrete sinusoidal transforms,” IEEE Trans. Circuits and Systems for Video Technology, vol. 4, no. 2, pp. 168-180, Apr. 1994.
[46] Bong-II Park, In-Cheol Park, and Chong-Min Kyung, “A regular layout structured multiplier based on weighted carry-save adder,” IEEE, pp. 243-248, 1999.
[47] G. B. Richard, Xingcha Fan, and Neil W. Bergmann, “An 180MHz 16 bit multiplier using asynchronous logic design techniques,” IEEE Custom Integrated Circuits Conference, pp 215-218, 1994
[48] Bryan W. Stiles and Earl E. Swartzlander Jr., “Pipelined parallel multiplier implementation,” IEEE, pp. 364-368, 1993.
[49] Jinn-Shyan Wang and Po-Hui Yang, “Power analysis and implementation of a low-power 300MHz 8-b x 8-b pipelined multiplier,” IEEE, pp. 364-368, 2000.
[50] S. He and M. Torkelson. “A new approach to pipeline FFT processor,” IEEE Proceedings of IPPS'96.
[51] J. Hormigo, J. Villalba, and E. Zapata, “Interval sine and cosine functions computation based on variable-precision CORDIC algorithm,” in 14th IEEE Symposium on Computer Arithmetic, 1999. Proceedings., pp. 186-193, 1999.
[52] J. Vankka, M. Kosunen, J. Hubach, and K. Halonen, “A CORDIC-based multicarrier QAM modulator,” Global Telecommunications Conference, 1999, pp. 173 --177, 1999.
[53] C.C.W. Hui, T.J. Ding, et al., " A New FFT Architecture and Chip Design for Motion Compensation Based on Pjase Correlation," Preceeding of International Conference, Application Specific Systems Architectures and Processors, pp.83-02, 1996.
[54] J. Lihong, Y. Gao, et al., " A New VLSI-Oriented FFT Algorithm and Implementation," IEEE ASIC Conference, pp.337-341, 1998.