Mathematics of the DFT

The continuous form of the fourier transform is

If we then discretize the continuous x(t) we get: 

which in turn gives us :

What we have now is equivalent to a discrete time signal x(n). Substituting into the continuous form of the the Fourier Transform gives us

If you look at the last equation, you will see that the integral has been replaced by a summation. As N (the number of samples) increases the result goes to infinity, so to stop this happening we multiply by 1 / N.

The summation is now the discrete equivalent of a continuous integration. This is the Discrete Fourier Transform (DFT). To make it appear simpler it is rewritten as

The DFT Equation

Twiddle Factor

In the Definition of the DFT, there is a factor called the Twiddle Factor
where N = number of samples.
If we take an 8 bit sample sequence we can represent the twiddle factor as a vector in the unit circle. e.g.

Note that

  1. It is periodic. (i.e. it goes round and round the circle)
  2. That the vectors are symmetric
  3. The vectors are equally spaced around the circle with spacing 
where  and

In the equations above  is the sampling frequency, and N is the number of samples.

is also called the frequency resolution or BIN SPACING of the DFT outputs, i.e., how far apart each sample is on the frequency domain.

Even though it may seem rather obscure this explains, mathematically, some of the properties of the DFT results.

The Twiddle Factors map onto the unit circle and are periodic.

Remember that the frequencies have been normalized here, that is, the sampling frequency is 2pi. It also take 2pi radians to go round the unit circle. So once round take you to the sampling frequency !! Twice round is just reproducing the results that you got first time round (in the range 0 to 2pi). i.e. the DFT results are PERIODIC about the sampling frequency (2pi)

The twiddle factors are inversely symmetric about the origin.

i.e. (The inverse of the vector)

 

 
 
 

This means that only the first half (0 to pi) of the twiddle factors contain all the necessary information as the second half is just an inverse of the first half.
 
If you look at the DFT equation you will see that for an N sample sequence it produces N output samples in the frequency domain. But because of the Twiddle Factor, we only need the first half (up to half the sampling frequency, or as it's commonly called half the Nyquist frequency). Remember your sampling theorem where any frequencies above half the sampling frequency was lost. This is in the range (pi to 2pi).

DFT response is often COMPLEX

The frequency response obtained from the DFT is often complex even though our original signal may have been completely REAL. How is this so, where does the complex part come from?

If you look at the Twiddle Factor you will see that the exponential has a j term. So unless our input signal can cancel this out, our frequency response will contain this j term and will be complex.

On to DFT Properties or back to DFT Theory

 or back to DFT Contents or back to Main Contents