Fourier Series, Fourier Transform

Discrete Fourier Transform (DFT)

The discrete Fourier transform converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.

The derivation from how you get to the DFT comes from Fourier Series.

We get that

  • Discrete data is expressed as a sum of coefficients
  • is a Root of Unity where

To find , we’ll need another useful property of our Nth roots of unity:

We can now convert any data set into its Fourier coefficients, and back!

Inverse DFT:


The discrete Fourier transform is invertible.

Splitting DFT into 2 to get to the FFT

The usual DFT of the sequence is

We can express with DFTs of two new arrays of half the length where

Then, and

This is how we can use the FFT.

Lack of standardization


As consequences of the properties of th roots of unity…

  1. The sequence is doubly infinite and periodic. i.e., If we allow or , the coefficients repeat.
  2. Conjugate symmetry: If data is real,

Hence the are symmetric about