Affiliations: [a]
College of Electrical and Information Engineering, Hunan University of Technology, Zhouzhou, China
| [b]
College of Information Science and Engineering, Hunan University, Changsha, China
| [c]
Department of Computer Science, State University of New York, New Paltz, New York, USA
| [d]
School of Computer and Information Engineering, Hunan University of Commerce, Changsha, China
Correspondence:
[*]
Corresponding author. Weijin Jiang, School of Computer and information engineering, Hunan University of
Commerce, Changsha 410205, China. E-mail: xsph_519@163.com.
Abstract: Discrete Fourier transform (DFT) finds various applications in signal processing, image processing, artificial intelligent, and fuzzy logic etc. DFT is often computed efficiently with Fast Fourier transform (FFT). The modified split radix FFT (MSRFFT) algorithm implements a length-N=2m DFT achieving a reduction of arithmetic complexity compared to split-radix FFT (SRFFT). In this paper, a simplified algorithm is proposed for the MSRFFT algorithm, reducing the number of real coefficients evaluated from 5/8N - 2 to 15/32N - 2 and the number of groups of decomposition from 4 to 3. A implementation approach is also presented. The approach makes data-path of the MSRFFT regular similar to that of the radix-2 FFT algorithm. The experimental results show that (1) MSRFFT consumes less time on central processing units (CPUs) with sufficient cache than existing algorithms; (2) the proposed implementation method can save execution time on CPUs and general processing units (GPUs).
Keywords: Fast Fourier transform (FFT), general processing unit (GPU) parallelism, modified split-radix (MSR), split-radix (SR)
