FFT algorithm for both input and output pruning

Abstract

When an input data sequence has a large number of zeros and the number of output samples required to be computed is small, significant time saving can be achieved by a judicious combination of the pruning algorithms for decimation-in-time (DIT) and decimation-in-frequency (DIF). It is shown that the complementary structure of the DIT and the DIF formulations makes possible the application of the pruning algorithms simultaneously at the input, as well as at the output, for either of the formulations. For a given number of input and output points, a choice between the two formulations can be made based on the amount of time saved in each. Also, a simple assembly language modification is shown by which the bit reversal is made significantly faster.