Algorithm Research And Design Of Fast Fourier Transform

Fast Fourier Transform (FFT) processors are widely used in different application areas such as communications, radars, imaging, wireless network etc. Enhancing the performance of the FFT is a major concern for researchers. Previously, research has concentrated on speed enhancement, however, with the advent of portable computation, area and specially power consumption have become of special interest. To measure the complexity and efficiency of an FFT algorithm depends on both the available technology and the intended applications. We can see that there is a memory access problem with previously proposed approaches. For instance, unless the processor where the FFT runs provides a large number of registers, repeated access to the memory to load same twiddle factors is unavoidable. It has been recognized that memory access is expensive due to long latency and high power consumption. So memory addressing is a key research concern for enhancing the performance of FFT processors. In this paper, we simply discuss the radix-2 algorithm and the address generation for butterfly operations. We also discuss the architecture of the FFT's memory and an effective memory-addressing scheme. We present a novel FFT algorithm to reduce the frequency of memory access as well as multiplication operations. Our work is to make it possible to improve the performance of FFT processors and reduce the delay of address generation to minimum. We analysis the hardware complexity and the processing time of the proposed scheme and compare it with the other existing schemes. After this, we design the FFT with the two distinct sections: (1) The coefficient memory can be cut to almost a factor of four (N/8). (2) All the butterflies sharing the same coefficient will be clustered and computed together. In this way, redundant memory access to load coefficients is avoided. At last, we use Matlab and C++ to design and emulation this algorithm.