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
In the Definition of the DFT, there is a factor called the Twiddle Factor
If we take an 8 bit sample sequence we can represent the twiddle factor
as a vector in the unit circle. e.g.
where N = number of samples.
It is periodic. (i.e. it goes round and round the circle)
That the vectors are symmetric
The vectors are equally spaced around the circle with spacing
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)
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.
The twiddle factors are inversely symmetric about the origin.
inverse of the vector)
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
or back to DFT Contents or back
to Main Contents