臺灣博碩士論文加值系統

正交分頻多工(OFDM)技術，已被廣泛地應用在許多無線通訊系統，如DAB、DVB-T/H、WiMAX、IEEE 802.11a/g/n以及UWB中。由於具有高頻譜效率與抗多路徑干擾(multipath interference)的特性，正交分頻多工成為先進通訊系統中最重要的技術之ㄧ。而在正交分頻多工的傳收機(transceiver)中，快速傅立葉轉換處理器(FFT processor)是負責訊號解調(demodulation)的關鍵模組。因為本身的高運算複雜度，快速傅立葉轉換處理器通常佔據很大比率的系統功率預算。但由於許多正交分頻多工技術都是使用在無線可持應用中，因此需採用功率效能佳的快速傅立葉轉換處理器來延長電池使用時間。在這篇論文中，我們從演算法到硬體階層中提出數個新技術來完成低功率與高效能的快速傅立葉轉換處理器設計。為了展現這些構想的優點，我們也針對不同應用的需要，實作並分析了三個快速傅立葉轉換處理器。
在第一個設計中，我們提出了一個針對WiMAX應用的兩路徑多輸入多輸出(MIMO)快速傅立葉轉換與反快速傅立葉轉換處理器。藉由新提出的區塊調整演算法與乒乓快取(cache)－記憶體架構達到降低功率消耗與硬體成本的目的，共可節省50%的記憶體存取次數與64K位元記憶體空間。此外經過適當的資料排程，提出之設計能提高硬體使用率，並可在2052個時脈周期內完成連續兩路徑之2048點快速傅立葉轉換與反快速傅立葉轉換。我們將此2048點快速傅立葉轉換與反快速傅立葉轉換處理器使用聯電0.13 µm 1P8M製程實現，核心面積為1332×1590 µm2，訊號量化雜訊比(SQNR)在QPSK與16/64-QAM輸入下均超過48 dB。在時脈速度為22.8 MHz時(支援WiMAX規範最高產出率)，連續兩路徑之2048點快速傅立葉轉換在1.2伏特下功率消耗約為25.6 mW。
在第二個設計中，我們提出一個適於高速低功率應用的多管線(multi-pipelined)快取記憶體快速傅立葉轉換處理器。藉由提出的多管線架構與資料排程機制，可減少一半的記憶體存取次數以降低功率消耗。且其蝶形運算單元(BU)的使用率也較傳統多路徑延遲回授(MDF)方式為高。我們將此4096點快速傅立葉轉換處理器使用聯電90 nm 1P9M製程實現，處理速度可達到8 Gsample/s，核心面積為1760×2650 µm2，訊號量化雜訊比在QPSK與16-QAM輸入下均超過37.2 dB。8 Gsample/s的4096點快速傅立葉轉換運算在1.0伏特下功率消耗約為1055 mW。相較於之前的高速快速傅立葉轉換晶片，我們所提出的方案至少可增加16%的能量效率(energy efficiency)。
在最後的設計中，我們提出一個應用於多輸入多輸出正交分頻多工之動態電壓頻率調整(DVFS)快速傅立葉轉換處理器。藉由新提出的多模多路徑延遲回授(MMDF)架構，此處理器可採用最低時脈頻率完成1~8路徑的256點快速傅立葉轉換或單一高速的256點快速傅立葉轉換以支援動態電壓頻率調整運作。除此之外，我們也提出新的開路電壓偵測與調整(OLVDS)技術來達成快速且可靠的電壓控制。藉由這些機制，我們設計的快速傅立葉轉換處理器可在不同狀態下操作在適當的電壓與頻率以達到功率感知(power-aware)要求。我們將此256點快速傅立葉轉換處理器使用聯電90 nm 1P9M製程實現，核心面積為1880×1880 µm2，訊號量化雜訊比在QPSK與16-QAM輸入下均超過35.8 dB。2.4 Gsample/s的256點快速傅立葉轉換運算在0.85伏特下功率消耗約為119.7 mW。而晶片在TT區域時，電壓調整技術依不同的工作模式可節省18%到43%的功率消耗。

Orthogonal frequency division multiplexing (OFDM) technology has been widely adopted in many wireless communication systems such as DAB, DVB-T/H, WiMAX, IEEE 802.11a/g/n, and UWB. The properties of high bandwidth efficiency and excellent multipath immunity have made OFDM become one of the most promising technologies in the advanced communication systems. In an OFDM transceiver, the fast Fourier transform (FFT) processor is the key component for signal demodulation. Due to the inherently high computational complexity, an FFT processor often consumes a large percent of system power budget. Since many OFDM systems are designed for wireless portable applications, the design of power-efficient FFT processors is demanded to increase the battery life. In this dissertation, several new techniques from algorithm to hardware level are proposed for low-power and high-performance FFT design. To demonstrate these proposed ideas, three FFT designs for different applications are also implemented and analyzed.
In the first design, a two-stream multiple-input multiple-output (MIMO) FFT/IFFT processor for WiMAX applications is presented. A novel block scaling method and a new ping-pong cached-memory architecture are proposed to reduce the power consumption and hardware cost. With these schemes, half the memory accesses and 64-Kbit memory can be saved. Furthermore, by proper scheduling of the two data streams, the proposed design achieves better hardware utilization and can process two 2048-point FFTs/IFFTs consecutively within 2052 cycles. A test chip of the proposed 2048-point FFT/IFFT processor has been designed using UMC 0.13 µm single-poly eight-metal (1P8M) CMOS process with a core area of 1332×1590 µm2. The SQNR performance of the 2048-point FFT/IFFT is over 48 dB for QPSK and 16/64-QAM modulations. Power dissipation of two 2048-point FFT computations is about 25.6 mW (1.2 volt) at 22.8 MHz which meets the maximum throughput rate of WiMAX applications.
In the second design, a novel multi-pipelined cached-memory FFT processor for high-throughput and low-power applications has been presented. By the proposed multi-pipelined architecture and data scheduling scheme, half the memory accesses can be eliminated for low power. Besides, the utilization of butterfly units (BUs) is also increased compared to the traditional multipath delay feedback (MDF) structure. A test chip of the proposed 4096-point FFT processor has been designed using UMC 90 nm single-poly nine-metal (1P9M) CMOS process to achieve 8 Gsample/s processing rate. The core area of this chip is 1760×2650 µm2. The SQNR performance of this FFT processor is over 37.2 dB to support QPSK/16-QAM modulation. Power dissipation of 8 Gsample/s 4096-point FFT computations is about 1055 mW at 1.0 volt. Compared to the previous high-throughput FFT chip, our proposal has at least 16% improvement in energy efficiency.
The last design presents a new dynamic voltage and frequency scaling (DVFS) FFT processor for MIMO OFDM applications. By the proposed multimode multipath delay feedback (MMDF) architecture, our FFT processor can process 1~8-stream 256-point FFTs or a high-speed 256-point FFT at minimum clock frequency for DVFS operations. Furthermore, a novel open-loop voltage detection and scaling (OLVDS) mechanism is proposed for fast and robust voltage management. With these schemes, the proposed FFT processor can operate at adequate voltage/frequency under different configurations to support the power-aware feature. A test chip of the proposed 256-point FFT processor has been fabricated using UMC 90 nm single-poly nine-metal (1P9M) CMOS process with a core area of 1880�e1880 µm2. The SQNR performance of this FFT chip is over 35.8 dB for QPSK/16-QAM modulation. Power dissipation of 2.4 Gsample/s 256-point FFT computations is about 119.7 mW at 0.85 volt. Depending on the operation mode, power can be saved by 18%~43% with voltage scaling in TT corner.

LIST OF FIGURES V
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 OFDM Overview 1
1.2 Motivation 5
1.2.1 Low-power Issue in FFT Design 5
1.2.2 High-throughput Issue in FFT Design 6
1.3 Goal and Contribution 8
1.4 Dissertation Organization 10
CHAPTER 2 OVERVIEW OF PREVIOUS FFT ALGORITHMS AND ARCHITECTURES 11
2.1 The FFT Algorithm 11
2.1.1 Decimation-in-time FFT Algorithm [3], [4] 12
2.1.2 Decimation-in-frequency FFT Algorithm [3], [4] 15
2.1.3 High-radix FFT Algorithm [4], [5] 16
2.1.3.1 Radix-4 Algorithm 16
2.1.3.2 Radix-8 Algorithm 17
2.1.4 Radix-2n FFT Algorithm [6] 18
2.1.4.1 Radix-22 Algorithm 18
2.1.4.2 Radix-23 Algorithm 19
2.1.4.3 Radix-24 Algorithm 20
2.1.5 Split-radix Algorithm [7], [8] 22
2.1.6 Non-2n FFT Algorithms 23
2.1.6.1 Prime Factor Algorithm [9], [10] 23
2.1.6.2 Winograd Fourier Transform Algorithm [11] 23
2.2 The FFT Architecture 24
2.2.1 The Memory-based FFT Architecture 24
2.2.1.1 Dual-memory Architecture [13] 25
2.2.1.2 Single-memory Architecture 25
2.2.1.3 Cached-memory Architecture [14] 26
2.2.2 Pipelined FFT architecture 27
2.2.2.1 Single-path Delay Feedback Architecture [15] 27
2.2.2.2 Multipath Delay Commutator Architecture [16], [17] 28
2.2.2.3 Multipath Delay Feedback Architecture [18] 29
2.2.3 Pipeline Shared-memory Architecture [19] 31
2.2.4 Selection of FFT Architectures 31
CHAPTER 3 BLOCK SCALING FFT ALGORITHM 34
3.1 Overview 34
3.2 Design Issue of the WiMAX MIMO FFT Processor 35
3.3 The FFT Algorithm 37
3.4 The Block Scaling Algorithm 38
3.5 The FFT Processor Design 40
3.5.1 Main Memory 41
3.5.2 Ping-Pong Cache Memory Structure 42
3.5.3 Processing Element (PE) 43
3.6 Chip Implementation 46
3.7 Measurement Result and Analysis 47
3.8 Summary 49
CHAPTER 4 MULTI-PIPELINED CACHED-MEMORY FFT ARCHITECTURE 50
4.1 Overview 50
4.2 Design Issue of the 8 Gsample/s Multi-pipelined Cached-memory FFT Processor 51
4.3 The FFT Algorithm 53
4.4 Scheduling Technique for the Multi-pipelined PE 57
4.4.1 Proposed MDC FFT with Reordered Output 58
4.4.2 Proposed MDC FFT with Reordered Input 59
4.5 The FFT Processor Design 60
4.5.1 Main Memory 61
4.5.2 Multi-pipelined Processing Element 61
4.5.2.1 Multi-pipelined Butterfly Unit 62
4.5.2.2 Internal Switch 64
4.5.3 I/O Switching Network 66
4.6 Chip Implementation 67
4.7 Analysis and Comparison 69
4.8 Summary 70
CHAPTER 5 DYNAMIC VOLTAGE AND FREQUENCY SCALING (DVFS) TECHNIQUE 71
5.1 Overview 71
5.2 Design Issue of the FFT Processor for a High-speed MIMO OFDM System 73
5.3 The FFT Algorithm 76
5.4 The FFT Processor Design 80
5.4.1 Input Scheduler 81
5.4.2 Module 1 and Module 2 83
5.4.3 Module 3 and Module 4 85
5.5 Open-Loop Voltage Detection and Scaling Scheme 86
5.5.1 Hardware Structure of the OLVDS Design 88
5.5.2 Operation of the OLVDS Scheme 89
5.6 Chip Implementation 92
5.7 Measurement Result and Analysis 94
5.8 Summary 98
CHAPTER 6 CONCLUSIONS AND FUTURE WORK 100
6.1 Conclusions 100
6.2 Future work 102
6.2.1 Very-long Size FFT Processors 102
6.2.2 Multi-standard General-size FFT Processors 103
BIBLIOGRAPHY 106
APPENDIX A COMMERCIAL FFT CHIPS 111
APPENDIX B ESSENTIAL FFT PATENTS 112

[1] J. Reunamäki, “Nokia PHY submission to Task Group 4,” IEEE 802.15-01/231r2, July 2001.
[2] L.-F. Chen, Y. Chen, L.-C. Chien, Y.-H. Ma, C.-H. Lee, Y.-W. Lin, C.-C. Lin, H.-Y. Liu, T.-Y. Hsu, and C.-Y. Lee, “A 1.8V 250mW COFDM baseband receiver for DVB-T/H applications,” in IEEE Int. Solid-State Circuits Conf. (ISSCC) Dig. Tech. Papers, Feb. 2006, pp. 262, 263, 652.
[3] A. V. Oppenheim and R. W. Schafer, Discrete-time Signal Processing, NJ: Prentice-Hall, 1999.
[4] L. R. Rabiner and B. Gold, Theory and Application of Digital Signal Processing, NJ: Prentice-Hall, 1975.
[5] S. Bouguezel, M. O. Ahmad, and M. N. S. Swam, “Improved radix-4 and radix-8 FFT algorithms,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS), May 2004, pp. III561–564.
[6] S. He, and M. Torkelson, “Designing pipeline FFT processor for OFDM (de)modulation” in Proc. IEEE URSI Int. Symp. Signals, Syst., and Electron., Oct. 1998, pp. 257–262.
[7] P. Dunamel, H. Hollmann, “Split radix FFT algorithm,” Electronics Letters, vol. 20, no. 1, pp. 14–16, Jan. 1984.
[8] P. Duhamel, “Algorithms meeting the lower bounds on the multiplicative complexity of length-2n DFT’s and their connection with practical algorithms,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 38, no. 9, pp. 1504–1511, Sep. 1990.
[9] I. J. Good, “The interaction algorithm and practical Fourier series,” J. Royal Stat. Soc., ser. B, vol. 20, no. 2, pp. 361–372, 1958.
[10] D. P. Kolba and T. W. Parks, “A prime factor FFT algorithm using high-speed convolution,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-25, no. 4, pp. 281–294, Aug. 1977.
[11] R. N. Bracewell, The Fourier Transform and Its Applications, NY: McGraw-Hill, second edition, 1986.
[12] Z.-X. Yang, Y.-P. Hu, C.-Y. Pan, and L. Yang, “Design of a 3780-point IFFT processor for TDS-OFDM,” IEEE Trans. Broadcast., vol. 48, no.1, pp. 57–61, Mar. 2002.
[13] S. Magar, S. Shen, G. Luikuo, M. Fleming, and R. Aguilar, “An application specific DSP chip set for 100 MHz data rates,” in Proc. Int. Conf. Acoustics, Speech, and Signal Processing, Apr. 1988, pp. 1989–1992.
[14] B. M. Baas, “A low-power, high-performance, 1024-point FFT processor,” IEEE J. Solid-State Circuits, vol. 34, no.3, pp. 380–387, Mar. 1999.
[15] S. He and M. Torkelson, “Design and implementation of a 1024-point pipeline FFT processor,” in Proc. IEEE Custom Integrated Circuits Conf., May 1998, pp. 131–134.
[16] P. A. Ruetz and M. M. Cai, “A real time FFT chip set: architectural issues,” in Proc. Int. Conf. Pattern Recognition, June 1990, pp. 385–388.
[17] E. Bidet, D. Castelain, C. Joanblanq, and P. Senn, “A fast single-chip implementation of 8192 complex point FFT,” IEEE J. Solid-State Circuits, vol. 30, no.3, pp. 300–305, Mar. 1995.
[18] Y.-W. Lin, H.-Y. Liu, and C.-Y. Lee, “A 1-GS/s FFT/IFFT processor for UWB applications,” IEEE J. Solid-State Circuits, vol. 40, no. 8, pp. 1726–1735, Aug. 2005.
[19] L. Jia, Y. Gao, and H. Tenhunen, “A pipelined shared-memory architecture for FFT processors,” in Proc. IEEE Int. Midwest Symp. on Circuits and Syst. (MWSCAS), Aug. 1999, pp. 804–807.
[20] WiMAX Forum, Mobile WiMAX-Part I: A Technical Overview and Performance Evaluations, Feb. 21, 2006.
[21] 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.
[22] B. M. Baas, “An approach to low-power, high-performance, fast Fourier transform processor design,” PhD Dissertation, Stanford University, Stanford, CA, 1999.
[23] 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. 2003.
[24] B. G. Jo and M. H. Sunwoo, “New continuous-flow mixed radix (CFMR) FFT using novel in-place strategy,” IEEE Trans. Circuits Syst., vol. 52, no. 5, pp. 911–919, May. 2005.
[25] 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, no. 2, pp. 483–495, Feb. 2006.
[26] Y.-T. Lin, P.-Y. Tsai, and T.-D. Chiueh, “Low-power variable-length fast Fourier transform processor,” Proc. IEE Comput. Digit. Tech., vol. 152, no. 4, pp. 499–506, July 2005.
[27] H. Harada et al. “New PHY layer and enhancement of MAC for mmwave system proposal,” IEEE 802.15-07-0934-01-003c, Nov. 2007.
[28] G. Baldwin et al. “Proposal for HD AV and data support,” IEEE 802.15-07-0942-02-003c, Nov. 2007.
[29] Y. Tang, X. Yi, W. Shieh and R. Evans, “Optimum design for coherent optical OFDM transmitter,” in Proc. OFC/NFOEC, Mar. 2007, paper JThA47.
[30] D. F. Hewitt, “Orthogonal frequency division multiplexing using baseband optical single sideband for simpler adaptive dispersion compensation,” in Proc. OFC/NFOEC, Mar. 2007, paper OME7.
[31] W. Shieh, X. Yi, and Y. Tang, “Experimental demonstration of transmission of coherent optical OFDM systems,” in Proc. OFC/NFOEC, Mar. 2007, paper OMP2.
[32] A. J. Lowery and J. Armstrong, “Orthogonal-frequency-division multiplexing for optical dispersion compensation,” in Proc. OFC/NFOEC, Mar. 2007, paper OTuA4.
[33] N. Cvijetic, L. Xu, T. Wang, “Adaptive PMD compensation using OFDM in long-haul 10Gb/s DWDM systems,” in Proc. OFC/NFOEC, Mar. 2007, paper OTuA5.
[34] Y.-M. Lin, “Demonstration and design of high spectral efficiency 4Gb/s OFDM system in passive optical networks in Proc. OFC/NFOEC, Mar. 2007, paper OThD7.
[35] J. Lee, H. Lee, S.-I. Cho, and S.-S. Choi, “A high-speed, low-complexity radix-24 FFT processor for MB-OFDM UWB systems,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS), May 2006, pp. 4719–4722.
[36] 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, Express Briefs, vol. 55, no. 2, pp. 146–150, Feb. 2008.
[37] Y. Chen, Y.-W. Lin, Y.-C. Tsao, and C.-Y. Lee, “A 2.4-Gsample/s DVFS FFT processor for MIMO OFDM communication systems,” IEEE J. Solid-State Circuits, vol. 43, no. 5, pp. 1260–1273, May, 2008.
[38] N. Miyamoto, L. Karnan,. K. Maruo, K. Kotani, and T. Ohmi, “A small-area high performance 512-point 2-dimensional FFT single-chip processor,” in Proc. IEEE European Solid-State Circuits Conf. (ESSCIRC), Sep. 2003, pp. 603–606.
[39] 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. (A-SSCC), Nov. 2006, pp. 203–206.
[40] Y.-W. Lin and C.-Y. Lee, “Design of an FFT/IFFT processor for MIMO OFDM systems,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 54, no. 4, pp. 807–815, Apr. 2007.
[41] K. J. Nowka, G. D. Carpenter, E. W. MacDonald, H. C. Ngo, B. C. Brock, K. I. Ishii, T. Y. Nguyen, and J. L. Burns, “A 32-bit PowerPC system-on-a-chip with support for dynamic voltage scaling and dynamic frequency scaling,” IEEE J. Solid-State Circuits, vol. 37, no. 11, pp. 1441–1447, Nov. 2002.
[42] T. Fujiyoshi, S. Shiratake, S. Nomura, T. Nishikawa, Y. Kitasho, H. Arakida, Y. Okuda, Y. Tsuboi, M. Hamada, H. Hara, T. Fujita, F. Hatori, T. Shimazawa, K. Yahagi, H. Takeda, M. Murakata, F. Minami, N. Kawabe, T. Kitahara, K. Seta, M. Takahashi, Y. Oowaki, and T. Furuyama, “A 63-mW H.264/MPEG-4 audio/visual codec LSI with module-wise dynamic voltage/frequency scaling,” IEEE J. Solid-State Circuits, vol. 41, no. 1, pp. 54–62, Jan. 2006.
[43] M. Nakai, S. Akui, K. Seno, T. Meguro, T. Seki, T. Kondo, A. Hashiguchi, H. Kawahara, K. Kumano, and M. Shimura, “Dynamic voltage and frequency management for a low-power embedded microprocessor,” IEEE J. Solid-State Circuits, vol. 40, no.1, pp. 28–35, Jan. 2005.
[44] T. Kuroda, K. Suzuki, S. Mita, T. Fujita, F. Yamane, F. Sano, A. Chiba, Y. Watanabe, K. Matsuda, T. Maeda, T. Sakurai, and T. Furuyama, “Variable supply-voltage scheme for low-power high-speed CMOS digital design,” IEEE J. Solid-State Circuits, vol. 33, no. 3, pp. 454–462, Mar. 1998.
[45] M. Nomura, Member, Y. Ikenaga, K. Takeda, Y. Nakazawa, Y. Aimoto, and Y. Hagihara, “Delay and power monitoring schemes for minimizing power consumption by means of supply and threshold voltage control in active and standby modes,” IEEE J. Solid-State Circuits, vol. 41, no. 4, pp. 805–814, Apr. 2006.
[46] K. K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementations, New York: Wiley, 1999.
[47] L. G. Johnson, “Conflict free memory addressing for dedicated FFT hardware,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 39, no. 5, pp. 312–316, May 1992.
[48] B. Giebel, J. Lutz, and P.L. O'Leary, “Digitally controlled oscillator,” IEEE J. Solid-State Circuits, vol. 24, no. 3, pp. 640–645, Jun. 1989.
[49] A. Drake, R. Senger, H. Deogun, G. Carpenter, S. Ghiasi, T. Nguyen, N. James, M. Floyd, V. Pokala, “A distributed critical-path timing monitor for a 65nm high-performance microprocessor,” in IEEE Int. Solid-State Circuits Conf. (ISSCC) Dig. Tech. Papers, Feb. 2007, pp. 398–399.
[50] A. Wang and A. Chandrakasan, “A 180-mV subthreshold FFT processor using a minimum energy design methodology,” IEEE J. Solid-State Circuits, vol. 40, no. 1, pp. 310–319, Jan. 2005.
[51] DVB, “Frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2),” DVB Document A122 (TM 3980 Rev. 5), June 2008.
[52] Standardization Administration of the People’s Republic of China, “Frame structure, channel coding and modulation for a digital television terrestrial broadcasting system,” Chinese National Standard GB 20600, Aug. 2006.