臺灣博碩士論文加值系統

本論文中，把之前存在的可以應用在5G 通訊架構的部分輸出輸入快速傅立葉轉換處理器，做更進一步的優化處理，且大幅降低了面積，仍然維持一樣的功能，且在之前的架構中，都是應用在2^k 的點數中，此論文也把部分輸入輸出的架構進一步套用在3×2^k 的點數中，讓這個架構可以應用在5G 通訊架構中更多的規格點數中，最後為了驗證架構的正確性，本論文使用TSMC 45nm 製程技術設計一個八倍平行但2048 點基底部分輸出的快速傅立葉轉換處理器，其結論跟我們分析硬體複雜度的結論一致，都在不影響功能的條件下，有效率的省下可觀的面積。

接著，隨著新世代通訊技術的發展，快速傅立葉轉換處理器的點數更趨於廣泛，且快速傅立葉轉換處理器通常都會搭配位元反序排序電路使用以確保資料順序，所以我們提出了可以應用在廣義的非2 次方點數的位元反序排序電路，也就是最廣義的情形，使得設計各種點數的快速傅立葉轉換處理器都可以搭配使用，也期望可以應用在現今5G 以及甚至未來6G 的通訊架構中。

In this work, we refine the previous existing partial FFT design, which can be used in 5G NR. The proposed design lowers the area significantly while keeping the same functionality. Furthermore, the previous partial FFT architecture is only for 2^k points. Here, we extend and
propose a partial FFT architecture for 3×2^k points. Finally, to validate the correctness of our architecture,
we use TSMC 45 nm process and design an 8-parallel 2048-points partial output FFT. The result is consistent with our analysis on hardware complexity, as expected we efficiently
save considerable area and increase the speed performance.

Additionally, with the quick development of new generation communication systems, the specification of the FFT size is going to be more general, so are the associated bit reversal
permutation circuits to get data in the natural order or bit-reversed order. Therefore, we propose a circuit and a procedure to calculate the bit reversal for most general case of non-power-of-two points to be applied to advanced systems such as 5G-NR systems that contains FFT factors of 3
and 5, and future communication systems.

摘要 i
Abstract ii
Acknowledgement iii
Table of Contents iv
List of Figures vi
List of Tables ix
1 Introduction 1
1.1 Background 1
1.2 Main Contributions 2
1.2.1 2k and 3 × 2k point Multi-path Partial FFT Architecture 2
1.2.2 Bit Reversal Circuits for Non-Power-of-two FFTs 2
1.3 Thesis Organization 2
2 Review of FFT Algorithms 3
2.1 Radix-2 DIT/DIF FFT Algorithms 3
2.1.1 Decimation-in-time (DIT) FFT Algorithm 3
2.1.2 Decimation-in-frequency (DIF) FFT Algorithm 5
2.2 High-Radix FFT Algorithms 7
2.2.1 Radix-4 FFT Algorithms 7
2.2.2 Radix-8 FFT Algorithms 8
2.2.3 Radix-2k FFT algorithms 9
2.3 Non-power-of-two FFT Algorithms 10
2.3.1 Radix-3 FFT Algorithm 10
2.3.2 Radix-5 FFT Algorithm 11
3 Review of FFT Architectures 13
3.1 Single-path Delay Feedback (SDF) Architecture 13
3.2 Multi-path Delay Feedback (MDF) Architecture 14
3.3 Multi-path Delay Commutator (MDC) Architecture 14
3.4 Serial Commutator (SC) Architecture 16
4 Partial FFT Architecture for N = 3 × 2k and N = 2k 18
4.1 Existing Partial FFT Architecture and Motivation 18
4.1.1 Introduction of OFDMA/SC-FDMA 19
4.1.2 Existing Partial Input/Output FFT Architectures 21
4.2 Applying the Idea of Partial FFT to N = 3 × 2k 28
4.2.1 Partial Input FFT of N = 3 × 2k 29
4.2.2 Partial Output FFT of N = 3 × 2k 34
4.3 Proposed N = 2k Refined Partial Output FFT Architecture 38
4.3.1 Refined Approach of Existing Partial Output FFT 38
4.3.2 Formal Proof of the Refined Approach 46
4.3.3 Proposed Refined Partial Output FFT Architecture 49
4.4 Implementation Result and Comparison 49
5 Bit Reversal Circuits for Non-Power-of-Two FFTs 51
5.1 Background Knowledge Review 52
5.1.1 Review of Basic Data Flow Concept 52
5.1.2 Introduction of Existing Bit-Reversal Circuit in N = 2n 55
5.2 Proposed approach for Bit-Reversal in N = 3 × 2k 57
5.2.1 Derivation of t − b Exchange Circuit 58
5.2.2 Whole Architecture of Bit Reversal in N = 3 × 2k 64
5.3 General Bit Reversal for Non-Power-of-Two 68
5.3.1 General same type exchange circuit 68
5.3.2 General different type flip circuit 74
5.3.3 General Bit Reversal approach 78
6 Conclusion and Future Works 84
6.1 Conclusion 84
6.2 Future Works 84
References 86

[1] N. Instruments, “Introduction to 802.11ax high-efficiency wireless,” Jul. 2017, https:// www.ni.com/ zh-tw/ innovations/ white-papers/ 16/ introduction-to-802-11ax-highefficiency-wireless.html.
[2] R. Stacey, “Ieee 802.11-15-0132-17-00ax-spec-framework,” May 2016, https:// mentor. ieee.org/802.11/dcn/15/11-15-0132-17-00ax-spec-framework.docx.
[3] C.-Y. Kuo, “An efficient parallel radix-3×2kserial commutator and a radix-2k partial input fft architecture for ofdma system,” Master’s thesis, National Yang Ming Chiao Tung University, Department of Electronics Engineering and Institute of Electronics, Sep. 2018.
[4] S.-C. Lin, “Design of partial input/output mdc and memory based fft processors for ofdma systems,” Master’s thesis, National Yang Ming Chiao Tung University, Department of Electronics Engineering and Institute of Electronics, Dec. 2019.
[5] W. Tsai, S. Chen, and S. Huang, “Reconfigurable radix-2k × 3 feedforward FFT architectures,” in Proc. IEEE Int. Symp. Circuits Syst., May 2019, pp. 1–5.
[6] 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.
[7] G.-T. Deng, “A radix-2k multi-path serial commutator and 532-point serial commutator fft processor,” Master’s thesis, National Yang Ming Chiao Tung University, Department of Electronics Engineering and Institute of Electronics, Sep. 2021.
[8] J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput., vol. 19, no. 90, pp. 297–301, Apr. 1965.
[9] M. Garrido, J. Grajal, M. A. Sánchez, and O. Gustafsson, “Pipelined radix-2k feedforward FFT architectures,” IEEE Trans. VLSI Syst., vol. 21, no. 1, pp. 23–32, Jan. 2013.
[10] M. Garrido, “A new representation of FFT algorithms using triangular matrices,” IEEE Trans. Circuits Syst. I, vol. 63, no. 10, pp. 1737–1745, Oct. 2016.
86
[11] J. Löfgren and P. Nilsson, “On hardware implementation of radix 3 and radix 5 fft kernels for lte systems,” in 2011 NORCHIP, 2011, pp. 1–4.
[12] M. Garrido, R. Andersson, F. Qureshi, and O. Gustafsson, “Multiplierless unity-gain SDF FFTs,” IEEE Trans. VLSI Syst., vol. 24, no. 9, pp. 3003–3007, Sep. 2016.
[13] M. Garrido, S.-J. Huang, S.-G. Chen, and O. Gustafsson, “The serial commutator (SC) FFT,” IEEE Trans. Circuits Syst. II, vol. 63, no. 10, pp. 974–978, Oct. 2016.
[14] N. Li and N. van der Meijs, “’A Radix 22 based parallel pipeline FFT processor for MBOFDM UWB system’,” in Proc. IEEE Int. SoC Conf., Sep. 2009, pp. 383 – 386.
[15] J. Lee, H. Lee, S. in 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., May 2006, pp. 210–213.
[16] S.-I. Cho, K.-M. Kang, and S.-S. Choi, “Implemention of 128-point fast Fourier transform processor for UWB systems,” in Proc. Int. Wireless Comm. Mobile Comp. Conf., Aug. 2008, pp. 210–213.
[17] C.-H. Yang, T.-H. Yu, and D. Markovic, “Power and area minimization of reconfigurable FFT processors: A 3GPP-LTE example,” IEEE J. Solid-State Circuits, vol. 47, no. 3, pp.
757–768, Mar. 2012.
[18] 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. 57, no. 6, pp. 451–455, Jun. 2010.
[19] J. Wang, C. Xiong, K. Zhang, and J. Wei, “A mixed-decimation MDF architecture for radix- 2k parallel FFT,” IEEE Trans. VLSI Syst., vol. 24, no. 1, pp. 67–78, Jan. 2016.
[20] M. Sánchez, M. Garrido, M. López, and J. Grajal, “Implementing FFT-based digital channelized receivers on FPGA platforms,” IEEE Trans. Aerosp. Electron. Syst., vol. 44, no. 4, pp. 1567–1585, Oct. 2008.
[21] M. Garrido, S. J. Huang, and S. G. Chen, “Feedforward FFT hardware architectures based on rotator allocation,” IEEE Trans. Circuits Syst. I, vol. 65, no. 2, pp. 581–592, Feb. 2018. 87
[22] M. Garrido, J. Grajal, and O. Gustafsson, “Optimum circuits for bit-dimension permutations,” IEEE Trans. VLSI Syst., vol. 27, no. 5, pp. 1148–1160, May 2019.
[23] M. S. Afaqui, E. Garcia-Villegas, and E. Lopez Aguilera, “Ieee 802.11ax: Challenges and requirements for future high efficiency wifi,” IEEE Wireless Communications, vol. 24, no. 3, pp. 130–137, 2017.
[24] K. Nagai, “Pruning the decimation-in-time fft algorithm with frequency shift,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 34, no. 4, pp. 1008–1010, 1986.
[25] “3gpp ts 38.101-1 v.16.0.0, user equipment (ue) radio transmission and reception; part1: Range 1 standalone,” Jun. 2019, rel. 16.
[26] M. Garrido, “Multiplexer and memory-efficient circuits for parallel bit reversal,” IEEE Trans. Circuits Syst. II, vol. 66, no. 4, pp. 657–661, Apr. 2019.