General FFT pruning algorithm

Abstract

The efficiency of the fast Fourier transform may be increased by removing operations on input values which are zero, and on output values which are not required; this procedure is known as FFT pruning algorithm. Up to now some algorithms have been proposed considering decimation-in-time (DIT) or decimation-in-frequency (DIF) procedures, and considering that for a N = 2/sup M/ input points of the FFT only quantities equals to 2/sup k/ (to an integer k), of nonzero input or desired output points are required. In this paper we propose a new FFT pruning algorithm where the number of nonzero inputs or desired outputs can be arbitrary. The idea of the proposed algorithm works well with DIT as well as DIEF procedures, and the implementation is similar to the FFT algorithms that use in-place computation, with a small alteration.