臺灣博碩士論文加值系統

在本論文中，我們提出二種快速傅立葉轉換處理器設計。首先，為了提高串列交換架構的吞吐率，提出一個多倍平行之基底-2串列交換架構設計，亦稱為多重路徑串列交換架構。為了降低硬體成本，將FFT演算法從基底-2延伸至高基底- ，且改善傳統基底-2^4演算法，提出一個改良式基底- 串列交換處理單元。利用改良式基底-2^4處理單元，設計一個四倍平行之128點基底-2^4串列交換架構。且針對最新IEEE 802.11ax標準，提出一個可提供1.2G sample/s的低複雜度八倍平行之混合基底2048點快速傅立葉轉換處理器，使用TSMC 90nm製程技術，合成面積為0.746mm^2 ，在工作頻率150MHz下，功率消耗為37.25mW 。第二個設計是針對LTE上行系統使用的單載波分頻多重接取(SC-FDMA)技術，其快速傅立葉轉換點數包含2、3、5因子，因此本文提出一個二倍平行之共享式3點或5點快速傅立葉轉換處理單元，並將此處理單元應用在多重路徑延遲交換架構，提出一個適用於多平行度之混合基底 點快速傅立葉轉換處理器架構設計方案，此架構具有低延遲、高吞吐率優點。

This work presents two different FFT processor designs. First, to enhance the throughput of the original serial commutator (SC) pipelined architecture, we propose parallel radix-2 serial commutator designs, called multi-path serial commutator (MSC). First, in order to achieve lower hardware complexity, we extend our previous radix-2 architecture to radix- architecture. We improve traditional radix-2^4 algorithm and design an area-efficient modified radix-2^4 processing element used in SC architecture. Next, we design a 4-parallel radix-2^4 128-point SC FFT processor by using the above mentioned processing element. In addition, we proposed a low-complexity processor for 8-parallel mixed-radix 2048-point FFT with throughput of 1.2G sample/s for the newest IEEE 802.11ax WLAN standard. The proposed design is implemented with TSMC 90 nm process technology. The area and power consumption of the synthesis results are respectively 0.746mm^2 and 37.25mW under 150MHZ working frequency. In the second design, a shared 2-parallel 3-point and 5-point FFT processing element is proposed, for the consideration of FFT sizes required in LTE/LTE-A system which include 2, 3 and 5 factors. By applying the prime factor PE to multi-path delay commutator architecture, we propose a parallel mixed-radix -point FFT processor design. This architecture has advantages of low latency and high throughput.

目錄
摘要................................................................................................................................ I
ABSTRACT.................................................................................................................II
致謝............................................................................................................................. IV
目錄...............................................................................................................................V
圖目錄......................................................................................................................VIII
表目錄........................................................................................................................XII
第1章緒論 .................................................................................................................1
1.1 研究背景與動機...........................................................................................................................1
1.2 論文架構.......................................................................................................................................2
第2章快速傅立葉轉換(FFT)演算法及架構...........................................................3
2.1 時域上錯置(DIT) FFT演算法...................................................................................................3
2.2 頻域上錯置(DIF) FFT演算法....................................................................................................5
2.3 高基底(HIGH-RADIX) FFT演算法................................................................................................7
2.3.1 Radix-4/22 FFT演算法......................................................................................................7
2.3.2 Radix-8/32 FFT演算法.......................................................................................................8
2.3.3 Radix-42 DIF FFT演算法................................................................................................10
2.4 質數(PRIME)點數FFT演算法...................................................................................................10
2.4.1 3點FFT演算法................................................................................................................. 11
2.4.2 5點FFT演算法.................................................................................................................12
2.5 快速傅立葉轉換FFT架構........................................................................................................13
2.5.1 單一路徑延遲回授(SDF) 管線式(pipelined) FFT架構.................................................13
2.5.2多重路徑延遲回授(MDF) 管線式(pipelined) FFT架構................................................14
2.5.3串列交換(SC)管線式(pipelined) FFT架構........................................................................14
2.5.4多重路徑延遲交換(MDC) 管線式(pipelined) FFT架構................................................15
第3章管線式radix-2k之多重路徑串列交換FFT架構....................................17
3.1 RADIX-2多重路徑串列交換FFT架構......................................................................................18
3.1.1 架構設計原理.....................................................................................................................18
3.1.2 多倍平行度radix-2多重路徑串列交換架構...................................................................23
3.1.3 優化乘法器複雜度及數量.................................................................................................25
3.1.4 輸入輸出自然排序的電路設計.........................................................................................28
3.2 延伸至radix2k−多重路徑串列交換FFT架構........................................................................30
3.2.1 Radix2k−處理單元........................................................................................................30
3.2.2 優化4Radix2−演算法....................................................................................................32
3.2.3 Radix-2k多重路徑串列交換FFT....................................................................................34
3.3 多重路徑管線式FFT架構比較................................................................................................38
3.4 實現結果.....................................................................................................................................39
3.5 總結.............................................................................................................................................41
第4章應用於無線區域網路之多重路徑串列交換FFT.......................................42
4.1 現有多輸入輸出快速傅立葉轉換的處理方式.........................................................................43
4.2 演算法和硬體設計考量.............................................................................................................45
4.3 架構設計.....................................................................................................................................47
4.2.1 模組1、2 ...........................................................................................................................48
4.2.2 模組3 .................................................................................................................................49
4.2.3 架構多點數設計方案.........................................................................................................52
4.2.4 模組4 .................................................................................................................................53
4.4 實踐結果.....................................................................................................................................54
4.5 總結.............................................................................................................................................57
第5章應用於第四代行動通訊上行系統之多平行度...........................................58
5.1 共享式平行化3/4/5點FFT處理單元......................................................................................60
5.1.1 平行化5點FFT處理單元................................................................................................60
5.1.2 共享式3/4/5點FFT處理單元........................................................................................63
5.2 多倍平行235αβγ點多重路徑延遲交換FFT架構設計...........................................................65
5.2.1 演算法................................................................................................................................65
5.2.2架構設計.............................................................................................................................67
5.3 應用於第四代行動通訊上行系統之FFT架構設計................................................................68
5.4 總結.............................................................................................................................................72
第6章結論與未來展望...........................................................................................73
6.1 結論.............................................................................................................................................73
6.2 未來展望.....................................................................................................................................74
參考文獻......................................................................................................................75

參考文獻
[1] J. W. Cooley and J. W. Turkey, “An algorithm for the machine calculation of complex Fourier series,” Math Comput., vol. 19, pp. 297-301, 1965.
[2] C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," in Proceedings of the IEEE, vol. 56, no. 6, pp. 1107-1108, June 1968.
[3] S. Bouguezel, M. O. Ahmad and M. N. S. Swamy, "Improved radix-4 and radix-8 FFT algorithms," 2004 IEEE International Symposium on Circuits and Systems (IEEE Cat. No.04CH37512), 2004, pp. III-561-4 Vol.3.
[4] Shousheng He and M. Torkelson, "Designing pipeline FFT processor for OFDM (de)modulation," 1998 URSI International Symposium on Signals, Systems, and Electronics. Conference Proceedings (Cat. No.98EX167), Pisa, 1998, pp. 257-262.
[5] Hanho Lee and Minhyeok Shin, "A high-speed low-complexity two-parallel radix-24 FFT/IFFT processor for UWB applications," 2007 IEEE Asian Solid-State Circuits Conference, Jeju, 2007, pp. 284-287.
[6] H. G. Myung, J. Lim and D. J. Goodman, "Single carrier FDMA for uplink wireless transmission," in IEEE Vehicular Technology Magazine, vol. 1, no. 3, pp. 30-38, Sept. 2006.
[7] E. H. Wold and A. M. Despain, "Pipeline and Parallel-Pipeline FFT Processors for VLSI Implementations," in IEEE Transactions on Computers, vol. C-33, no. 5, pp. 414-426, May 1984.
[8] Shousheng He and M. Torkelson, "A new approach to pipeline FFT processor," Proceedings of International Conference on Parallel Processing, Honolulu, HI, 1996, pp. 766-770.
[9] Song-Nien Tang, Chi-Hsia and Tsin-Yuan Chang, ”An Area- and Energy-Efficient Multimode FFT Processor for WPAN/WLAN/WMAN Systems”, IEEE Journal of Solid-state Circuits, vol. 47, no. 6, June 2012.
[10] Yu-Wei Lin, Hsuan-Yu Liu and Chen-Yi Lee, “A 1-GS/s FFT/IFFT Processor for UWB Applications”, IEEE Journal of Solid-state Circuits, vol. 40, no. 8, August 2005.
[11] Chia-Hsiang Yang, Tsung-Han Yu, and Dejan Marković, “Power and Area Minimization of Reconfigurable FFT Processors - A 3GPP-LTE Example”, IEEE Journal of Solid-state Circuits, vol. 47, no. 3, March 2012.
[12] Y. W. Lin and C. Y. Lee, "Design of an FFT/IFFT Processor for MIMO OFDM Systems," in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 54, no. 4, pp. 807-815, April 2007.
[13] 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," in IEEE Journal of Solid-State Circuits, vol. 43, no. 5, pp. 1260-1273, May 2008.
[14] M. Garrido, S. J. Huang, S. G. Chen and O. Gustafsson, "The Serial Commutator FFT," in IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 63, no. 10, pp. 974-978, Oct. 2016.
[15] Hsin-Yun Hu, “An efficient mixed MDF and MDC FFT architecture and a new radix-2^