Fast Fourier Transform

In the third experiment we pwerform FFT. The Fast Fourier Transform (FFT) is one of the most important in signal processing and data analysis, but the FFT is a complicated algorithm.
In complex notation, the time and frequency domains each contain one signal made up of N complex points. Each of these complex points is composed of two numbers, the real part and the imaginary part.
The FFT operates by decomposing an N point time domain signal into N time domain signals each composed of a single point. The second step is to calculate the N frequency spectra corresponding to these N time domain signals. Lastly, the N spectra are synthesized into a single frequency spectrum.