HARDWARE APPARATUS AND METHOD FOR IMPLEMENTING FAST FOURIER TRANSFORM AND INVERSE FAST FOURIER TRANSFORM

摘要

A hardware apparatus and method for implementing fast Fourier transform and inverse fast Fourier transform are provided. The method includes the following steps: A. the point number N (N=2n) of input data currently performing FFT calculation is determined; B. a reverse order reading unit generates a reading address of the reverse order reading process, data-input are read in reverse order and are written into a processing result storing unit from up to down, and only two data-input are read in one time and are written into the RAM storing unit 1 and 2; C. a calculating unit performs N-stage iterative butterfly calculation, and during each process of butterfly calculation of each stage, one datum respectively read from the RAM storing unit 1 and 2 is regarded as data to be processed currently; and the calculating result of each stage is respectively written into specific storing address predetermined in the RAM storing unit 1 and 2, and is regarded as data to be processed of the next stage of calculation. The invention does not have strict requirements of the order of input dataflow, is suitable for application scenes of real-time calculation, saves cost of storing unit, and is highly practical.