Method and apparatus for performing fast fourier transforms

• US 6,230,177 B1
• Filed: 06/12/1998
• Issued: 05/08/2001
• Est. Priority Date: 06/12/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Gossett, Carroll Philip, Winget, Nancy Cam, Lu, Chien-Ping
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/096,538
• Time in Patent Office: 1,061 Days
• Field of Search: 708/403-409, 708/290
• US Class Current: 708/404
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

The method and apparatus employ a texture filter in a graphics processor to perform a transform such as, for example, a Fast Fourier Transform. The texturizer can include an array of linear interpolators. The architecture reduces the computational complexity of the transform processes.

Claims

1. A method for generating a fast fourier transform (FFT) comprising the steps of:

receiving signal data;

storing the received data in a memory;

texturizing the data with parameters selected to generate the FFT transform; and

storing the texturized data.

2. The method of claim 1, wherein said step of texturizing comprises the substeps of:

reading the received data from the memory;

passing the data to at least one array of linear interpolators; and

performing multiply and accumulate operations on the data in said at least one array.

3. The method of claim 2 comprising the further step of transposing the data read prior to passing the data to the at least one array.

4. The method of claim 3 wherein said step of transposing comprises the step of adjusting data locality in accordance with an addressing scheme associated with said at least one array.

5. A method for generating a fast fourier transform (FFT), comprising the steps of:

receiving signal data;

storing the received data;

texturizing the data using parameters selected to perform multiply and accumulate operations that support generating the fast fourier transform using the received signal data as input data.

6. The method of claim 5, wherein said step of texturizing comprises the substeps of matching the input data to a predefined texturizing addressing scheme;

and

operating on input data with at least one array of linear interpolators.

7. The method of claim 6 comprising the further step of transposing the data read prior to passing the data to the at least one array of linear interpolators.

8. The method of claim 7 wherein said step of transposing comprises the step of adjusting data locality in accordance with an addressing scheme associated with said at least one array.

9. A method for generating an N point fast fourier transform, (FFT), where N is an integer divisible by 2, the method comprising the steps of:

a) receiving input data;

b) generating a first plurality of radix-4 FFT'"'"'s using a texture subsystem;

c) storing the results of the step of generating;

d) generating a second plurality of radix-4 FFT'"'"'s using the texture subsystem; and

e) storing said results of the step of generating said second plurality of radix-4 FFTs.

10. The method of claim 9 wherein said first plurality of radix-4 FFTs correspond to a group of N/4 radix 4 FFTs.

11. The method of claim 10 wherein steps b) and d) constitute separate passes of an FFT process and the total number of passes, P equals log₄N.

12. The method of claim 9, wherein said step of generating a first plurality of radix-4 FFTs comprises the substeps of:

storing the received input data in a texture memory;

passing the received input data to at least one texture filter; and

performing multiply and accumulate operations on the data in said at least one texture filter.

13. The method of claim 12 wherein said step of passing passes the received input data to four texture filters.

14. A system for generating a fast fourier transform (FFT) comprising:

a texture memory; and

a texture filter coupled to said texture memory including at least one array of linear interpolators having parameters set to support calculations necessary to generate the fast fourier transform.

15. The system of claim 14 further comprising a data transposer coupled to said texture memory.

16. A system for generating a fast fourier transform from input data comprising:

a texture memory; and

a plurality of texture filters, coupled to said texture memory, each texture filter including an array of linear interpolators that receive input data from said texture memory;

wherein each array of linear interpolators includes operation parameters set to perform calculations to support calculations necessary to generate the fast fourier transform.

17. The system of claim 16 further comprising a data transposer coupled to said, texture memory.

18. A method for generating fast fourier transforms, (FFT) the method comprising the steps of:

transposing data into an arrangement corresponding to a Level of Detail for a texturizing subsystem;

texturizing the transposed data using parameters, selected for generating a fast fourier transform; and

storing the texturized data.

19. The method of claim 18 further comprising submitting the stored texturized data to a second stage of texturizing.

20. The method of claim 18 wherein for generating an N-point FFT where N is an integer divisible by 2^x where x is an integer greater than or equal to 1, after texturizing the transposed data to calculate a radix 2⁴ FFT where y is an integer greater than or equal to 1, submitting data to at least z additional passes of texturizing where z=(log_2^y N)−

1.