Understanding Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT). Simulation and Digital Implementation by means of blocks, not C-code

The DFT and FFT are used mainly to obtain the amplitude of a harmonic component from a periodic signal containing several harmonics. For instance, it is desired to know the 180 Hz harmonic amplitude from a signal. Then, the DFT and FFT are the best choices to do that.

This report presents how to implement DFT and FFT by means of simplified blocks, which are sine, cosine, sum, square, etc. It is easy to find on the internet the DFT and FFT performed in C-code. Actually, the DFT and FFT are almost always performed in C-code mainly because its modularity. However, DFT and FFT in C-code are exhaustive for those who want to learn how the DFT and FFT work. Here, the objective is to present a step-by-step way to implement DFT and FFT. An 8-point DFT and FFT is presented using simplified blocks.

The simulation used in this report is freely available on http://busarello.prof.ufsc.br/