臺灣博碩士論文加值系統

正交分頻多工技術 (OFDM) 提供一個有效的方法來消除多路徑通道中的頻率選擇性衰減。由於許多先進的數位訊號處理應用於此系統，因此正交分頻多工系統的運算複雜度相當高，其中快速傅立葉轉換處理器就是其中一個高運算複雜度的模組。當我們在設計快速傅立葉轉換處理器時需考慮快速傅立葉轉換處理器的規格會隨著不同的正交分頻多工系統而有所差異。本論文主要是著重在DVB-T, UWB, IEEE 802.11n 這三個正交分頻多工系統，同時提出三個新式快速傅立葉轉換處理器的架構應用於此三個系統中。
在DVB-T 系統中，我們提出一個8192點快速傅立葉轉換處理器，其具有3-step radix-8 快速傅立葉轉換演算法、新式動態調整的機制及矩陣預取緩衝器。利用所提出的動態調整的機制在 8K點的快速傅立葉轉換中約可省下64 K 位元的記憶體空間。此外，透過資料的排程 (scheduling) 及矩陣預取緩衝器 (matrix prefetch buffer)的架構，單埠記憶體可被採用於所提出的架構中且無任何效能的衰減。一個符合8K模式之DVB-T的測試晶片已被設計及用0.18 um 1P6M CMOS的製程實現。此處理器的核心面積為 4.84 mm2。在操作在20 MHz下，功率消耗約為25.2 mW。
在UWB系統中，所提出的管線式快速傅立葉轉換架構名稱為Mixed-Radix Multi-Path Delay Feedback (MRMDF)，其可藉由多條路徑的架構而提供較高的throughput rate。此外，藉由延遲迴授及資料排程，在MRMDF架構下的所需的記憶體及複數乘法硬體複雜度約為已知架構的38.9 %及44.9%。high-radix快速傅立葉轉換演算法也實現在所提出的處理器中以減少複數乘法器的數目。一個符合UWB系統的測試晶片已被設計及用0.18 um 1P6M CMOS的製程實現。此處理器的核心面積為 1.76 x 1.76 mm2, 此面積包含處理器及測試模組。所製作的快速傅立葉轉換處理throughput rate 可達到 1G sample/s，此時的功率消耗為175 mW，當其throughput rate符合UWB的規範時(409.6 MS/s), 其功率消耗為77.6 mW。
在IEEE 802.11n系統中，所提出的處理器不但能支援64點及128點的運算也能同時處理1~4個資料序列以符合IEEE 802.11n的要求。此外，與傳統4個處理器的方式相比，我們提出的架構具有較低的硬體複雜度。所提出的快速傅立葉轉換處理已用0.13 um 1P8M CMOS的製程來設計，此處理器的核心面積為 660 x 2142 um2, 此面積包含處理器及測試模組。當工作頻率操作在 40 MHz下，所提出的處理器可在3.2 us的時間內計算4個長度為128點的獨立資料序列。

Orthogonal Frequency Division Multiplexing (OFDM) technique provides an efficient way to overcome a multipath-fading environment. Because lots of advanced digital signal processing is used in this system, the computational complexity of OFDM is high. The Fast Fourier Transform (FFT) is one of the highest computational components. The specification of FFT which varies with different OFDM systems must be considered when we design the FFT processor. In this dissertation, we focus on three OFDM systems such as digital video broadcasting – territorial (DVB-T), Ultra-wideband (UWB), and IEEE 802.11n and propose three novel FFT architectures for these applications.
In a DVB-T system, an 8192-point FFT processor, in which a 3-step radix-8 FFT algorithm, a new dynamic scaling approach, and a novel matrix prefetch buffer are proposed. About 64 K bit memory space can be saved in the 8 K-point FFT by the proposed dynamic scaling approach. Moreover, with data scheduling and pre-fetched buffering, single-port memory can be adopted without degrading throughput rate. A test chip for 8 K mode DVB-T system has been designed and fabricated using 0.18 um single-poly six-metal (1P6M) CMOS process with core area of 4.84 mm2. Power dissipation is about 25.2 mW at 20 MHz
In a UWB system, the proposed pipelined FFT architecture called Mixed-Radix Multi-Path Delay Feedback (MRMDF) can provide higher throughput rate by using the multi-data-path scheme. Furthermore, the hardware costs of memory and complex multiplier in MRMDF are only 38.9% and 44.8 % of those in the known FFT processor by means of the delay feedback and the data scheduling approaches. The high-radix FFT algorithm is also realized in our processor to reduce the number of complex multiplications. A test chip for UWB system has been designed and fabricated using 0.18 um 1P6M CMOS process with core area of 1.76 x 1.76 mm2, including an FFT/IFFT processor and a test module. The throughput rate of this fabricated FFT processor is up to 1 G sample/s while it consumes 175 mW. Power dissipation is 77.6 mW, when its throughput rate meets UWB standard in which the FFT throughput rate is 409.6 M sample/s.
In a IEEE 802.11n system, the proposed processor based on multi-data-path scheme not only supports the operation of FFT/IFFT in 128 points and 64 points but also can provide the different throughput rates for 1~4 simultaneous data sequences to meet IEEE 802.11n requirements. Furthermore, less hardware complexity is needed in our design compared with the traditional four-parallel approach. The proposed FFT/IFFT processor is designed in a 0.13um single-poly and eight-metal CMOS process. The core area is 660 x 2142 um2, including an FFT/IFFT processor and a test module. At the operation clock rate of 40 M Hz, our proposed processor can calculate 128-point FFT with four independent data sequences within 3.2 us.

LIST OF FIGURES V
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 OFDM Introduction 1
1.1.1 OFDM Signal Processing 3
1.2 The Motivation and The Goal 4
1.3 Dissertation Organization 7
CHAPTER 2 SURVEY OF FFT ALGORITHM AND ARCHITECTURE 8
2.1 The FFT Algorithm 8
2.1.1 Decimation-in-Time (DIT) FFT Algorithm 8
2.1.1.1 Radix-2 DIT FFT Algorithm 8
2.1.1.2 Radix-4 DIT FFT Algorithm 11
2.1.1.3 Radix-8 DIT FFT Algorithm 12
2.1.2 Decimation-in-Frequency FFT Algorithm 13
2.1.2.1 Radix-2 DIF FFT Algorithm 13
2.1.2.2 Radix-4 DIF FFT Algorithm 14
2.1.2.3 Radix-8 DIF FFT Algorithm 15
2.1.3 Comparison of The Radix-2n FFT Algorithm 18
2.1.4 Other FFT Algorithms 19
2.1.4.1 Mixed-Radix FFT Algorithm 19
2.1.4.2 Split-Radix FFT Algorithm 20
2.1.4.2.1 Split-Radix 2/4 DIF FFT Algorithm 20
2.1.4.3 Winograd Fourier Transform Algorithm (WFTA) 21
2.1.4.4 Goertzel DFT 21
2.2 The FFT Architecture 22
2.2.1 The Single-Memory FFT Architecture 22
2.2.1.1 The Addressing Generator 22
2.2.1.2 The Main Memory Partition 27
2.2.1.3 The Performance Analysis 30
2.2.2 The Cache (Prefetch Buffer)-Memory FFT architecture 32
2.2.2.1 The Addressing Generator 34
2.2.3 The Pipelined FFT Architecture 36
2.2.3.1 The Radix-2n SDF Pipelined FFT Architecture 37
2.2.3.1.1 Radix-2 SDF Pipelined FFT Architecture (R2SDF) 37
2.2.3.1.2 Radix-22 SDF Pipelined FFT Architecture (R22SDF) 37
2.2.3.1.3 Radix-23 SDF Pipelined FFT Architecture (R23SDF) 38
2.2.3.2 The Radix-n MDC Pipelined FFT Architecture 39
2.2.3.2.1 Radix-2 MDC Pipelined FFT Architecture (R2MDC) 39
2.2.3.2.2 Radix-4 MDC Pipelined FFT Architecture (R4MDC) 40
2.2.3.3 Comparison of Various Pipelined FFT Architectures 40
2.2.4 The Dual-Memory FFT Architecture 41
2.2.5 The Array FFT architecture 41
2.3 Design Methodology of the FFT Processor for OFDM systems 42
2.4 Case Study- IEEE 802.11a 45
2.5 Summary 46
CHAPTER 3 THE DYNAMIC SCALING APPROACH TO IMPLEMENTATION OF LONG-SIZE FFT PROCESSORS 48
3.1 Overview 48
3.2 The FFT Algorithm for DVB-T Applications 51
3.2.1 The Dynamic Scaling Approach 60
3.2.1.1 The Proposed Approach 61
3.2.1.2 Simulation 61
3.3 The Proposed FFT Architecture 63
3.3.1 The Matrix Prefetch Buffer 65
3.3.2 Memory Capacity 66
3.4 Chip Implementation 67
3.5 Summary 70
CHAPTER 4 A MIXED-RADIX MULTI-PATH DELAY FEEDBACK (MRMDF) STRUCTURE FOR HIGH-THROUGHPUT-RATE FFT PROCESSORS 71
4.1 Overview 71
4.2 Design Issue of The FFT Processor for OFDM-based UWB System 72
4.3 The FFT Algorithm for UWB Applications 74
4.4 The FFT/IFFT Architecture for UWB System 80
4.4.1 The Proposed FFT/IFFT Architecture 80
4.4.1.1 Module 1 (Radix-2 FFT Algorithm) 82
4.4.1.2 Module 2 (Radix-8 FFT Algorithm) 84
4.4.1.3 Module 3 (Radix-8 FFT Algorithm) 87
4.4.2 Comparison 88
4.5 Simulation 90
4.6 Chip Implementation 92
4.7 Summary 94
CHAPTER 5 A UNFOLDING MRMDF STRUCTURE-BASED FFT PROCESSORS DEALING WITH MULTIPLE DATA SEQUENCES 94
5.1 Overview 94
5.2 Design Issue of the FFT Processor for a MIMO OFDM System 95
5.3 The FFT Algorithm for IEEE 802.11n System 97
5.4 The FFT/IFFT Architecture for MIMO OFDM Applications 102
5.4.1 The Proposed FFT/IFFT Architecture 102
5.4.1.1 Module 1 105
5.4.1.2 Module 2 107
5.4.1.3 Module 3 108
5.4.1.4 Module 4 110
5.4.2 Performance Analysis and Comparison 111
5.4.2.1 Performance Analysis 111
5.4.2.2 Comparison 113
5.5 Simulation and Implementation 115
5.6 Summary 117
CHAPTER 6 CONCLUSIONS AND FUTURE WORK 118
6.1 Conclusions 118
6.2 Future work 119
6.2.1 Multiple prefetch buffer-based FFT processors 120
6.2.2 The High-Throughput-Rate FFT Processor 121
BIBLIOGRAPHY 122

[1]S. B. Weinstein, P. M. Ebert, “Data transmission by frequency-division multiplexing using the discrete fourier transform,” IEEE Trans. Commun., pp. 628-634, Oct. 1971.
[2]B. Hirosaki, “ An orthogonally multiplexed QAM system using the discrete Fourier transform,” IEEE Trans. Commun., pp. 983-989, July 1981.
[3]L. J. Cimini., “ Analysis and simulation of a digital mobile channel using orthogonal frequency division multiplexing, “ IEEE Trans. Commun., pp. 665-675, Jul. 1985.
[4]Lihong Jia, Yonghong Gao, Jouni Isoaho, and Hannu Tenhunen, “A new VLSI-oriented FFT algorithm and implement,” Proceedings. Eleventh Annual IEEE International ASIC Conference pp.337-341, Sep 1998.
[5]Alan V. Oppenheim and Ronald W. Schafer, “Discrete-time signal processing”, published by Prentice-Hall, 1999.
[6]Shousheng He, and M. Torkelson, “Designing pipeline FFT processor for OFDM (de)modulation” URSI International Symposium on Signals, Systems, and Electronics, vol.29, pp. 257-262, Oct 1998.
[7]Wen-Chang Yeh and Chein-Wei Jen, “High-speed and low-power split-radix FFT,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Volume.51 Issue.3, pp. 864-874, Mar 2003.
[8]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 Nov. 2004.
[9]P. Dunamel, H. Hollmann, “Split Radix FFT Algorithm,” Electronics Letters 5th, vol. 20 No. 1, Jan 1984.
[10]R. N. Bracewell, “The Fourier Transform and Its Applications,” McGraw-Hill, New York, NY, second edition, 1986.
[11]Alan V. Oppenheim and Ronald W. Schafer, “Discrete-time signal processing”, published by Prentice-Hall, 1989.
[12]L. R. Rabiner and B. Gold, Theory and Application of Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1975.
[13]B.M. Bass, “A low-power, High-performance, 1024-point FFT processor”, IEEE Journal of Solid-State Circuits, vol. 34, pp. 380-387, May 1999.
[14]Hsin-Fu Lo,MingDer Shieh, Chien-Ming Wu, “Design of an efficient FFT processor for DAB system”, The IEEE International Symposium on Circuits and Systems, vol. 4, pp. 654-657, May 2001.
[15]S. Magar, S. Shen, G. Luikuo, M. Fleming, and R. Aguilar, “An application specific DSP chip set for 100 M Hz data rates,” in Proc. Int. Conf. Acoustics, Speech, and Signal Processing, Apr. 1988, vol.4, pp. 1989-1992.
[16]J. O’Brien, J. Mather, and B. Holland, “A 200 MIPS single-chip 1 k FFT processor,” in Proc. IEEE Int. Solid-State Circuits conf, vol.36, pp. 166-167, 327, 1989.
[17]ETSI, “Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for digital terrestrial television”, ETSI EN 300 744 v1.4.1, 2001.
[18]Weidong Li and L. Wanhammar, “A pipeline FFT processor,” IEEE Workshop on Signal Processing Systems, pp. 654-662, 1999
[19]Chien-Ming Wu, Ming-Der Shieh, Hsin-Fu Lo, and Min-Hsiung Hu, ”Implementation of channel demodulator for DAB system” International Symposium on Circuits and Systems, vol.2 , 25-28, May 2003.
[20]E. Bidet, D. Castelain, C. Joanblanq, and P. Senn, “ A fast single-chip implementation of 8192 complex point FFT,” IEEE Journal of Solid-State Circuits, vol.20, pp. 300-205, Mar 1995.
[21]Anuj Batra et al., “Multi-band OFDM Physical Layer Proposal for IEEE 802.15 Task Group 3a,” IEEE P802.15-03/268r3, March, 2004.
[22]S. Magar, S. Shen, G. Luikuo, M. Fleming, and R. Aguilar, “An application specific DSP chip set for 100 M Hz data rates,” in Proc. Int. Conf. Acoustics, Speech, and Signal Processing, vol.4, pp. 1989-1992, Apr. 1988.
[23]J. García, J. A. Michel, and A. M. Burón, “VLSI configurable delay Commutator for a pipeline split radix FFT architecture,” IEEE Trans. Signal Processing, vol. 47, pp.3098-3107, Nov. 1999.
[24]Koushik Maharatna, Eckhard Grass, and Ulrich Jagdhold, “A 64-Point Fourier Transform Chip for High-Speed Wireless LAN Application Using OFDM,” IEEE Journal of Solid-State Circuits, vol 39, pp. 484-493, March 2004.
[25]Yunho Jung, Hongil Yoon, and Jaeseok Kim, “New Efficient FFT Algorithm and Pipeline Implementation Results for OFDM/DMT Applications,” IEEE Transactions on Consumer Electronics, vol. 49, pp. 14-20.
[26]Mujtaba et al., TGn Sync Proposal Technical Specification for IEEE 802.11 Task Group, January, 2005. IEEE 802.11-04/0889r3.
[27]E.E. Swartzlander, W.K.W. Young, S.J. Joseph,” A radix 4 delay commutator for fast Fourier transform processo