Re: FFT for N Not a Power of 2
- From: Joseph Gwinn <joegwinn@xxxxxxxxxxx>
- Date: Sat, 22 Nov 2008 12:20:53 -0500
In article <4926F19F.4050708@xxxxxxxxxxxxxxxxxx>,
Phil Hobbs <pcdhSpamMeSenseless@xxxxxxxxxxxxxxxxxx> wrote:
Bill Davy wrote:
"Phil Hobbs" <pcdhSpamMeSenseless@xxxxxxxxxxxxxxxxxx> wrote in message
news:4922B772.7090503@xxxxxxxxxxxxxxxxxxxxx
W. eWatson wrote:
It would seem that the FFT is applicable to only data with a number ofNo.
observations that are a power of 2. Is that correct? If so, does one only
remove the largest number of observations that are a power of 2, while
ignoring the remainder?
There are FFT algorithms that work for any N, including prime numbers, but
they're a few times less efficient than radix-2 FFTs.
Not sure that's right. I have a feeling that radix 4 and perhaps radix 8
are more efficient than radix 2 and that some transforms (I seem recall one
by Singleton in an IEEE publication) used large factors. And somewhere
there is a program that will generate an efficient FFT program for a
specified number. Of course, if it's a prime, you're stuffed.
You're only stuffed if you're Tukey. ;) The fast algorithsm for prime N
iiuc involve taking two different chirp-Z transforms in a row, but
they're still N log N algorithms, like the Cooley-Tukey and Sande-Tukey
algorithms. It's true that the quicker FFTs, e.g. FFTW don't use a pure
radix-2 approach--but it sounds as though the OP is trying to understand
FFT spectral estimation. Misapplied FFTs are famous for generating
reasonable-looking wrong answers, so becoming clear on what's actually
going on is the first order of business.
Plausible but wrong for sure. I once did this to myself while using
Mathematica to simulate third order intermodulation in the receive path
of a UHF radar.
Because this was simulation, I used test tones with periods that were
both exact multiples of the sampling window, thus eliminating splice
errors when the FFT did its job. However, I got an odd-looking "noise
floor" (there being no noise in the simulation) at -30 to -50 decibels
below the two carriers, with floor rising near the two tones. Now given
that Mathematica uses 64-bit IEEE-754 Double Floats for such things, one
would expect a floor around -300 dBc caused by accumulated roundoff
errors.
At first I thought that Mathematica was not correctly handling FFTs with
lengths not a power of two, but later discovered the true problem: One
had to ensure that the length of the window and periods of each of the
two test tones were such that there was no discontinuity at the splice
when one notionally rolled the window into a cylinder. Being off by
even one sample generated enough wideband "energy" to raise the floor
everywhere. It was not enough the the number of samples be a power of
two, although that did yield the shortest run times. This also
explained why the larger the length of the window (in samples),the lower
the floor - the "energy" was of fixed magnitude and was being spread
uniformly into the bins of the FFT, so if there were more bins there was
less energy per bin.
Joe Gwinn
.
- References:
- FFT for N Not a Power of 2
- From: W. eWatson
- Re: FFT for N Not a Power of 2
- From: Phil Hobbs
- Re: FFT for N Not a Power of 2
- From: Bill Davy
- Re: FFT for N Not a Power of 2
- From: Phil Hobbs
- FFT for N Not a Power of 2
- Prev by Date: Re: lens alignment stage for multiple degress of freedom
- Next by Date: Re: FFT for N Not a Power of 2
- Previous by thread: Re: FFT for N Not a Power of 2
- Next by thread: Re: FFT for N Not a Power of 2
- Index(es):
Relevant Pages
|
