Fast implementation algorithm of radix-32 million-point FFT
Gang Wang, Zhigang Zhou, Jajiong Wu, Jun He, Haozhe Zhu, Jing Ni, Gang Chen, Jian Zhou · 2025
In order to meet the requirements of high precision and low latency of ultra-large point fast Fourier transforms (FFT) calculation in signal analysis and processing applications, this paper proposes a fast algorithm for the base 32 implementation of millions of point FFT to improve the efficient computing performance of ultra large point FFT under limited memory resource constraints. The algorithm optimizes the selection of the FFT calculation base 32, designs the calculation architecture of the base 32 four stage serial FFT, as well as the core modules such as 32 point basic FFT calculation, data splitting and aggregation, and can expand to support the efficient and universal calculation of K (K refers to 210 in this paper) and M (M refers to 220 in this paper) level point FFT. Through Matlab simulation evaluation, compared with the classical algorithm, the performance calculation error is lower than 10−2. The test results show that the time to complete 2M point FFT when the clock works at 100MHz is 10.49ms, which meets the performance requirements of real-time application.