Re: FFT for N Not a Power of 2

"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 of
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?

No.

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.



Bill


.

Relevant Pages

  • Re: FFT for N Not a Power of 2
    ... 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. ... I have a feeling that radix 4 and perhaps radix 8 are more efficient than radix 2 and that some transforms used large factors. ...
    (sci.optics)
  • Re: Really FFT?
    ... Is it then really a FFT (CPU ~ O(n ln n)) of a mere FT? ... FFT radix that wastes CPU time. ... means that padding to the next power of two is not such a bad idea ...
    (sci.math.num-analysis)
  • Re: FFT Radix
    ... aligned and ready for input into the FFT. ... Is it possible to use 64 radix 2 butterflys in front of two 64 point ... "Mixed-radix" is a generic term for when you use a variety of radices ... or three radix-2 steps followed by two radix-4 steps. ...
    (comp.dsp)
  • Re: FFT for N Not a Power of 2
    ... remove the largest number of observations that are a power of 2, ... There are FFT algorithms that work for any N, including prime numbers, but ... with floor rising near the two tones. ... had to ensure that the length of the window and periods of each of the ...
    (sci.optics)
  • Re: Why is more power required for BASS?
    ... Beware of FFT - that shows energy, not power. ... a steady 1V RMS 1 kHz tone may display ...
    (rec.audio.pro)