Computational Complexity Analysis of FFT Pruning - A Markov Modeling Approach

The Fourier transform is instrumental in many signal processing applications such as digital filtering, spectral analysis and communications. In 1965, Cooley and Tukey demonstrated that the discrete Fourier transform (DFT) can be computed using the fast Fourier transform (FFT) algorithm with reduced computational complexity. When the input vector to the FFT contains mostly zeros (i.e., is sparse), it is possible to realize computational savings over a full FFT by only performing the arithmetic operations on non-zero elements. That is, the FFT is "pruned" so that only the useful computations are performed. In this paper, we derive the (non-stationary) Markov process that describes the number of occupied (i.e. non-zero) paths at each stage of a pruned FFT. With the probability distribution of the number of non-zero paths at each FFT stage, we then determine the probability distribution of the number of multiplications and additions necessary to compute the FFT of an input vector with a given sparsity distribution