Architecturally efficient FFT pruning algorithm

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. © IEE 2005.