Cooley-Tukey Type Discrete Fourier Transform Algorithm For Continuous Function Sampled At Some Composite Point N = pq, p ≠ q

Abstract

By introducing complete base number indices and restricting the number of sampled points to the value N which is highly composite, the paper is focused on the computational complexity of Discrete Fourier Transform (DFT) of a continuous function. We construct a Cooley-Tukey type Fast Fourier Transform FFT algorithm aimed at reducing the number of complex computational operations from N2 complex multiplications to Ny/2 ⁄ and from N(N − 1) complex additions to Ny, where y is an integer to which the selected base number is raised. To justify the effectiveness of our derived FFT algorithm an example is presented for N = 32 sampled points.