Discrete Fourier transform

cosmos 1st December 2017 at 3:39pm
Fourier transform

We approximate the Fourier transform with a Discrete transform. The derivation can be done with the following process:

Sample signal by multiplying by Dirac comb –> FT gets convolved with another Dirac comb, thus repeating it and making it periodic.

Then sample the FT by multiplying it with another Diract comb –> then dually, the signal gets convolved by another Dirac comb which repeats it making it periodic.

As both FT and signal are now periodic, we can just look at one period of each (which now has all the information in our modified signal/FT). But because both are discretized with these Dirac combs, within one period there is now only a finite number of values. These values for the FT are the discrete Fourier transform, which can in fact be calculated easily directly from the also finite number of values within one period of the modified time-domain signal!

See Saad exercises for DTC

The famous Fast Fourier transform is just an efficient algorithm to compute the discrete Fourier transform.