🚀 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...

1) Inverse DFT differs from DFT by the sign of the exponent and (if you're
   not a mathematician) a factor of 1/N (assuming N data points) 
2) FFT is simply a fast method for computing a bunch of DFT values.  With
   DFT, you could compute the spectral value at any frequency you care, but it
   takes O(N) operations for each frequency.  FFT gives you the spectral
   values at N equidistant frequencies for a total cost of O(N log N) (N has
   to be a power of 2), significantly cheaper than the O(N^2) sweat the regular
   DFT works up.  

SR

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