Implementation of the Discrete Fourier Transform, cheat-sheet

The Discrete Fourier Transform is used to convert an equally-space sampled signal from its representation as a function of time to its representation as a function of frequency. The DFT calculates \(n/2\) coefficients from \(n\) samples covering \(D\) seconds. These coefficients (complex numbers) are the magnitude and phase at frequencies \(\frac{0}{D}\)Hz, \(\frac{1}{D}\)Hz, ..., \(\frac{n/2-1}{D}\)Hz of cosine functions. An efficient algorithm to calculate these cofficients is the Fast Fourier Transform. This algorithm works only if the number of samples is a power of two.

Sampling of the function:

Discrete Fourier Transform:

Spectrum of the function from its DFT coefficients:

Reconstruction of the function from its DFT:

Example of a square wave function (in red) DFT converted and reconstructed by sampling from t=1s to t=5s using 128 samples. First graph shows the magnitude for each of the 64 frequency bins (spectrum), second graph shows the square wave function and its reconstruction (in blue) from the DFT coefficients.