Patent ID: 6609140
Filing Date: 2003-08-19
Classification: G06F

Abstract:
A system for performing a fast Fourier transform on N ordered inputs in n stages comprising:a non-final stage calculating means for repetitively performing in-place butterfly calculations for nâˆ’1 stages; a final stage calculating means for performing a final stage of butterfly calculations including: a first loop means for performing a portion of the final stage butterfly calculations, the first loop means iterating on a table of first loop index values consisting of values that bit-reverse into themselves, the first loop means including control logic to select inputs for a set of butterfly calculations based on the first loop index values, performing the set of butterfly calculations, and storing butterfly calculation outputs in shuffled order in place of the selected inputs to result in a correct ordering of transform outputs; and a second loop means for performing a remaining portion of the final stage butterfly calculations, the second loop means iterating on a table of second loop index value pairs consisting of two values that bit-reverse into each other, the second loop means including control logic to select inputs for two sets of butterfly calculations based on the two second loop index pair values respectively, performing two sets of butterfly calculations, and storing butterfly calculation outputs from a first one of the two sets of butterfly calculations in shuffled order in place of the inputs selected for a second one of the two sets of butterfly calculations and storing butterfly calculation outputs from the second one of the two sets of butterfly calculations in shuffled order in place of the inputs selected for the first one of the two sets of butterfly calculations to result in a correct ordering of transform outputs.