高效能混合式多重路徑延遲迴授與多重路徑延遲交換架構和2^k基底串行交換之快速傅利葉轉換處理器設計

An Efficient Mixed MDF and MDC FFT Architecture and New Radix-2^k Serial Commutator FFT Architectures

胡欣芸

快速傅利葉轉換 ； 管線式架構 ； 多重路徑延遲迴授 ； 多重路徑延遲交換 ； FFT ； Pipelined architecture ； Multipath delay feedback ； Multipath delay commutator

交通大學電子工程系所學位論文

2016年

碩士

陳紹基

英文

近年，正交分頻多工 (Orthogonal Frequency Division Multiplexing； OFDM) 技術被廣泛的應用於各式通訊系統中，例如無線都會區域網路(Wireless Metropolitan Area Network: WMAN) 、無線區域網路 (Wireless Local Area Network； WLAN) 、無線個人區域網路 (Wireless Personal Area Network: WPAN) 及第四代行動通訊系統 (Long Term Evolution； LTE) 等等。在正交分頻多工系統中，快速傅立葉轉換 (Fast Fourier Transform； FFT)是其中不可或缺的主要運算之一，由於現代的通訊系統的資料傳輸率越來越高，使得快速傅立葉轉換處理器的吞吐量也必須提高，因此設計一個在高吞吐量下減少面積複雜度的快速傅立葉轉換處理器，為目前主要的設計議題，因此為了提高快速傅立葉轉換處理器的吞吐量，本論文使用管線化的快速傅立葉轉換處理器設計，並設計出下列兩個新穎的快速傅立葉轉換處理器設計: 藉由觀察，本論文發現，多重路徑延遲迴授架構與多重路徑延遲交換架構的優缺點可以互補，像是多重路徑延遲迴授架構擁有零調序記憶體的優點，而多重路徑延遲交換架構卻需要調序記憶體將輸入訊號做調序，或是多重路徑延遲交換架構使用到較少量的蝶型處理器，而多重路徑延遲迴授架構所使用到的蝶型處理器量是多重路徑延遲交換架構的兩倍，因此本論節這兩個架構提出一個混合多重路徑延遲迴授和多重路徑延遲交換的架構(mixed MDF and MDC FFT architecture; MDFC)，此架構可同時擁有多重路徑延遲迴授架構與多重路徑延遲交換架構的優點，另外本論文使用前饋式Radix-3的蝶型運算單元(Butterfly unit; BU)使此架構可用於處理多倍平行度2^k×3點FFT。 針對基底-2^k的快速傅利葉轉換演算法，擴充[8]所提出的連續交換之快速傅利葉轉換處理器，並觀察各個傳統基底-2^k的快速傅利葉轉換演算法，將連續交換之快速傅利葉轉換處理器做優化處理，提出基底-2^2的連續交換之快速傅利葉轉換處理器、基底-2^3的連續交換之快速傅利葉轉換處理器和基底-2^4的連續交換之快速傅利葉轉換處理器。

Recently, OFDM (Orthogonal Frequency Division Multiplexing) has been widely used in various communication systems, such as WMAN (Wireless Metropolitan Area Network), WLAN (Wireless Local Area Network), WPAN (Wireless Personal Area Network), and 4G mobile communication systems (Long Term Evolution ; LTE). In Orthogonal Frequency Division Multiplexing communication systems, Fast Fourier Transform (FFT) is an important computation in this system. Since the data transmission rate of communication systems is higher than ever, we need to promote throughput of fast fourier transform processor. It is an important issue that designing a FFT processor with low area complexity and high throughput. Since we want to design a high throughput FFT processor, we proposed two kinds of pipelined FFT architecture as below: It can be observed that pros of MDF and MDC architecture can make up each other’s cons. As such, we mix MDF and MDC architecture and propose a new architecture that has both advantages of fewer butterfly units like MDC FFT and free of input memory like MDF FFT. Additionally, we use the folded and reused FFT processor technique in [13] to optimize processor of MDF architecture. The feedforward radix-3 PE in [21] is adopted so that MDFC architecture can perform 2^r×3-point FFT. We also put a variable length unit in feedforward radix-3 PE so that the radix-3 PE can be used to perform 2^r-point FFT. We extend the serial commutator FFT architecture which is proposed in [8]. According to each conventional radix-2^k FFT algorithm, we optimized radix-2^k serial commutator FFT architectures. We proposed the radix-2^2 serial commutator FFT architecture, the radix-2^3 serial commutator FFT architecture and the radix-2^4 serial commutator FFT architecture in the thesis.

1. [1] James. W. Cooley and John W. Tukey, “An algorithm for the machine calculation of complex Fourier series”, Math. Comp., vo l. 19, pp. 297 -301, 1965 .
   連結：
2. [4] F. Qureshi, M. Garrido and O. Gustafsson, “Unified architecture for 2, 3, 4, 5, and 7-pointDFTs based on Winograd Fourier transform algorithm”, Electronics Letters, vol. 49, no. 5, February 2013.
   連結：
3. [6] S.N. Tang, J.W. Tsai, and T.Y. Chang, “A 2.4-GS/s FFT processor for OFDM-Based WPAN applications,” IEEE Trans. Circuits Syst. II, vol. 6, no. 57, pp. 451-455, June. 2010.
   連結：
4. [7] Yu-Wei Lin and Chen-Yi Lee, “Design of an FFT/IFFT Processor for MIMO OFDM Systems”, IEEE Trans. On Circuit and Systems-I: Regular Papers, vol. 54, no. 4, pp. 807-815, April 2007.
   連結：
5. [8] M. Garrido; S. J. Huang; S. G. Chen; O. Gustafsson, "The Serial Commutator (SC) FFT," in IEEE Transactions on Circuits and Systems II: Express Briefs , vol.PP, no.99, pp.1-1
   連結：
6. [9] E. E. Swartzlander, W. K. W. Young, and S. J. Joseph, “A radix-4 delay commutators for fast Fourier transform processor implementations” IEEE J. Solid-State Circuits, vol. 19, no. 5, pp. 702-709, Oct. 1984.
   連結：
7. [10] M. Garrido, J. Grajal, M. A. Sanchez and O. Gustafsson, "Pipelined Radix- 2^k Feedforward FFT Architectures," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 21, no. 1, pp. 23-32, Jan. 2013.
   連結：
8. [11] B. M. Baas, “A generalized cached-FFT algorithm,” in Proc. IEEE Int. Conference on Acoustics, Speech, and Signal Processing (ICASSP), vol. 5, pp. 89-92, 2005.
   連結：
9. [12] 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.
   連結：
10. [15] Chu Yu and Mao-Hsu Yen, “Area-Efficient 128- to 2048/1536-Point Pipeline FFT Processor for LTE and Mobile WiMAX Systems”, IEEE Trans. On Very Large Scale Integration Systems (VLSI), issue. 99, pp. 585–589, September 2014.
    連結：
11. [16] X. Liu, F. Yu, and Z. Wang, “’A pipelined architecture for normal I/O order FFT’,” Journal of Zhejiang University - Science C, vol. 12, no. 1, pp. 76–82, Jan. 2011.
    連結：
12. [18] T. Lenart and V. Öwall, “Architectures for dynamic data scaling in 2/4/8K pipeline FFT cores,” IEEE Trans. VLSI Syst., vol. 14, no. 11, pp. 1286–1290, Nov. 2006.
    連結：
13. [19] T. Adiono, M. S. Irsyadi, Y. S. Hidayat, and A. Irawan, “’64-point fast efficient FFT architecture using radix-2^3 single path delay feedback’,” Proc. Int. Conf. Electrical Engineering Informatics, vol. 02, pp. 654 – 658, Aug. 2009.
    連結：
14. [20] C.-P. Fan, M.-S. Lee, and G.-A. Su, “A low multiplier and multiplication costs 256-point FFT implementation with simplified radix-2^4 SDF architecture,” in Proc. IEEE Asia-Pacific Conf. Circuits Syst., Dec. 2006, pp. 1935 – 1938.
    連結：
15. [22] M. Garrido, J. Grajal and O. Gustafsson, "Optimum Circuits for Bit Reversal," in IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 58, no. 10, pp. 657-661, Oct. 2011.
    連結：
16. [24] Chin-Long Wey, Shin-Yo Lin and Wei-Chien Tang, "Efficient memory-based FFT processors for OFDM applications," 2007 IEEE International Conference on Electro/Information Technology, Chicago, IL, 2007, pp. 345-350.
    連結：
17. Bibliography
18. [2] A. V. Oppenheim and R. W. Schafer, Discrete-time Signal Processing, NJ:
19. Prentice-Hall, 1999.
20. [3] Johan Lofgren and Peter Nilsson, “On Hardware Implementation of Radix 3 and
21. Radix 5 FFT Kernels for LTE systems”, NORCHIP Conference, pp.1-4, November 2011.
22. [5] Yu-Wei Lin, Hsuan-Yu Liu and Chen-Yi Lee, “A 1-GS/s FFT/IFFT Processor for
23. UWB Applications”, IEEE Journal of Solid-state Circuits, vol. 40, no. 8, August 2005.
24. [13] Bo-Wei Wang, Tsai. 2014 Design of Improved MDF FFT Processor with Low-Area Complexity. Master thesis. Hsinchu, Taiwan: National Chiao Tung University, Department of Electronics Engineering and Institute of Electronics.
25. [14] Thomas Lenart and Viktor Owall, “A Pipelined FFT Processor using Data Scaling with Reduced Memory Rquirement”,In Proc. NORCHIP,2002
26. [17] Sau-Gee Chen and Shen-Jui Huang, “A Novel Memoryless Rotator Architecture for FFT Computation”, Department of Electronic Engineering, National Chiao Tung University, Ph.D. dissertation, Jun. 2012.
27. [21] Wei-Lun, Tsai. 2015 A Parallel Mixed-Radix Feedforward FFT Processor for 4G Communication System. Master thesis. Hsinchu, Taiwan: National Chiao Tung University, Department of Electronics Engineering and Institute of Electronics.
28. [23] M. Garrido, J. Grajal, and O. Gustafsson, “Optimum circuits for bit reversal,” IEEE Trans. Circuits Syst. II, vol. 58, no. 10, pp. 657 –661, Oct. 2011.