Real-time method and apparatus for performing a large size fast fourier transform

A method of performing a k-stage FFT computation of N data points wherein k and N are integers, the method comprising:

• for each one of a plurality of stage groupings of at least one stage of k stages of the k-stage FFT computation wherein the plurality of stage groupings of at least one stage collectively comprise the k stages, performing a respective plurality of operations on the N data points, each one of the respective plurality of operations comprising:
• performing an import of a respective plurality of sets of data points of the N data points from an external memory into an internal memory;
• performing a FFT computation upon each one of the respective plurality of sets of data points of the N data points in the internal memory;
• and
• performing an export of the respective plurality of sets of data points of the N data points from the internal memory into the external memory to update the respective plurality of sets of data points of the N data points in the external memory.

A processor comprising:

• an internal memory adapted to store data;
• a DMA (direct memory access) unit adapted to import data into the internal memory and to export data from the internal memory;
• and
• a central processor unit (CPU) adapted to perform, for each one of a plurality of stage groupings of at least one stage of k stages of the k-stage FFT computation wherein the plurality of stage groupings of at least one stage collectively comprise the k stages, a respective plurality of operations on the N data points, for each one of the respective plurality of operations the CPU is adapted to:
• provide instructions to the DMA unit for performing an import of a respective plurality of sets of data points, of N data points, into the internal memory;
• perform a FFT computation upon each one of the respective plurality of sets of data points, of the N data points, in the internal memory;
• and
• provide instructions to the DMA unit for performing an export of the respective plurality of sets of data points, of the N data points, from the internal memory to update the respective plurality of sets of data points of the N data points.

An article of manufacture comprising:

• a computer usable medium having computer readable program code means embodied therein for performing a k-stage FFT computation of N data points wherein k and N are integers, the computer readable code means in said article of manufacture comprising:
• computer readable code FFT means for performing, for each one of a plurality of stage groupings of at least one stage of k stages of the k-stage FFT computation wherein the plurality of stage groupings of at least one stage collectively comprise the k stages, a respective plurality of operations on the N data points, for each one of the respective plurality of operations the computer readable code FFT means comprising:
• computer readable code means for providing instructions for performing an import of a respective plurality of sets of data points of the N data points from an external memory into an internal memory;
• computer readable code means for performing a FFT computation upon each one of the respective plurality of sets of data points of the N data points in the internal memory;
• and
• computer readable code means for providing instructions for performing an export of the respective plurality of sets of data points of the N data points from the internal memory into the external memory to update the respective plurality of sets of data points of the N data points in the external memory.