METHOD AND APPARATUS FOR REDUCED MEMORY FOOTPRINT FAST FOURIER TRANSFORMS

摘要

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.

主权项

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.