Methods and apparatus for fast fourier transforms

In a system for calculating a fast Fourier transform on N ordered input elements having a plurality of calculation stages wherein N is a power of two, a method for performing a final calculation stage comprising:

• performing a first iteration loop, the first iteration loop accepting input elements located using index values that bit-reverse into themselves, performing butterfly calculations on the inputs, and storing output elements in place of the input elements in a shuffled order, the shuffled order resulting in the output elements being ordered in the same manner as the input elements to the fast Fourier transform, the iteration loop iterating through all bit-reversal index values,
• performing a second iteration loop, the second iteration loop accepting input elements located using pairs of index values that bit-reverse into each other, performing a first set of butterfly calculations using input elements located using a first index value of a bit-reversal pair, performing a second set of butterfly calculations using input elements located using a second index value of a bit-reversal pair, storing output elements from the first set of butterfly calculations in place of the input elements to the second set of butterfly calculations in shuffled order and storing output elements from the second set of butterfly calculations in place of the input elements to the first set of butterfly calculations in shuffled order, the order of the storing resulting in the output elements being ordered in the same manner as the input elements to the fast Fourier transform, the iteration loop iterating through all bit-reversal pair index values.

A computer program product for performing a final calculation stage in a system for calculating a fast Fourier transform on N ordered input elements having a plurality of calculation stages wherein N is a power of two, comprising:

• a computer readable medium containing computer readable code for performing a first iteration loop, the first iteration loop accepting input elements located using index values that bit-reverse into themselves, performing butterfly calculations on the inputs, and storing output elements in place of the input elements in a shuffled order, the shuffled order resulting in the output elements being ordered in the same manner as the input elements to the fast Fourier transform, the iteration loop iterating through all bit-reversal index values,
• a computer readable medium containing computer readable code performing a second iteration loop, the second iteration loop accepting input elements located using pairs of index values that bit-reverse into each other, performing a first set of butterfly calculations using input elements located using a first index value of a bit-reversal pair, performing a second set of butterfly calculations using input elements located using a second index value of a bit-reversal pair, storing output elements from the first set of butterfly calculations in place of the input elements to the second set of butterfly calculations in shuffled order and storing output elements from the second set of butterfly calculations in place of the input elements to the first set of butterfly calculations in shuffled order, the order of the storing resulting in the output elements being ordered in the same manner as the input elements to the fast Fourier transform, the iteration loop iterating through all bit-reversal pair index values.

A computer system for system for performing a fast Fourier transform on N ordered inputs in n stages comprising:

• a four-fold SIMD processor;
• a non-final stage calculating means for repetitively performing in-place butterfly calculations for n−1 stages, the butterfly calculations being perform in groups of four simultaneous butterflies on the four-fold SIMD processor;
• a final stage calculating means for performing a final stage of butterfly calculations on the four-fold SIMD processor 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 four simultaneous radix-4 butterfly calculations based on the first loop index values, performing the four simultaneous radix-4 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 four simultaneous radix-4 butterfly calculations based on the two second loop index pair values respectively, performing the two sets of four simultaneous radix-4 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 groups of butterfly calculations in shuffled order in place of the inputs selected for the first one of the two groups of butterfly calculations to result in a correct ordering of transform outputs.

A method for calculating a fast Fourier transform comprising:

• accessing an ordered set of N transform inputs;
• performing one or more non-final stages of butterfly calculations, each of the one or more stages accepting N inputs and transforming them into stage outputs and storing the outputs in place of the outputs in a bit-reversed order;
• performing a final stage of butterfly calculations using the outputs of a previous stage of butterfly calculations as inputs to the final stage of butterfly calculations, the final stage of butterfly calculations including:
• (a) a first loop iterated through a list of first loop index values between 0 and N/16−1 that bit reverse into themselves, the first loop including:
• (i) selecting four groups of four consecutive inputs, the inputs being selected by transforming the first loop index value into four input indices by multiplying the first loop index value by four and successively adding N/4 to result in four input indices, each group of four consecutive inputs being selected beginning with one input index, the four groups of four consecutive inputs being representable as a 4×4 matrix;
• (ii) performing four radix-4 butterfly calculations, one calculation for each group of four inputs;
• and
• (iii) storing the outputs in place of the inputs in shuffled order, the shuffled order resulting from a 4×4 matrix transposition and subsequent swapping of two inner columns;
• and
• (b) a second loop iterated through a list of second loop index pair values, the second loop index pair values being each pair of values between 0 and N/16−1 that bit reverse into each other, the including loop including:
• (i) selecting two sets of four groups of four consecutive inputs, the inputs being selected by transforming each value in the second loop index pair into four input indices by multiplying each second loop index pair value by four and successively adding N/4 to result in two sets of four input indices, each group of four consecutive inputs being selected beginning with one input index, the two sets of four groups of four consecutive inputs being representable as two 4×4 matrices;
• (ii) performing two sets of four radix-4 butterfly calculations, one calculation for each group of four inputs;
• and
• (iii) storing the outputs of each set of four radix-4 butterfly calculations in place of the inputs to the other set of four radix-4 butterfly calculations in shuffled order, the shuffled order resulting from a 4×4 matrix transposition and subsequent swapping of two inner columns;
• wherein following the second loop, outputs from the fast Fourier transform are correctly ordered.