Hardware implementation for fast fourier transform

Abstract

The Fast Fourier Transform is a means of obtaining the Discrete Fourier Transform. But while in the DFT the number of multiplications is in the order of N2, (where N is the number of points) in the FFT the number of multiplications needed is only in the order of N LogN. Nevertheless this number of multiplications has to be done, and when one is concerned about computing the FFT in real time, then these multiplications have to been done in a precise time. If, for example, a signal is sample data 44.1KHz and 1024 points are needed, then 5120 butterflies have to be performed (each containing a complex multiplication, which in reality is four real multiplications and four additions) in 23 milli-sec, or one butterfly in 4.5 micro-sec or one multiplication in less than 1 micro-sec. Since on commercially available computers multiplication is still a slow process, at best it takes about2micro-sec, keeping in mind that a lot of house keeping must be done by the processor itself, then a software procedure is prohibitive for real time computation. Therefore a hardware solution must be sought The aim of this project is to design an algorithm and build the hardware to achieve the real time computation of FFT. [...]