Pruning the decimation in-time FFT algorithm
D. R. Skinner · IEEE Transactions on Acoustics Speech and Signal Processing · 1976
Significant time-saving can be achieved by a simple modification to the radix-2 decimation in-time fast Fourier transform (FFT) algorithm when the data sequence to be transformed contains a large number of zero-valued samples. The time-saving is accomplished by replacing M - L stages of the FFT computation with a simple recopying procedure where 2Mis the total number of points to be transformed of which only 2Lare nonzero.