Calculation of Discrete Fourier Transform(DFT) in C/C++ using Naive and Fast Fourier Transform (FFT) method

Discrete Fourier Transform has great importance on Digital Signal Processing (DSP). There are many situations where analyzing the signal in frequency domain is better than that in time domain. The Fourier Transform actually converts the function in time domain to frequency domain, some processing is done in frequency domain, and finally inverse Fourier transform converts the signal back into time domain. The term discrete means the signal is not continuous rather it is sampled by some sampling frequency i.e. only some samples are taken in certain interval (also called period). The sampling frequency depends upon the frequency of original signal and this must satisfy Nyquist criteria. A simple example of Fourier transform is applying filters in frequency domain of digital image processing. Before looking into the implementation of DFT, I recommend you to first read in detail about the Discrete Fourier Transform in Wikipedia. If you are already familiar with it, then you can see the implementation directly. The 1 dimensional DFT can be calculated by using the following formula