The Cyber-Spy.Com Usenet Archive Feeds Directly
From The Open And Publicly Available Newsgroup
This Group And Thousands Of Others Are Available
On Most IS NNTP News Servers On Port 119.
Cyber-Spy.Com Is NOT Responsible For Any Topic,
Opinions Or Content Posted To This Or Any Other
Newsgroup. This Web Archive Of The Newsgroup And
Posts Are For Informational Purposes Only.
From: Chuck Simmons
Organization: You jest.
X-Mailer: Mozilla 4.61 [en] (X11; U; Linux 2.0.33 i586)
Subject: Re: fft in hc11 again
References: <firstname.lastname@example.org> <3DA87610.DD963CF3@webaccess.net> <3DA883C2.222BF1A@SpamMeSenseless.pergamos.net>
Date: Sat, 12 Oct 2002 22:42:47 GMT
NNTP-Posting-Date: Sat, 12 Oct 2002 15:42:47 PDT
Phil Hobbs wrote:
> Chuck Simmons wrote:
> > About time someone said something sensible about the FFT algorithms. In
> > particular pointing out limitations and problems. The difficulties with
> > FFT are great enough that the FFT function in Matlab usually does an
> > ordinary DFT instead unless the buffer size is fudged to force
> > conditions under which FFT is just as accurate. Generally, the FFT is
> > only preferable when computational cycles are at a premium. In that
> > case, all of the horrors of windowing and other spectral distorions can
> > be tolerated in order to get the job done. If speed is not an issue,
> > ordinary DFT methods are safer numerically.
> This is nuts. The FFT is nothing more or less than an efficient
> algorithm for computing the DFT. Apart from roundoff, it is
> mathematically identical to any other algorithm for computing the DFT.
> Furthermore, its roundoff performance is greatly superior to the N**2
> algorithms, because there are far fewer computations involved per
False for several reasons. There does not exist a meaningful FFT for a
buffer length of 3998, for example. As far as I can remember, roundoff
error is theoretically identical except that the FFT is more sensitive
to systematic roundoff error. Roundoff error is determined by
computational depth, number of multiply-adds per point in the final
result. The FFT reduces computational width by reusing results at all
depths. The depth is the same.
> FFTs are a bit blunder-prone, it's true, mainly due to the odd data
> rearrangement, and the usual off-by-one errors in writing array-based
> code, but from a mathematical point of view they are the clear winners
> in accuracy as well as efficiency.
There are major problems with interpreting FFT results. In fact, failure
to exactly match the FFT to the data set produces garbage that is
physically meaningless. It is sometimes impossible to know what is
garbage and what is real. For example, suppose you capture N rotations
of servo error from a disk drive. You now have a buffer containing N*K
points where K is the number of servo samples per rotation. Suppose that
N*K does not factor properly for an FFT so that N*K points are put into
a buffer of length M where M>N*K and M factors to a useful FFT. I'll
ignore the problem of windowing which simply obfuscates. What happens is
that the FFT will not properly find the spectrum. This can be proved by
comparing the FFT on the buffer of length M with a DFT on a buffer of
length K*M. Windowing or no windowing, the FFT stumbles and falls when
the natural period of the data fails to match the natural period of the
FFT. It is not always possible to make a data sequence match an FFT with
a finite number of samples. Therefore, in a vast number of cases, the
FFT will prove inferior to an ordinary DFT. For this reason, I always
prefer the ordinary DFT when the buffer size fits the data sequence
intrinsic period and does not fit an FFT of any sort. Matlab, of course,
because it decides based on factoring the buffer length what algorithm
should be used, takes care of this problem automatically.
Data interpretation is further complicated by misconceptions. Too many
engineers think of the DFT and the FFT as giving results that relate to
the Fourier transform on the real line. Actually, the FFT and the DFT
give results identical to a truncated Fourier transform on the unit
circle. I've seen engineers chase wild geese for weeks because they
didn't understand that fundamental fact.
The only way that you can do numerical analysis with a high degree of
success is to understand the problem and use the right algorithm for the
problem. Blindly stating that one size fits all is a blunder that bites.
I've seen it happen too many times.
... The times have been,
That, when the brains were out,
the man would die. ... Macbeth
Chuck Simmons email@example.com
Go Back To The Cyber-Spy.Com
Usenet Web Archive Index Of
The sci.electronics.design Newsgroup