FFT pruning

Abstract

There are basically four modifications of the N=2^Mpoint FFT algorithm developed by Cooley and Tukey which give improved computational efficiency. One of these, FFT pruning, is quite useful for applications such as interpolation (in both the time and frequency domain), and least-squares approximation with trignometric polynomials. It is shown that for situations in which the relative number of zero-valued samples is quite large, significant time-saving can be obtained by pruning the FFT algorithm. The programming modifications are developed and shown to be nearly trivial. Several applications of the method for speech analysis are presented along with Fortran programs of the basic and pruned FFT algorithm. The technique described can also be applied effectively for evaluating a narrow region of the frequency domain by pruning a decimation-in-time algorithm.