Methods and apparatus for fast fourier transforms

Abstract

A system for calculating fast Fourier transforms includes a non-final stage calculating element for repetitively performing in-place butterfly calculations for n−1 stages as well as a final stage calculating element for performing a final stage of butterfly calculations. The final stage calculation includes a first loop and a second loop. The first loop performs a portion of the final stage butterfly calculations and includes control logic to perform groups of butterfly calculations and to store the butterfly calculation outputs in a shuffled order in place of the inputs to result in a correct ordering of transform outputs. The second loop performs a remaining portion of the final stage butterfly calculations and includes control logic to perform butterfly calculations and to store the butterfly calculation outputs in a shuffled order in place of the inputs to result in a correct ordering of transform outputs.

1 - 46 . (canceled)  
   
   
       47 . 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 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 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.  
   
   
   
       48 . The system of  claim 47 , wherein the final stage calculating means performs all butterfly calculations as radix-4 butterflies having four inputs and four outputs.  
   
   
       49 . The system of  claim 48 , wherein N is a power of two.  
   
   
       50 . The system of  claim 49 , wherein the non-final stage calculating means performs a first stage of radix-8 butterfly calculations followed by n−2 stages of radix-4 butterfly calculations.  
   
   
       51 . The system of  claim 48 , wherein the non-final and final stage calculating means include a four-fold SIMD processor for performing four radix-4 butterfly calculations at a time.  
   
   
       52 . A method for performing a fast Fourier transform on N ordered inputs in n stages comprising: 
 performing non-final stage calculations by repetitively performing in-place butterfly calculations for n−1 stages;    performing final stage calculations by performing a final stage of butterfly calculations in a first loop for performing a portion of the final stage butterfly calculations and in a second loop for performing a remaining portion of the final stage butterfly calculations;    wherein each of the butterfly calculations in the first loop and the second loop includes storing butterfly calculation outputs in shuffled order in place of selected inputs to result in a correct ordering of transform outputs.    
   
   
       53 . The method of  claim 52 , wherein the final stage butterfly calculations are all performed as radix-4 butterflies having four inputs and four outputs.  
   
   
       54 . The method of  claim 53 , further comprising storing twiddle factors for application in the butterfly calculations in groups of four, each group having an index and the groups being stored in bit reversed order based on the index.  
   
   
       55 . A method for performing a fast Fourier transform on N ordered inputs in n stages comprising: 
 performing non-final stage calculations by repetitively performing in-place butterfly calculations for n−1 stages;    performing final stage calculations by performing a final stage of butterfly calculations wherein butterfly calculation outputs are stored in shuffled order in place of selected inputs to result in a correct ordering of transform outputs.    
   
   
       56 . The method of  claim 55 , wherein the final stage butterfly calculations are all performed as radix-4 butterflies having four inputs and four outputs.  
   
   
       57 . The method of  claim 56 , further comprising storing twiddle factors for application in the butterfly calculations in groups of four, each group having an index and the groups being stored in bit reversed order based on the index.