QUESTION #704

What is the Discrete Fourier Transform?

Asked by: Ozair Sajid

Answer

Fourier Transforms are a very powerful tool used in physics to determine for example frequency components of a time signal, momentum distributions of particles and many other applications. It is basically a decomposition of a function into sinusoids, usually expressed as complex exponentials. This decomposition usually requires a continuous set of frequencies/wavelengths except in the case where the original function is already periodic. Computers can perform fourier transforms of functions but because they can only deal with discrete quantities, the Discrete Fourier Transform is introduced as an approximate numerical method for computing the Fourier Transformation of a function.
Answered by: Martin Archer, Physics Undergraduate, Imperial College London, UK

Answer

A good definition of the Fourier transform (and then the discrete Fourier transform) requires a more rigorous mathematical description that then follows with some interesting mathematical consequences. I don't think that's really appropriate here. A good place to start with some introduction to the mathematical concepts behind the DFT would be Wikipedia's: http://en.wikipedia.org/wiki/Discrete_Fourier_transform and http://en.wikipedia.org/wiki/List_of_Fourier-related_transforms That being said, I'll give an overall description that will hopefully communicate the usefulness of the DFT. If you're not familiar with the Fourier transform, its purpose is to decompose a function into sinusoidal basis functions. A common example of this is converting a time-domain signal (a signal varying in time) into its frequency components (i.e., adding those frequency components together will result in the original signal). The Fourier transform is applied to continuous-time signals. That is, it applies to signals that exist at all instants of time. It then breaks that signal into a possibly infinite spectrum of frequency components. When signals are sampled by a computer system, those signals are neither continuous-time nor have the possibility of containing non-redundant information with an infinite bandwidth. Additionally, an infinite transform is simply useless on a computer that works with finite constructs. So enter the discrete Fourier transform (or DFT), which takes a finite number of samples of a signal and transforms them into a finite number of frequency samples of that signal. So that's the very special difference. The discrete Fourier transform does not act on signals that exist at all time and continue to time infinity, the DFT applies to signals that exist at a finite number of time points and products a finite number of frequency points. Some may say the DFT approximates the Fourier transform. This is perhaps too gross of an over-simplification. The DFT approximates the DTFT (the discrete-Time Fourier Transform). And the DFT is to the DTFT as the Fourier series is to the Fourier transform... But like I said, you can get lost in the nuances without the mathematics for support.
Answered by: Ted Pavlic, B.S., Electrical Engineering Grad Student, Ohio State U.