 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：81 、訪客IP：18.216.145.37
姓名 楊禮宗(Li-Tsung Yang) 查詢紙本館藏 畢業系所 電機工程學系在職專班 論文名稱 採用不定資料分布存取方案與基數2/4分裂架構實現記憶體式快速傅立葉轉換運算的晶片電路
(Implementation of Memory-based FFT Using Inconstant-distribution Access Scheme and Split-radix 2/4 Architecture)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 本論文的重點是使用文獻中所發表的記憶體式快速傅立葉轉換運算架構(Memory base FFT) 之分裂基數Split-radix 2/4，結合Hong所發表的普遍化不定資料分布存取方案 [19]，整合出適用於小至16點大到4096或8192點數的快速傅立葉轉換運算電路架構，並適用於無線通訊系統中的正交分頻多工 (OFDM) 多載波調變技術。
採用記憶體快速傅立葉運算架構比管線式快速傅立葉運算架構 (Pipeline base FFT)可節省電路面積、硬體成本、較高的蝴蝶運算單元硬體使用率和較低的存取功率消耗；而使用分裂基數 Split-radix 2/4 理論可減少蝴蝶運算單元 (Butterfly unit) 電路的複雜度，又可減少單一級數Pass運算時間，進而降低總運算時間；同時，記憶體存取方案 (Memory access scheme) 採用Hong所發表的普遍化不定資料分布存取方案，可固定蝴蝶運算單元架構，不需隨每一級數Pass做變動調整，僅需在蝴蝶運算單元和記憶體單位之間的資料交換存取控制電路做規律的邏輯排序。
綜合採取上述分別在演算法理論、運算架構複雜度、運算單元和記憶單元的硬體面積等優點，構思出本電路並實現，先後以 C++、MATLAB、Verilog HDL語言推導各種點數的正確性，最後再以 RTL Simulation、ISE 14.4進行模擬和合成 (Synthesis)，以及使用Xilinx Virtex 5 XC5VLX330 FPGA board進行驗證。
摘要(英) The focus of this thesis is to use the split-radix 2/4 published in the memory base fast Fourier transform (FFT) operation architecture. It combines with the generalized inconstant-distribution access scheme proposed by Hong to realize a circuit for the FFT operation ranging from as small as 16 points to as large as 4096 or 8192 points. In addition, it suits for orthogonal frequency division multiplexing (OFDM) multi-carrier modulation technology in wireless communication systems.
Comparing to pipeline-based FFT architecture, memory-based FFT architecture can obtain lower hardware cost, higher usage ratio of hardware in butterfly unit, and lower power consumption. While using split-radix 2/4 algorithm to reduce complexity of the butterfly unit circuit, the single-pass operation time can also be reduced, thereby reducing the total operation time. At the same time, the memory access scheme using the generalized inconstant- distribution access scheme proposed by Hong can have fixed butterfly operations. The butterfly unit structure does not have necessary to be adjusted with each Pass. It only needs to perform regular logical ordering on the data exchange access control circuit between the butterfly operation unit and the memory unit.
Based on the above-mentioned advantages of the algorithm, considering complexity of computing architecture, hardware area of computing unit and memory unit, etc., this circuit is conceived and implemented, and the verification of various FFT points is derived in C ++, MATLAB, Verilog HDL, and finally uses RTL Simulation, ISE 14.4 for behavior simulation and Circuit Synthesis, and Xilinx Virtex 5 XC5VLX330 FPGA board for evaluation.
關鍵字(中) ★ 記憶體存取方案
★ 分裂基數
★ 快速傅立葉關鍵字(英) ★ Memory access scheme
★ Split-radix
★ FFT論文目次 摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vii
表目錄 ix
一、 導言 1
1-1 研究背景 1
1-1-1 離散時間系統 1
1-1-2 數位系統硬體實現 2
1-2 研究動機 4
1-2-1 Cooley-Tukey 演算法點數降解的數學推導 (以 Decimation-in-frequency 為例) 6
1-2-2 Cooley-Tukey 演算法的硬體實現性 7
1-3 研究目標與論文架構 9
二、 快速傅利葉轉換 (FFT) 理論 10
2-1 Radix-2 DIF FFT 演算法 10
2-2 Radix-4 / Radix-22 DIF FFT 演算法 12
2-3 Radix-8 / Radix-23 DIF FFT 演算法 13
2-4 Split-Radix 2/4 DIF FFT 演算法 16
2-5 Split-Radix 2/8 DIF FFT 演算法 18
2-6 比較與總結 19
三、 記憶體式快速傅利葉轉換架構設計 21
3-1 記憶單元 22
3-1-1 單一記憶單元 - 存取方案優化 22
3-1-2 雙記憶單元 - 運算空間擴充 23
3-1-3 比較與總結 24
3-2 記憶體結構 24
3-2-1 雙記憶體 (Dual-memory) 架構 24
3-2-2 單一記憶體 (Single-memory) 架構 25
3-2-3 快取記憶體 (Cached-memory) 架構 25
3-2-4 乒乓快取記憶體 (Ping-Pong Cache Memory) 架構 26
3-3 比較與總結 26
四、 記憶體存取方案 28
4-1 概論 28
4-2 固定資料分布 (Constant data distribution) 存取方案 29
4-2-1 採用奇偶檢驗作為區別資料指標以映射至不同 Bank 指標 29
4-2-2 步距固定的上數計數器輸出蝶形運算指標映射到資料指標 30
4-2-3 桶狀移位器產生資料指標和加入交換功能區塊以映射出列指標 30
4-2-4 移位插入通過多工器陣列 (SIB MUX array) 產生資料指標 31
4-2-5 Bit-wise XOR operation 映射 Bank 指標 31
4-3 不定資料分布 (Inconstant data distribution) 存取方案 33
4-3-1 SFG 模型中相同 Pass 的 Edge 排列結構具有全域對稱性 33
4-3-2 SFG 蝶形運算結構的 Edge 連接在所有 Pass 中都相同 34
4-4 所提出的適用於分裂基數 2/4 之存取方案 37
4-5 總結 40
五、 硬體實現與驗證 42
5-1 設計流程 42
5-2 硬體架構設計 43
5-3 演算法模擬 (C++、MATLAB) 48
5-4 FPGA 驗證 50
5-5 效能驗證 52
六、 結論 55
參考文獻 56參考文獻 [1] 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), pp. III 561–564, May 2004.
[2] S. He and M. Torkelson, ”A New approach to Pipeline FFT processor”, in Proc. Int. Parallel Processing Symp., pp. 766–770, 1996.
[3] S. He and M. Torkelson, “Designing pipeline FFT processor for OFDM (de)modulation”, in Proc. URSI Int. Symp. Signals Syst. Elect., pp. 257–262, 1998.
[4] James W.Cooley, and John W. Tukey, ”An algorithm for the machine calculation of complex Fourier series”, Mathematics of Computation, Vol. 19, no. 90, pp. 297301, Apr. 1965.
[5] P. Duhamel and H. Hollmann, “Split-radix FFT Algorithm”, Eletronic Letters, Vol.20, No.1 pp. 14-16, Jan. 1984.
[6] Trio Adiono, Aditya F. Ardyanto, Nur Ahmadi, Idham Hafizh, Septian G. P. Putra “An SoC Architecture for Real-Time Noise Cancellation System Using Variable Speech PDF Method”, International Journal of Electrical and Computer Engineering (IJECE) , Vol. 5, No. 6, pp. 1336~1346, December 2015.
[7] B. M. Bass, “A low-power, high-performance, 1024-point FFT processor”, IEEE J.
Solid-State Circuits, Vol. 34, no. 3, pp. 380–387, Mar. 1999.
[8] 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, pp. 203–206, Nov. 2006.
[9] 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, pp. 1989–1992., Apr. 1988.
[10] B. M. Bass, “A low-power, high-performance, 1024-point FFT processor”, IEEE J.Solid-State Circuits, Vol. 34, no. 3, pp. 380–387, Mar. 1999.
[11] M. C. Pease, “Organization of large scale Fourier processors”, IEEE Trans. Circuits Syst. Vol. 16, pp. 474–482, July 1969.
[12] D. Cohen, “Simplified control of FFT hardware”, IEEE Trans. Acoust., Speech Signal Processing, Vol. ASSP-24, pp. 577-579, Dec. 1976.
[13] L. G. Johnson, “Conflict free memory addressing for dedicated FFT hardware”, IEEE Trans. Circuits Syst. II, Vol. 39, pp. 312–316, May 1992.
[14] C. P. Hung and S. G. Chen, “Design of an efficient variable length FFT processor” , IEEE Int. Symp. on Circuits Syst., Vol. 2, pp. 833-836, May 2004.
[15] J. H. Takala, T. S. Jarvinen, and H. T. Sorokin, “Conflict-free parallel memory access scheme for FFT processors”, IEEE Int. Symp. on Circuits Syst., Vol. 4, pp. 524-527, May 2003.
[16] X. Xiao, E. Oruklu, and J. Saniie, “An efficient FFT engine with reduced addressing logic”, IEEE Trans. Circuits Syst. II, Vol. 55, no 11, pp. 1149–1153, November 2008.
[17] X. Xiao, E. Oruklu, and J. Saniie, “Fast memory addressing scheme for radix-4 FFT implementation”, IEEE Int. Conf. Electro/Information Tech., pp. 437–440, June 2009.
[18] Weihua Zheng, Kenli Li, and Keqin Li, “Scaled Radix-2/8 Algorithm for Efficient Computation of Length-N = 2m DFTs”, IEEE TRANSACTIONS ON SIGNAL PROCESSING, Vol. 62, no. 10, May 15, 2014.
[19] 洪孟嶢， “記憶體式快速傅立葉轉換運算架構的普遍化不定資料分布存取方案”， 國立中央大學，電機工程研究所碩士論文，民國104年6月。
[20] Yutian Zhao, Ahmet T. Erdogan and Tughrul Arslan, “A low-power and domain-specific reconfigurable FFT fabric for system-on-chip applications”, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, 18 April 2005.
[21] 楊耀先， “可自我測試且具成本效益之記憶體式快速傅利葉轉換處理器設計” ， 國立中央大學，電機工程研究所碩士論文，民國96年7月。
[22] Y. Zhao, A.T. Erdogan, and T. Arslan, ”A novel low-power reconfigurable FFT processor”, in Proc. IEEE Int. Symposium on Circuits and Systems (ISCAS), pp.41 – 44, May 2005.
[23] Y.H. Lee, T.H. Yu, K.K. Huang and A.Y. Wu, “Rapid IP design of variable-length cached-FFT processor for OFDM-based communication systems”, in Proc. IEEE Workshop on Signal Processing Systems Design and Implementation, pp. 62 – 65, Oct 2006.
指導教授 薛木添(Muh-Tian Shiue) 審核日期 2020-1-20 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit