Method and apparatus for reduced memory footprint fast fourier transforms

Patent metadata

Field	Value
Publication number	US-9317480-B2
Application number	US-201213994828-A
Country	US
Kind code	B2
Filing date	Mar 12, 2012
Priority date	Mar 12, 2012
Publication date	Apr 19, 2016
Grant date	Apr 19, 2016

Abstract

Generally, this disclosure describes a method and apparatus for reduced memory footprint fast Fourier transforms (FFTs). An apparatus may include intermediate factor circuitry configured to generate an intermediate factors vector including a number of intermediate factors in response to a request to generate an FFT of an N-point input data set, N composite, wherein N is equal to a product of a number of nonunity integer factors, the number of intermediate factors is related to the nonunity integer factors of N and the number of intermediate factors is less than N. The apparatus may include intermediate result circuitry configured to reconstruct a subset of twiddle factors based at least in part on an element by element product of a first subset of the intermediate factors vector and a complex conjugate of a second subset of the intermediate factors vector, wherein the twiddle factors are complex roots of unity.

First claim

What is claimed is:

1. An apparatus comprising:
intermediate factor circuitry configured to generate an intermediate factors vector comprising a number of intermediate factors in response to a request to FFT circuitry to generate a fast Fourier transform (FFT) of an N-point input data set, N composite, wherein N is equal to a product of a number of nonunity integer factors, the number of intermediate factors is related to the nonunity integer factors of N and the number of intermediate factors is less than N;
memory circuitry configured to store the intermediate factors vector in contiguous memory locations; and
intermediate result circuitry configured to reconstruct a subset of twiddle factors based at least in part on an element by element product of a first subset of the intermediate factors vector and a complex conjugate of a second subset of the intermediate factors vector, each of the first subset and the second subset loaded from contiguous memory locations in the memory circuitry, wherein the twiddle factors are complex roots of unity configured to be used in generating the FFT.

2. The apparatus of claim 1 , wherein
the number of intermediate factors stored in the intermediate factors vector is related to a sum of at least a portion of the nonunity integer factors of N.

3. The apparatus of claim 1 , wherein
the first subset of the intermediate factors vector and the second subset of the intermediate factors vector correspond to a size of a register associated with intermediate results circuitry.

4. The apparatus of claim 1 , wherein
each intermediate factor of the first subset of the intermediate factors vector corresponds to a complex exponential raised to a square of a sum of a first index associated with a first nonunity integer factor of N and a second index associated with a second nonunity integer factor of N and
each intermediate factor of the second subset of the intermediate factors vector corresponds to the complex exponential raised to a square of a difference of the first index associated with the first nonunity integer factor of N and the second index associated with the second nonunity integer factor of N.

5. The apparatus of claim 4 , wherein
the number of intermediate factors corresponds to a sum of the first nonunity integer factor of N and twice the second nonunity integer factor of N minus two.

6. The apparatus of claim 1 , further comprising:
FFT circuitry configured to generate an intermediate input data array wherein a number of dimensions of the intermediate input data array is related to the number of nonunity integer factors of N, the memory circuitry configured to store the intermediate input data array.

7. The apparatus of claim 6 , wherein
the intermediate result circuitry is further configured to generate an intermediate output array based on the intermediate factors and the intermediate input data array, and
the memory circuitry is further configured to store the intermediate output array.

8. The apparatus of claim 7 , wherein the FFT circuitry is further configured to generate an output data set corresponding to the FFT of the input data set based at least in part on the intermediate output array.

9. The apparatus of claim 6 , wherein
the intermediate result circuitry is further configured to multiply a subset of the intermediate input data array by the first subset of the intermediate factors vector and complex conjugates of the second subset of the intermediate factors vector, element by element, to generate a subset of an intermediate output array and the memory circuitry is configured to store the subset of the intermediate output array.

10. A method comprising:
generating an intermediate factors vector comprising a number of intermediate factors in response to a request to FFT circuitry to generate a fast Fourier transform (FFT) of an N-point input data set, N composite, wherein N is equal to a product of a number of nonunity integer factors, the number of intermediate factors is related to the nonunity integer factors of N and the number of intermediate factors is less than N;
storing the intermediate factors vector in contiguous memory locations in memory circuitry; and
reconstructing a subset of twiddle factors based at least in part on an element by element product of a first subset of the intermediate factors vector and a complex conjugate of a second subset of the intermediate factors vector, each of the first subset and the second subset loaded from the contiguous memory locations in the memory circuitry, wherein the twiddle factors are complex roots of unity configured to be used in generating the FFT.

11. The method of claim 10 , wherein
the number of intermediate factors in the intermediate factors vector is related to a sum of at least a portion of the nonunity integer factors of N.

12. The method of claim 10 , wherein
the first subset of the intermediate factors vector and the second subset of the intermediate factors vector correspond to a size of a register associated with intermediate results circuitry.

13. The method of claim 10 , wherein
each intermediate factor of the first subset of the intermediate factors vector corresponds to a complex exponential raised to a square of a sum of a first index associated with a first nonunity integer factor of N and a second index associated with a second nonunity integer factor of N and
each intermediate factor of the second subset of the intermediate factors vector corresponds to the complex exponential raised to a square of a difference of the first index associated with the first nonunity integer factor of N and the second index associated with the second nonunity integer factor of N.

14. The method of claim 13 , wherein
the number of intermediate factors corresponds to a sum of the first nonunity integer factor of N and twice the second nonunity integer factor of N minus two.

15. The method of claim 10 , further comprising:
generating an intermediate input data array wherein a number of dimensions of the intermediate input data array is related to the number of nonunity integer factors of N; and
storing the intermediate input data array in the memory circuitry.

16. The method of claim 15 , further comprising:
generating an intermediate output array based on the intermediate factors and the intermediate input data array, and
storing the intermediate output array in contiguous memory locations.

17. The method of claim 16 , further comprising:
generating an output data set corresponding to the FFT of the input data set based at least in part on the intermediate output array.

18. The method of claim 15 , further comprising:
multiplying a subset of the intermediate input data array by the first subset of the intermediate factors vector and complex conjugates of the second subset of the intermediate factors vector, element by element, to generate a subset of an intermediate output array and storing the subset of the intermediate output array in contiguous memory locations.

19. A system comprising one or more storage mediums having stored thereon, individually or in combination, instructions that when executed by one or more processors result in the following operations comprising:
generating an intermediate factors vector comprising a number of intermediate factors in response to a request to FFT circuitry to generate a fast Fourier transform (FFT) of an N-point input data set, N composite, wherein N is equal to a product of a number of nonunity integer factors, the number of intermediate factors is re

Assignees

• Baksheev Dmitry D
• Petrov Evgueni S
• Petrov Vladimir S
• Intel Corp

Inventors

• Baksheev Dmitry D
• Petrov Evgueni S
• Petrov Vladimir S

Classifications

• G06F17/142 Primary

  Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm · CPC title