Fast Fourier transform device and method for improving a processing speed thereof

摘要

Disclosed is fast Fourier transform device and method for improving a processing speed. The fast Fourier transform device includes a memory part having N memory addresses at which the N data items are written, and having a structure dividing the memory addresses into even-numbered addresses and odd-numbered addresses. An address generation unit generates addresses each including bits except for the most significant bit with respect to the memory addresses. A computation part reads the data items at the even-numbered addresses and odd-numbered addresses based on the addresses generated in the address generation unit, and performing Radix-2 based butterfly computations. The fast Fourier transform device arranges the messed-up memory addresses in order in a new digit-reverse manner. Accordingly, the fast Fourier transform device operates the two butterfly computation structures at the same time so as to reduce the processing time by half as well as to simplify the implementation thereof.