Computational Complexity Analysis of FFT Pruning - A Markov Modeling Approach
Citations Over TimeTop 25% of 2006 papers
Abstract
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
Related Papers
- → Five-step FFT algorithm with reduced computational complexity(2006)9 cited
- → A Grouped Fast Fourier Transform Algorithm Design For Selective Transformed Outputs(2006)4 cited
- → A COOLEY-TUKEY MODIFIED ALGORITHM IN FAST FOURIER TRANSFORM(2011)1 cited
- → A family of MD FFT algorithms of complexity intermediate between the MD Cooley-Tukey FFT and the MD prime-factor FFT(2002)
- A Kind of Improved Real-Valued Fast Fourier Transform(FFT) and implementation on DSP(2012)