Traced fast fourier transform apparatus and method
AssigneeComsat Corporation
InventorsZhong Hu, Prakash Chakravarthi
Life of this patent
Estimating the term…
Abstract
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 ncludes signal preprocessing in which the indices are adjusted so that the index for a particular stage points to those butterflies of the previous tage which contribute toward its output. The FFT is performed on the indexed data. In one embodiment, a pipelined FFT processor is controlledin a corresponding manner.
Claims6
A method for radix-2 fast fourier transform on a digital series to produce signals in cyclically noncontinuous output bins, comprising the steps of:
- determining the number 2S of FFT points, the output bin index OS, and the input signal array;
- determining the butterfly index for the last stage by
- 17 Ψ S - 1 = O S % ( N 2 ) ( 9 )
- determining the butterfly index for each stage other than said last stage by
- 18 Ψ l - 1 = Ψ l % ( N 2 S - l + 1 ) ( 10 )
- where l varies from 1 to (S−1);
- using said butterfly index, calculating only those butterflies necessary for calculation of the output bins.
Dependencies are inferred from the claim text.