🚀 go-pugleaf

In article <7899@microsoft.UUCP> brianw@microsoft.UUCP (Brian Willoughby) writes:
>Its been a while since I studied this in college, anyone care to describe
>the DFT vs. FFT in layman's terms, or point to a text which does?  I seem
>to remember that the inverse FT is basically the same operation as the FT
>from time- to frequency-domain...

OK, here goes.  First thing to do is to read Bracewell's book on the
Fourier Transform.  Then you might understand my rather poor
explanations.  It's a lot easier to explain if you can draw nice
squiggly lines and diagrams, so bear with me please.

Regarding the DFT and the FFT: they are one and the same thing.  The
discrete Fourier transform (DFT) is a truncated and sampled version of
the continuous Fourier transform (FT) and is a computable
approximation of the FT.  The Fast Fourier Transform is merely a
well-known, computationally efficient way to calculate the DFT if the
number of samples is a power of 2.

The DFT is characterised by two quantities: the number of points, N,
and the sampling time, T.

To derive the DFT from the FT requires three steps: sampling of the
continuous time series, truncation of the now sampled series and
making a continuous, periodic set of samples by placing the N sampled
points end-to-end.  This is achieved by multiplying by a comb function
with separation T to sample the points, then by multiplying by a
top-hat or pill-box gating pulse of length NT, and finally by
convolving with a comb function with separation NT to form a signal
with period NT.

What does this look like in the frequency domain?  The sampling stage
(mult by comb(T)) causes the frequency spectrum to be replicated in
frequency every 1/T (this explains why aliasing occurs if the freq
spec extends beyond 1/2T), the truncation stage "smears" the data by
convolving them with a sinc(1/NT) function, and the time-domain
replication is what causes the freq spec to be periodic and *not* the
sampling stage (an important and oft misunderstood point).

Thus, the DFT is a derivative of the continuous FT, and this
three-stage process can be used to predict and analyse the effect on
the DFT or the time-domain of most operations.  Just remember that T
and 1/T, and that multiplication and convolution are transform pairs,
and you won't go far wrong.

As for the connection between the forward- and the backward-FTs, there
is only a minus sign in the exponent of the kernel that changes.
Whether you define the forward-version to be exp(-2*pi*j*f*t) or
exp(2*pi*j*f*t) is just a matter of choice, but the backward-version
must be of the opposite sign.

>Brian Willoughby
>UUCP:           ...!{tikal, sun, uunet, elwood}!microsoft!brianw
>InterNet:       microsoft!brianw@uunet.UU.NET
>  or:           microsoft!brianw@Sun.COM
>Bitnet          brianw@microsoft.UUCP


-- 
Hubert Matthews      ...helping make the world a quote-free zone...

hjm@cernvax.cern.ch   hjm@vxomeg.decnet.cern.ch    ...!mcvax!cernvax!hjm