The generalized discrete fourier transform for the computation of the DFT on large sets of data

In this paper we consider a generalized form of the Discrete Fourier Transform (DFT), called Generalized Discrete Fourier Transform (GFT). Two fast algorithms are given that allow us to obtain a one-dimensional GFT by evaluating a proper multidimensional GFT. It is proved that such two algorithms involve exactly the same arithmetic operations on the same data, and that in the case of the DFT the Algorithm I represents a form of the classical FFT algorithm in mixed radix based on decimation in time. It is shown that the Algorithm II is particularly advantageous for evaluating the DFT on large sets of data.