**Mail Archives: djgpp/1999/06/17/18:50:23**
El día Wed, 16 Jun 1999 13:30:19 +0300 (IDT), Eli Zaretskii
<eliz AT is DOT elta DOT co DOT il> escribió:
>> What are you calling DFT and FFT? DFT is a transformation, and FFT is
>> an algorithm to implement DFT, so how is it that you seem to have
>> separate functions for DFT and FFT?
>
>FFT is an algorithm to perform a lot of DFT's simultaneously
>in an efficient way. A single DFT is just the value of the
>spectrum for a certain frequency, and doesn't need any algorithms
>to compute.
The DFT (Discrete Fourier Transform) is a mathematical transformation
that maps a complex valued discrete function, f(n), in another complex
valued function, F(m), which holds information about the frequency
spectrum of the former. The resulting function, F(m), can be evaluated
at exactly N points of the spectrum, where N is the number of data
points of f(n).
The FFT is an algorithm to efficiently compute the DFT which is mostly
used when N is a power of 2. There are many other algorithms which
also compute the DFT, like Goertzel's, but you can just compute the
DFT directly, that is, by using its *definition*. You can compute all
the N values of the DFT or just the ones you want, but in order to do
this you need an algorithm as well, even when it can be as simple as
traversing all the values of f(n) and multiplying them for the
appropiate complex exponentials. If you say that you need no
algorithms to compute the DFT, I may reply that you don't need one for
the FFT either, as it can be also expressed as a weighted sums of
complex exponentials, just like a DFT where most of the unneeded terms
have been left out.
Regards,
GUILLE
----
Guillermo Rodriguez Garcia
XXguille AT XXiies DOT XXes (ya sabes :-)

*- Raw text -*