The quick discrete Fourier transform

Abstract

This paper will look at an approach that uses symmetric properties of the basis function to remove redundancies in the calculation of discrete Fourier transform (DFT). We will develop an algorithm, called the quick Fourier transform (QFT), that will reduce the number of floating point operations necessary to compute the DFT by a factor of two or four over direct methods or Goertzel's method for prime lengths. Further by applying the idea to the calculation of a DFT of length-2/sup M/, we construct a new O(N log N) algorithm. The algorithm can be easily modified to compute the DFT with only a subset of input points, and it will significantly reduce the number of operations when the data are real. The simple structure of the algorithm and the fact that it is well suited for DFTs on real data should lead to efficient implementations and to a wide range of applications.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>