US Patent 7246143 Traced fast fourier transform apparatus and method

A Fast Fourier Transform (FFT) arrangement for use in those situations in which not all of the outputs are desired is controlled in such a fashion that at least those multiplications (and possibly those additions) are not performed which do not contribute toward the desired outputs. The technique is usable in those situations in which the desired output signals are noncontiguous, or are in noncontiguous bins. The technique includes signal preprocessing in which the indices are adjusted so that the index for a particular stage points to those butterflies of the previous stage which contribute toward its output. The FFT is performed on the indexed data. In one embodiment, a pipelined FFT processor is controlled in a corresponding manner.