Architecturally efficient FFT pruning algorithm
S. Singh, Swaminathan Srinivasan · Electronics Letters · 2005
Several fast Fourier transform (FFT) pruning algorithms have been proposed for applications where the entire spectrum of frequencies is not of relevance and even the inputs are sparse. However, these are architecturally inefficient because of the complexity of the overhead operations involved. Developed is a new generic pruning algorithm that uses only single bit combinational operations for delineating paths in the signal flow graph, as against butterflies, which are relevant for computation of the desired frequency coefficients. The entire delineation process has been divided into stages making the proposed algorithm also amenable for pipelined hardware implementation.