Method and device for fast fourier transform

A circuit for performing Fast Fourier Transform/Inverse Fast Fourier Transform (FFT/IFFT), comprising:

• an address calculating unit, configured to convert a set of reversal-order or a set of natural-order addresses of FFT/IFFT data to a set of addresses in a radix-based numeral representation;
• wherein the address calculating unit is further configured to calculate sequence numbers of a plurality of memory locations for buffering a set of data for a parallel calculation, by accumulating or subtracting each digit of the set of addresses in the radix-based numeral representation and then preforming a modulo operation on the accumulation or subtraction results, wherein the radix represents a length of short DFT sequence for the parallel calculation in a FFT/IFFT calculation;
• an interface unit configured to store the FFT/IFFT data simultaneously and respectively into corresponding memory locations indicated by the calculated sequence numbers;
• and
• a FFT/IFFT calculation unit, configured to perform a FFT/IFFT calculation, comprising
• a short DFT sequence calculator configured to:
• retrieve corresponding data from the memory, directly perform a short DFT sequence calculation for the data, modify the calculated data with a modified twiddle factor, in-place store the modified data back to the memory directly;
• repeat the short DFT sequence calculation, until the whole FFT/IFFT calculation completes.

A non-transitory computer-readable medium comprising instructions executable by at least one processor to perform a method comprising:

• converting a set of reversal-order or set of natural-order addresses of FFT/IFFT data to set of addresses in a radix-based numeral representation;
• calculating sequence numbers of a plurality of memory locations for buffering a set of data for a parallel calculation, by accumulating or subtracting all digits of the set of addresses in the radix-based numeral representation and then performing a modulo on the accumulation or subtraction results, wherein the radix represents a base for a length of short DFT sequence for the parallel calculation in a FFT/IFFT calculation;
• storing the FFT/IFFT data simultaneously and respectively into the corresponding memory locations indicated by the calculated sequence numbers;
• and
• performing FFT/IFFT calculation, comprising
• performing a short DFT sequence calculation, comprising:
• retrieving corresponding data from the memory, inputting directly the corresponding data into a short DFT sequence calculator for calculation, modifying the calculated data with a modified twiddle factor, in-place storing the modified data back to the memory directly;
• repeating the short DFT sequence calculation, until the whole FFT/IFFT calculation completes.