Address generators integrated with parallel FFT for mapping arrays in bit reversed order

Abstract

Reducing the amount of required memory and instruction cycles when implementing Fast Fourier Transforms (FFTs) on a computer system is described. The invention optimizes FFT software using in-place bit reversal (IPBR) implemented on a processor capable of bit reversed incrementation. Enables the design of address generators that combine IPBR and one FFT stage in parallel. Increases efficiency by removing instructions to store output from a stand-alone IPBR mapping and then fetch the same data as input for the FFT stage.

1 . A method for reordering the elements of a 2{circumflex over ( )}(log2N) length input array in bit reversed order to generate address pairs using a Fast Fourier Transform in a computer system processor, comprising: 
 generating a sequence of address pairs in said processor from said input array by processing said array; and    calculating a Fast Fourier Transform (FFT) using said sequence of generated address pairs and self-reversed addresses of said address pairs as input to said Fast Fourier Transform.    
   
   
       2 . The method of  claim 1 , wherein said generating a sequence of address pairs further comprises excluding one of said address pairs and bit reversed compliments to said address pairs in a previous generation process from a subsequent generation process.  
   
   
       3 . The method of  claim 1 , wherein said generating comprises generating a four element set of values of said generated address pairs after each said generation step.  
   
   
       4 . The method of  claim 1 , wherein said generating comprises generating an eight element set of values of said generated address pairs after each said generation step.  
   
   
       5 . The method of  claim 1 , wherein said generating further comprises plotting said generation of said sequence on a graph, a first axis of said graph is scaled to measure most significant bits in said array and a second axis of said graph is scaled to measure least significant bits in said array.  
   
   
       6 . The method of  claim 5 , wherein said generation comprises iterating through an organized path of said plotted address pairs.  
   
   
       7 . A method for reordering the elements of a 2{circumflex over ( )}(log2N) length input array in bit reversed order to generate address pairs using a Fast Fourier Transform in a computer system processor, comprising: 
 providing a plot of addresses pairs of said array, wherein each address pair has a first address and a second address and the second address in each address pair is a bit reversed compliment of the first address,    wherein a first axis of said plot represents a scale of most significant bits and a second axis of said plot represents a scale of least significant bits for each address of said address pair values;    defining a path in said plot for processing a plurality of said plotted address pairs;    generating a set of output address pairs and self reversed addresses by processing through said path; and    calculating a Fast Fourier Transform (FFT) using said set of output address pairs and self-reversed addresses of said address pairs as an input to said FFT.    
   
   
       8 . The method of  claim 7 , wherein said generating said set of output address pairs further comprises excluding a set of address pairs and bit reversed compliments to said excluded address pairs of a previous processing from a subsequent processing.  
   
   
       9 . The method of  claim 7 , wherein said generating comprises generating a four to eight element set of address pair values and bit reversed compliments to said address pair values.  
   
   
       10 . The method of  claim 7 , wherein said processing comprises processing through and organized said path of said plot.  
   
   
       11 . The method of  claim 7 , wherein said generating comprises performing a discrete set of processing steps to advance each of said address pairs such that each address pair remains mutually bit reversed after each said move.  
   
   
       12 . The method of  claim 7 , wherein said generating comprises generating a sequence of address pairs from said input array to produce a set of address pairs that are not self-reversible.  
   
   
       13 . The method of  claim 7 , wherein said providing a plot comprises, for said array that is an odd log2N array, providing said first axis with Q+1 least significant bits and said second axis with the bit reversed Q most significant bits.  
   
   
       14 . The method of  claim 7 , wherein said providing a plot comprises, for said array that is an even log2N array, providing said first axis with Q least significant bits and said second axis with the bit reversed Q most significant bits.  
   
   
       15 . The method of  claim 7 , wherein said providing a plot comprises, for said array that is an odd log2N array, providing said first axis with bit reversed Q+1 least significant bits and said second axis with the bit reversed Q most significant bits.  
   
   
       16 . The method of  claim 7 , wherein said providing a plot comprises, for said array that is an even log2N array, providing said first axis with bit reversed Q least significant bits and said second axis with Q most significant bits.