Discrete Fourier Transform

Everyone has heard of Fourier Transform (FT). It's used to convert a signal from time domain to frequency domain. But what is Discrete Fourier Transform?

I don't mean Discrete Time Fourier Transform, where the integral for Continuous Time FT is replaced with a summation, for discrete time signals. Discrete Fourier Transform (DFT) is the sampled form of DTFT. Since nowadays, almost all systems are digital, we have to sample the continuous signal given by DTFT, to obtain a discretised version of it. The signal is sampled at integer multiples of (2π/N). This, we can then process in a digital system.

We implemented this transform using C programming for an 'N' point discrete time signal. The value of 'N' was taken as input from the user. Of course, this discretisation is at the cost of accuracy. But this error can be decreased by appending zeros at the end of the actual signal, which gives a larger value of N giving us a better spectrum. The reason for this increase in the accuracy is that DFT always gives periodic results. So even if your signal is not periodic, it has to be assumed periodic! If we expand the original time domain signal, the DFT output gets compressed and vice versa.

The only drawback is that it's too slow for real time processing. A computer or any processor will take a lot of time to perform N square complex multiplications and N(N-1) complex additions. Obviously, we don't practically use this. The solution: Fast Fourier Transform!