EFFICIENT COMPUTATION OF THE DFT WITH ONLY A SUBSET OF INPUT OR OUTPUT POINTS

The standard FFT algorithms inherently assume that the length of the input and output sequences are equal. In practice this is not always an accurate assumption, and this paper discusses ways of efficiently computing the DFT, when the number of input and output data points differ. The two problems, whether the length of the input or output sequence is reduced, can be found to be ''duals'' of each other, and the same methods can, to a large extent, be used to solve both. The algorithms utilize the redundancy in the input or output to reduce the number of operations below those of the FFT algorithms. This paper briefly discusses the well-known pruning method and introduces a new efficient algorithm called transform decomposition. This new algorithm is based on a mixture of a standard FFT algorithm and Horner's polynomial evaluation scheme equivalent to the one in Goertzel's algorithm. It is shown to require fewer operations than pruning and also to be more flexible than pruning. The algorithm works for both power of two and prime-factor algorithms, as well as for real input data.