簡易檢索 / 詳目顯示

回結果列表
研究生： 劉怡均
Liu, Yi-Jun
論文名稱： 有效率記憶體管理方式之快速傅立葉轉換處理器設計
New Memory Management Methods for Efficient FFT Processor Design
指導教授： 謝明得
Shieh, Ming-Der
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2008
畢業學年度： 96
語文別： 英文
論文頁數： 63
中文關鍵詞： 低功率 、資料重置 、單埠記憶體 、記憶體式快速傅立葉處理器
外文關鍵詞： data relocation, low-power, single-ported memory, memory-based FFT
相關次數： 點閱：48  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 快速傅立葉轉換處理器(FFT)是數位訊號處理系統中不可或缺的關鍵元件，更是目前無線通訊技術之核心，例如正交分頻多工系統(OFDM)，即使用快速傅立葉轉換及反傅立葉轉換之運算來達到調變及解調變之目的。根據不同規格需求，現今已存在多種典型的快速傅立葉處理器設計方式，其中記憶體式快速傅立葉處理器是一個具低成本應用的設計方法，在大點數的應用上是相當具競爭性。
    為提高產出率，記憶體式傅立葉轉換器通常會將記憶體切割成多個區塊以提供足夠頻寬。然而，因為每個記憶體區塊都有自己的位址解碼器，越多之區塊代表位址解碼器所佔面積越多。本論文提出一種資料重置(data relocation)的機制將這些區塊再度合併，在提供相同的頻寬下，可共享一組位址解碼器而達到面積及功率的改善。所提出之資料重置機制的記憶體管理方式，不但可應用於單埠記憶體架構上，並可適用於各種基數的運算單元(radix-r PE)中。最後在低功率的考量下，我們將此記憶體管理方式延伸，並加入快取記憶體的概念以達到低功率快速傅立葉轉換處理器的設計。

    Fast Fourier Transform (FFT) has been widely used in digital signal processing, and become one of the key techniques in most wireless communication systems. In particular, the popular Orthogonal Frequency Division Multiplexing (OFDM) technique has been extensively adopted in existing wireless standards for performing signal modulation. To fit in the requirements of different applications, many FFT design styles have been proposed in the literature, in which the memory-based FFT processor is preferred for cost-efficient requirement, especially for large-sized FFTs.
    Multi-banked memories are commonly used in memory-based FFT architectures to improve their throughput rate; however, memory area increases inevitably due to the increasing number of address decoders within the memory module. To solve this problem without sacrificing the resulting throughput rate, this thesis proposes a data relocation mechanism and an efficient memory management scheme to merge the multi-banks into one bank for alleviating the area overhead. The proposed techniques can be applied to single-ported memories for lower area and power requirements, and can be systematically extended to radix-r processing elements. To further reduce the power consumption, a low-power cached-FFT is designed based on the proposed methodology.

    TABLE OF CONTENTS v LIST OF TABLES vii LIST OF FIGURES viii Chapter 1 Introduction 1 1.1 FFT overview 1 1.2 Motivation 3 1.3 Organization of the thesis 3 Chapter 2 FFT Algorithm and Architectures 4 2.1 Algorithm Overview 4 2.1.1 Decimation in Time (DIT) FFT 5 2.1.2 Decimation in Frequency (DIF) FFT 9 2.2 FFT/IFFT Architectures 11 2.2.1 Pipelined architectures 11 2.2.2 Memory-based architectures 12 Chapter 3 Proposed Memory-based Architecture 18 3.1 Area and power analysis of Memory 19 3.2 Temporal data relocation and pseudo-bank concept 21 3.3 Memory addressing scheme with radix-r PE 29 3.4 Mixed Radix-2/4 architecture 35 3.5 Parameterized IP generator 37 3.5.1 Scalable Building Blocks 37 3.5.2 Building block design 38 3.5.3 Verification 40 3.6 Experiment results and comparisons 41 3.6.1 Experimental results for speed and power 41 3.6.2 Comparison of critical path 42 3.6.3 Area comparisons 43 Chapter 4 Low Power FFT Design 46 4.1 Introduction to cached-FFT algorithm 47 4.2 Proposed three-level memory hierarchy scheme 48 4.2.1 Scheduling with re-order buffers for power reduction 48 4.2.2 Three-level memory hierarchy scheme 54 4.3 Experimental results and comparisons 56 Chapter 5 Conclusions and Future Works 59 5.1 Conclusions 59 5.2 Future Works 60 References 61

    [1] ETSI, “Digital Video Broadcasting (DVB); Framing Structure, channel coding and modulation for digital terrestrial television,” ETSI EN 300 744 V1.5.1, Jun. 2004.
    [2] 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., pp. 203-206, Nov. 2006.
    [3] 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.
    [4] Y.-J. Cho, C.-L. Yu, T.-H. Yu, C.-Z. Zhan, and A.-Y. Wu, “Efficient Fast Fourier Transform processor design for DVB-H system,”in Proc. VLSI/CAD Symposium, Aug. 2007.
    [5] B. M. Baas, “A low-power, high-performance, 1024-point FFT processor,” IEEE J. Solid-State Circuits, vol. 34, pp. 380-387, Mar. 1999.
    [6] 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, pp. 911-919, May 2005.
    [7] 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, pp. 484-493, Mar. 2003.
    [8] P.-Y. Tsai, T.-H. Lee and T.-D. Chiueh, “Power-efficient continuous-flow memory-based FFT processor for WiMax OFDM mode,” in Proc. ISPACS, pp. 622-625, 2006.
    [9] S. He, and M. Torkelson, “Design and implementation of a 1024-point pipeline FFT processor,” in Proc. IEEE Custom Integrated Circuits Conf., Santa Clara, CA, USA, pp. 131-134, May 1998,.
    [10] 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.
    [11] Y.-W. Lin, H.-Y. Liu and C.-Y. Lee, “A 1-GS/s FFT/IFFT Processor for UWB Applications,” IEEE J. Solid-State Circuit, vol. 40, no. 8, pp. 1726-1735, Aug. 2005.
    [12] 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.
    [13] S. Lee, D.-B. Kim and S.-C. Park, “Power-efficient design of memory-based FFT processor with new addressing scheme,” in Proc. Int. Symp. on Commu. and Inform. Tech., pp. 678-681, Oct. 2004.
    [14] Y. Ma, “An effective memory addressing scheme for FFT processors,” IEEE Trans. on Signal Processing, vol. 47, pp. 907-911, Mar. 1999.
    [15] J. A. Hidalgo, J. L´opez, F. Arg¨uello, and E. L. Zapata “Area-efficient Architecture for Fast Fourier Transform”, IEEE Trans. Circuits Syst. II, Analog and Digital Signal Processing, vol. 46, no. 2, pp. 187-193, Feb. 1999.
    [16] X. Xiao, E. Oruklu and J. Saniie, “Efficient FFT engine with reduced addressing logic,” in Proc. IEEE EIT, pp. 390-395, May 2007.
    [17] C.-M. Wu, M.-D. Shieh, H.-F. Lo, M.-H. Hu, “Implementation of channel demodulator for DAB system,” in Proc. IEEE Int. Symp. Circuits Syst, vol. 2, pp.137-140, May 2003
    [18] C.-L. Wey, W.-C. Tang, and S.-Y. Lin, “Efficient memory-based FFT architectures for Digital Video Broadcasting (DVB-T/H),” in Proc. Int. Symp. on VLSI Design, Automation, and Test (VLSI-DAT), Hsinchu, Taiwan, Apr. 2007.
    [19] C.-L. Wey, S.-Y. Lin, and W.-C. Tang, “Efficient memory-based FFT architectures for OFDM applications,” in Proc. IEEE EIT, pp. 345-350, May 2007.
    [20] W.-H. Yang, “Design of self-testable and cost-efficient memory-based FFT processors,” M.S. Thesis, Department of Electrical Engineering, National Central University, Taiwan, Jun. 2007.
    [21] H. Saleh, E.-E.Swartzlander, Jr., “A contention-free radix-2 8k-point Fast Fourier Transform engine using single-port SRAMs”, in Proc. IEEE Southeast Conf., pp.497-502, Apr. 2008.
    [22] E.-H. Wold and A.-M. Despain, “Pipeline and parallel pipeline FFT processors for VLSI implementation,” IEEE Trans. Comput., vol. C-33, pp. 414–426, May 1984.
    [23] C.-P. Fan, M.-S. Lee and G.-A. Su, ”A Low multiplier and Multilplication Costs 256-points FFT Implementation with Simplified Radix-24 SDF architecture,“ IEEE Asia-Pacific Conference on Circuits and Systems, Dec. 2006
    [24] S. He and M. Torkelson, “Designing pipeline FFT processor for OFDM (de) modulation,” in Proc. 1998 URSI International Symposium on Signals, Systems, and Electronics, 1998 (ISSSE 98), pp. 257–262, 1998.
    [25] H. Lee and M. Shin, “A high-speed low-complexity two-parallel Radix-24 FFT/IFFT processor for UWB applications,” in Proc. IEEE Asia Solid-State Circuits Conference, Nov. 2007.
    [26] C.-K. Chang, C.-P. Hung and S.-G. Chen, “An efficient memory-based FFT architecture,” in Proc. IEEE Int. Symp. Circuits Syst., vol.2, pp. 129-132, 2003.
    [27] C.-H. Chang, C.-L. Wang and Y.-T. Chang, “A novel memory-based FFT processor for DMT/OFDM applications,” in Proc. IEEE Int. Conf. on Acoustics, Speech, Signal Processing, pp. 3206-3216, March 1999.
    [28] “TSMC 0.18 μm (CL018G) Process 1.8-Volt SAGE-XTM Standard Cell Library Databook,” in Artisan Components, Sep. 2003.
    [29] J.-C. Kuo, C.-H. Wen, C.-H. Lin and A.-Y. Wu, “VLSI Design of a variable-length FFT/IFFT processor for OFDM-Based Communication systems,” EURASIP J. applied Signal Processing, vol. 2003, no. 13, pp. 1306-1316, Dec. 2003.
    [30] Z. Wang and Z. Cui, “A memory efficient partially parallel decoder architecture for quasi-cyclic LDPC codes,” IEEE Trans. On VLSI Syst., vol. 15, no. 4, pp. 483-488, Apr. 2007.
    [31] L. G. Johnson, “Conflict free memory addressing for dedicated FFT hardware,” IEEE Trans. Circuits Syst. II , Exp. Brief, vol. 39, no. 5, pp. 312-316, May 1992.
    [32] J. H. Takala, T. S. Jarvinen amd H. T. Sorokin, “Conflict-free Parallel Memory Access Scheme for FFT Processors,” in Proc. IEEE Int. Symp. Circuits Syst., vol. 4, pp. 524-527, May 2003.

    下載圖示 校內：2013-08-27公開
    校外：2013-08-27公開
    QR CODE