A novel correlation‐based FFT algorithm

Since the discovery of the fast Fourier transform (FFT), many new FFT algorithms have been developed. Conventionally, the convolution‐based approach deals commonly with the prime length discrete Fourier transforms. In this paper, based on some theorems of Number Theory, a new algorithm for computing the FFT (with power of two length) is proposed. This novel recursive algorithm contains three stages, the first and the last stages contain only additions and substractions, and the second stage is of block diagonal form, with each block being a circular correlation/convolution matrix. The newly proposed convolution‐based FFT algorithm has the following advantages: 1. In terms of computational counts, this algorithm can achieve the multiplicative lower bound derived by Winograd.2. The proposed algorithm can easily be implemented in a parallel computing environment.3. The proposed algorithm is recursive in nature, and thus the computation structure is rather regular.