Fast fourier transform using a small capacity memory

摘要

The present invention provides technologies for implementing a high-speed Fast Fourier Transform (FFT) algorithm with a small memory. An information processing apparatus for performing a radix-2 FFT on a data sequence comprises storage means, reading means, a plurality of butterfly operation means, writing means, and control means, wherein each stage of the FFT operation includes a plurality of operation steps, and at every operation step the control means controls each of the means so that: the reading means reads from the storage means sets of data elements referred by storage addresses A, A+1, A+2m, and A+2m+1, the plurality of butterfly operation means perform radix-2 butterfly operation on the data elements in the sets, and the writing means writes the sets of the result data into the storage area referred by the storage addresses A, A+1, A+2m, and A+2m+1.

主权项

1. An information processing apparatus for performing a radix-2 Fast Fourier Transform (FFT) on a data sequence, the information processing apparatus comprising:
a storage element comprising a plurality of storage areas, each of which stores a plurality of data elements to be processed and is assigned a storage address; a reading element configured to read from the storage element a plurality of sets, each of which includes the plurality of data elements stored in a same storage area; a plurality of butterfly operation elements configured to perform butterfly operations with predetermined coefficients respectively on a plurality of data elements, each of said plurality of data elements included in the plurality of sets read from the storage element, to compute a plurality of result data respectively; a writing element configured to write a set including the plurality of result data into the storage element; and a controller configured to control each of the storage, reading, butterfly operation, and writing elements to perform the butterfly operations on all of the data elements stored in the storage element at every stage of the FFT operation; wherein each stage of the FFT operation includes a plurality of operation steps, and at every operation step the controller controls each of the storage, reading, butterfly operation, and writing elements so that:
the reading element reads from the storage element a first set of data elements referenced by a first storage address A, a second set of data elements referenced by a second storage address A+1, a third set of data elements referenced by a third storage address A+2m, and a fourth set of data elements referenced by a fourth storage address A+2m+1;the plurality of butterfly operation elements perform radix-2 butterfly operations on the data elements included in the first set and the data elements included in the third set to compute a first and third set of the result data, and perform radix-2 butterfly operations on the data elements included in the second set and the data elements included in the fourth set to compute a second and fourth set of the result data; andthe writing element writes the first set of the result data into the storage area referenced by the first storage address A, writes one of the second and third sets of the result data into the storage area referenced by the second storage address A+1, writes the other of the second and third set into the storage area referenced by the third storage address A+2m, and writes the fourth set of the result data into the storage area referenced by the fourth storage address A+2m+1;where A comprises zero or a positive integer which is determined for each operation step, and m comprises a positive integer determined for each stage.