US 7,024,443 B2 · Method and system for performing a fast-Fourier transform

Abstract

In a method for performing a fast-Fourier transform (FFT), input data samples are written to a storage instance in a data input step, then subjected to a processing step in which the stored input samples are read out of the storage instance and processed in accordance with a transformation algorithm. The resulting output data samples are written back to the storage instance and, in a transformed data output step, read out of the storage instance, successively received batches of the input data samples being fed cyclically to a plurality of such multiple-function storage instances. Each batch is fed to a respective storage instance such that, at any given time during performance of the method, the input, processing and output steps are being performed simultaneously in respect of different batches using different respective storage instances. For each received data input batch, the processing step comprises a plurality of calculation passes creating intermediate data values which are stored between passes in both the respective multiple function storage instance and a further storage instance which is substantially dedicated for use in such processing steps. The invention also includes a related method for performing an inverse fast-Fourier transform (IFFT), as well as FFT and IFFT systems.

Claims24

Dependent claims

A method of performing a fast-Fourier transform (FFT) in which input data samples are written to a storage instance in a data input step, then subjected to a processing step in which the stored input samples are read out of the storage instance and processed in accordance with a transformation algorithm, the resulting output data samples being written back to the storage instance, and, in a transformed data output step, read out of the storage instance, successively received batches of the input data samples being fed cyclically to a plurality of such multiple-function storage instances, each batch to a respective instance, such that, at any given time during performance of the method, the input step, the processing step and the output step are being performed simultaneously in respect of different said batches using different respective said storage instances, wherein, for each received data input batch, the processing step comprises a plurality of calculation passes creating intermediate data values which are stored between passes in both the respective one of the said multiple-function storage instances and a further storage instance substantially dedicated for use in such processing steps.

A method of performing an inverse fast-Fourier transform (IFFT) in which input data samples are written to a storage instance in a data input step, then subjected to a processing step in which the stored input samples are read out of the storage instance and processed in accordance with a transformation algorithm, the resulting output data samples being written back to the storage instance, and, in a transformed data output step, read out of the storage instance, successively received batches of the input data samples being fed cyclically to a plurality of such multiple-function storage instances, each batch to a respective instance, such that, at any given time during performance of the method, the input step, the processing step and the output step are being performed simultaneously in respect of different said batches using different respective said storage instances, wherein, for each received data input batch, the processing step comprises a plurality of calculation passes creating intermediate data values which are stored between passes in both the respective one of the said multiple-function storage instances and a further storage instance substantially dedicated for use in such processing steps.

A fast-Fourier transformation system for transforming input data samples received in batches at a system input into transformed output data samples delivered to a system output in corresponding batches, wherein the system comprises:

a plurality of multiple-function storage instances;
control means for controlling writing of data to and reading of data from the storage instances;
and
a processor core arranged to read stored data samples, to process them in accordance with a transformation algorithm and to store the resulting output data samples;
each received input data batch being subjected to a plurality of calculation passes creating intermediate data values which are stored between the passes;
wherein the control means are arranged such that successively received input data sample batches are fed cyclically in a data input step to the multiple-function storage instance, each batch being fed to a respective one of the said storage instances, such that the data samples processed in the processor core as part of a processing step are read from the same storage instance as that to which they were fed when received from the system input as input data samples in the data input step, the resulting output data samples being written to the same storage instance and, in a data output step, read from the same storage instance to the system output, and such that the input step, the processing step and the output step are performed simultaneously in respect of different said batches using different respective said storage instances,
and wherein the system further comprises a further storage instance, the control means being further arranged such that the said intermediate data values are stored in both the respective multiple-function storage instance in which the corresponding input samples were stored and in the further storage instance, the primary function of the further storage instance being the storage of the intermediate values.

4 more elements

An inverse fast-Fourier transformation system for transforming input data samples received in batches at a system input into transformed output data samples delivered to a system output in corresponding batches, wherein the system comprises:

a plurality of multiple-function storage instances;
control means for controlling writing of data to and reading of data from the storage instances;
and
a processor core arranged to read stored data samples, to process them in accordance with a transformation algorithm and to store the resulting output data samples;
each received input data batch being subjected to a plurality of calculation passes creating intermediate data values which are stored between the passes,
wherein the control means are arranged such that successively received input data sample batches are fed cyclically in a data input step to the multiple-function storage device, each batch being fed to a respective one of the said storage instances, such that the data samples processed in the processor core as part of a processing step are read from the same storage instance as that to which they were fed when received from the system input as input data samples in the data input step, the resulting output data samples being written to the same storage instance and, in a data output step, read from the same storage instance to the system output, and such that the input step, the processing step and the output step are performed simultaneously in respect of different said batches using different respective said storage instances,
and wherein the system further comprises a further storage instance, the control means being further arranged such that the said intermediate data values are stored in both the respective multiple-function storage instance in which the corresponding input samples were stored and in the further storage instance, the primary function of the further storage instance being the storage of the intermediate values.

4 more elements

Dependencies are inferred from the claim text.

Method and system for performing a fast-Fourier transform

Life of this patent

Method and system for performing a fast-Fourier transform

Life of this patent

Abstract

Claims24