Method and system for performing a fast-fourier transform

• US 20040034677A1
• Filed: 11/08/2002
• Published: 02/19/2004
• Est. Priority Date: 08/15/2002
• Status: Active Grant

• Current Assignee: Rim Semiconductor Co.
• Original Assignee: Zarlink Semiconductor Limited (Microchip Technology Incorporated)
• Inventors: Forrest, Kevin W., Abouseido, Maamoun, Davey, Stephen W.
• Granted Patent: US 7,024,443 B2
• Time in Patent Office: Days
• US Class Current: 708/404
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

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.

Claims

1. 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.

2. A method according to claim 1, in which, of the data making up the intermediate data values stored between calculation passes of the processing step, as least as much data is stored in the dedicated storage instance as in the multiple-function storage instance.

3. A method according to claim 1, wherein the intermediate data values contain real values and imaginary values, the real values being stored in the respective multiple-function storage instance and the imaginary values in the dedicated storage instance.

4. A method according to claim 3, wherein the processing step has a final calculation pass producing first and second sets of output data samples derived from the respective input data batch, the samples of the second set being the complex conjugates of the samples of the first set, and wherein the real and imaginary parts of the first set only are stored in the respective multiple-function storage instance.

5. A method according to claim 4, wherein DC and Nyquist points resulting from the final calculation pass are stored as a pair in the respective multiple-function storage instance.

6. A method according to claim 4, in which the transformed data output step includes address decoding to cause the data to be read out in a different order from that in which it was stored at the end of the processing step.

7. 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.

8. A method according to claim 7, in which of the data making up the intermediate data values stored between calculation passes of the processing step, as least as much data is stored in the dedicated storage instance as in the multiple-function storage instance.

9. A method according to claim 7, wherein the intermediate data values contain real values and imaginary values, the real values being stored in the respective multiple-function storage instance and the imaginary values in the dedicated storage instance.

10. A method according to claim 9, wherein the processing step has an initial calculation pass including the generation of the complex conjugates of samples stored in the respective multiple-function storage instance in the data input step.

11. A method according to claim 10, wherein the data input step includes storing DC and Nyquist points as a pair in the respective multiple-function storage instance.

12. A method according to claim 10, in which the data input step includes writing the input data samples to the respective multiple-function storage instance with bit-reversed addressing.

13. 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.

14. A system according to claim 13, wherein the storage capacity of the further storage instance is at least as large as that of each of the multiple-function storage instances.

15. A system according to claim 13, wherein the control means are arranged such that, of the intermediate data values, the real values are stored in the respective multiple-function storage instance and the imaginary values are stored in the said further storage instance.

16. A system according to claim 13, wherein the processor core and the control means are arranged such that the said plurality of calculation passes include a final calculation pass producing first and second sets of output data samples derived from the respective input data batch, the samples of the second set being the complex conjugates of the samples of the first set, and the real and imaginary parts of the first set only are stored in the respective multiple-function storage instance.

17. A system according to claim 16, wherein the processor core and the control means are arranged such that DC and Nyquist points resulting from the final calculation pass are stored as a pair in the respective multiple-function storage instance.

18. A system according to claim 16, including address decoding means for causing the output data samples to be read out from the respective multiple-function storage instance in a different order from that in which it was stored after processing by the processor core.

19. 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.

20. A system according to claim 19, wherein the storage capacity of the further storage instance is at least as large as that of each of the multiple-function storage instances.

21. A system according to claim 19, wherein the control means are arranged such that, of the intermediate data values, the real values are stored in the respective multiple-function storage instance and the imaginary values are stored in the said further storage instance.

22. A system according to claim 21, wherein the control means are arranged such that the said plurality of calculation passes have an initial calculation pass including the generation of the complex conjugates of samples stored in the respective multiple-function storage instance in the data input step.

23. A system according to claim 22, wherein the control means are arranged such that the data input step includes storing DC and Nyquist points as a pair in the respective multiple-function storage instance.

24. A system according to claim 23, further comprising bit-reversal means coupled to the system input for causing the input data samples to be written to the respective multiple-function storage instance with bit-reversed addressing.