Fast fourier transform (FFT) butterfly calculations in two cycles

Abstract

A digital signal processor (DSP) including two multipliers and two three-input arithmetic logic units is able to perform a sequence of Fast Fourier Transform butterfly calculations such that results of a butterfly calculation in said sequence are available two cycles after results of an immediately previous butterfly calculation in said sequence are available.

What is claimed is:  
     
         1 . A method comprising: 
 performing a sequence of Fast Fourier Transform butterfly calculations such that results of a butterfly calculation in said sequence are available two cycles after results of an immediately previous butterfly calculation in said sequence are available.    
     
     
         2 . A method to calculate four results of a Fast Fourier Transform butterfly calculation in two cycles, the calculation involving real and imaginary cosinusoidal data inputs, real and imaginary sinusoidal data inputs, and real and imaginary coefficients, the method comprising: 
 in a first cycle: 
 adding a first value to a first product of a real sinusoidal data input and a real coefficient and subtracting therefrom a second product of an imaginary sinusoidal data input and an imaginary coefficient to produce a first result; and  
 adding said first value to said second product and subtracting therefrom said first product to produce a second result; and  
   in a second cycle: 
 adding a second value to a third product of said real sinusoidal data input and said imaginary coefficient and to a fourth product of said imaginary sinusoidal data input and said real coefficient to produce a third result; and  
 subtracting from said second value said third product and said fourth product to produce a fourth result.  
   
     
     
         3 . The method of  claim 2 , wherein said first value is a real cosinusoidal data input and said second value is an imaginary cosinusoidal data input.  
     
     
         4 . The method of  claim 2 , the method further comprising: 
 in said first cycle: 
 concatenating a rounding constant to a real cosinusoidal data input to produce said first value; and  
   in said second cycle: 
 concatenating said rounding constant to an imaginary cosinusoidal data input to produce said second value.  
   
     
     
         5 . The method of  claim 2 , the method further comprising: 
 in said first cycle: 
 multiplying said real sinusoidal data input and said imaginary coefficient to produce said third product; and  
 multiplying said imaginary sinusoidal data input and said real coefficient to produce said fourth product.  
   
     
     
         6 . The method of  claim 2 , the method further comprising: 
 in said second cycle: 
 multiplying a real sinusoidal data input of a next butterfly calculation and a real coefficient of said next butterfly calculation to produce a first product for said next butterfly calculation; and  
 multiplying an imaginary sinusoidal data input of said next butterfly calculation and an imaginary coefficient of said next butterfly calculation to produce a second product for said next butterfly calculation.  
   
     
     
         7 . The method of  claim 2 , the method further comprising: 
 writing to memory said first result, said second result, said third result and said fourth result within two cycles.    
     
     
         8 . The method of  claim 2 , the method further comprising: 
 writing said first result and said third result to memory in a particular cycle and said second result and said fourth result to memory in a next cycle.    
     
     
         9 . A digital signal processor comprising: 
 a first multiplier and a second multiplier, where in a first cycle said first multiplier is to multiply a real sinusoidal data input of a Fast Fourier Transform butterfly calculation and an imaginary coefficient of said butterfly calculation and said second multiplier is to multiply an imaginary sinusoidal data input of said butterfly calculation and a real coefficient of said butterfly calculation, and where in a second cycle said first multiplier is to multiply a real sinusoidal data input of a next butterfly calculation and a real coefficient of said next butterfly calculation and said second multiplier is to multiply an imaginary sinusoidal data input of said next butterfly calculation and an imaginary coefficient of said next butterfly calculation;    a first three-input arithmetic logic unit, where in a first cycle said first arithmetic logic unit is to subtract an output of said second multiplier from an output of said first multiplier and to add thereto a first value to produce a first result, and where in a second cycle said first arithmetic logic unit is to add the output of said first multiplier and the output of said second multiplier to a second value to produce a second result; and    a second three-input arithmetic logic unit, where in a first cycle said second arithmetic logic unit is to subtract an output of said first multiplier from an output of said second multiplier and to add thereto said first value to produce a third result, and where in a second cycle said second arithmetic logic unit is to subtract the output of said first multiplier and the output of said second multiplier from said second value to produce a fourth result.    
     
     
         10 . The digital signal processor of  claim 9 , wherein said first value is a real cosinusoidal data input of said butterfly calculation and said second value is an imaginary cosinusoidal data input of said butterfly calculation.  
     
     
         11 . The digital signal processor of  claim 9 , wherein said first value is a concatenation of a rounding constant to a real cosinusoidal data input of said butterfly calculation and said second value is a concatenation of said rounding constant to an imaginary cosinusoidal data input of said butterfly calculation.  
     
     
         12 . The digital signal processor of  claim 9 , further comprising: 
 means for writing to memory said first result, said second result, said third result and said fourth result within two cycles.    
     
     
         13 . The digital signal processor of  claim 12 , wherein said means for writing includes at least: 
 means for writing said first result and said third result to memory in a particular cycle; and    means for writing said second result and said fourth result to memory in a next cycle.