Discrete Fourier Transforms

Back to my page

Paul's DFT Page

One of the major tools used in signal processing is the DFT, which stands for Discrete Fourier Transform. The reason we need to to a DFT instead of a Fourier Transform is that our computers are limited in their abilites. They use sampling, and they have limited memory, so we have to adapt to the computers.

What is a DFT?

A DFT is like doing a Fourier Transform, but instead of doing it with an integral, we do it with discrete values and a sum. A Fourier Transform looks like this:
$X(f)=\int _{-\infty }^{\infty }x(t)e^{-j2\pi ft}\,dt$
Which uses an integral, while the DFT which looks like this:
$X(f)=\sum _{n=0}^{N-1}x(n)e^{\frac {-j2\pi nm}{N}}$
Which is using a sum and a discrete series of delta functions x(n) instead of the continuous function x(t).

What is it used for?

The DFT is (as the name suggests) the discrete version of the continuous Fourier Transform. This is important because computers can only truly work in the discrete time domain. You can use it to find out frequency and phase information about a discrete signal.

Things to know about a DFT

A Discrete Fourier transform has some limitations. The first is that it can only test for discrete frequencies. Each frequency in the output of the DFT is a multiple of the fundamental frequency. The fundamental frequency is based on the number of samples used in the transform and the sampling rate. If the sampling rate of a signal is 100 Hz (100 samples per second) and the number of samples stored is 40 samples, that means that the period of the fundamental frequency is
$T_{0}={\frac {40samples}{100samples/second}}=0.4seconds$.
Therefore the fundamental frequency will be:
$f_{0}={\frac {1}{T_{0}}}=2.5Hz$.
This is important because if your signal contains a frequency that is not an exact multiple of the fundamental frequency, it will not show up as a single spike like it would in the continuous Fourier Transform.

Another important thing to know is the range of frequencies that the DFT shows. A DFT shows frequencies in the range $[0,2\pi )$. However, only 1/2 the frequencies are positive frequencies. In the range $[0,\pi ]$ the frequencies are positive. The negative frequencies are in the range $(\pi ,2\pi )$. Why are the negative frequencies above the positive frequencies? That is a good question, and the answer has to do with the unit circle. I need to do more explanation here.