摘要 |
<p>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.</p> |