New Fast Fourier Transform with Linear Multiplicative Complexity

摘要

In this paper, we introduced a new Fast Fourier Transform algorithm with linear multiplicative complexity for real and complex input signals. The proposed algorithm also reduces the total number of operations (arithmetic complexity, or the number of multiplications and additions) compared to the existing methods, such as Duhamel, Heideman, Burrus, Bi et al., Bouguezel et al.