|
Likely DFT abbreviates discrete Fourier transforms. By now the main interest in DFT is the FFT -- fast Fourier transform, for positive integer n points, n / log(n) times faster. The FFT was reinvented by J. Tukey, at Princeton and Bell Labs, at a US Presidential Science Advisors meeting, while Tukey was taking meeting notes with one hand and doing Fourier derivations with the other, from a query from R. Garwin, at IBM's Watson lab. Garwin said he was using too much computer time calculating Fourier transforms, so Tukey showed him the FFT. Later Cooley at IBM programmed the FFT, and Cooley and Tukey published the work. The FFT was revolutionary for signal processing, for sonar, radar, molecular spectroscopy, etc. The sampling issue is: Suppose have a periodic waveform with highest frequency 20 KHz
(kilo Hertz, 1000 cycles per second). Then there is the canonical theorem of interpolation theory that says that can reproduce the wave form exactly from the values of the waveform at equally spaced points 40,000+ times a second, or some such (there is a detail right at the 40,000). There is a cute pseudo-proof based just on pictures! So, for DFT/FFT, we start with those sampled values, and that's the "discrete" part. E.g., the reason audio CDs use 44 KHz or some such is that they want to be good for music up to 22 KHz. If the music really does have significant power at 22 KHz and we sample at only, say, 15 KHz, then we will have under sampled and end up with distorted music. A computer sound card or chip has to reverse the discrete sampling and generate a continuous waveform for the audio system and speakers, that is, to analog. There is a good start on Fourier series (for periodic waveforms) with the math done carefully in W. Rudin, Principles of Mathematical Analysis. If a waveform is not periodic but defined for all time, then we can do the closely related Fourier transform, and there is a nice treatment of the math in W. Rudin, Real and Complex Analysis. Suppose we have waveforms x(t) and y(t) where t is time and x(t) and y(t) are real numbers. Suppose we also have real numbers a and b. Suppose we are in, say, a concert hall and musicians are playing x(t) and y(t). Suppose due to the concert hall, for function h what we hear from x is h(x). Then we hope and believe that h( ax + by ) = ah(x) + bh(y) that is, the the concert hall effect h
is a linear operator. If in addition
h doesn't change over time, say, yesterday
to tomorrow, then, presto, bingo: All h
and the concert hall can do to x and y is
adjust the volume of the harmonics! Or,
a time invariant linear system is a
linear operator and, from Fourier theory,
a convolution. Here I am simplifying
somewhat. Well, the world is awash in linear
systems, especially for sonar and
radar. So, one of the big, early
uses of DFT/FFT was in analyzing
the acoustic signals from reflections
from subsurface layers from
small explosions at the surface,
all for looking for oil. |