Forums

selective fft

Started by amara vati September 21, 2004
which is the best fft method if want the spectrum only for a selective
set of points, say only 10-20% of the points in the entire spectrum.

amar
Use DFT directly or Goertzel algorithm of DFT
Alex.
"amara vati" <amaraavati@yahoo.com> wrote in message
news:f89b870.0409202130.deef21f@posting.google.com...
> which is the best fft method if want the spectrum only for a selective > set of points, say only 10-20% of the points in the entire spectrum. > > amar
the computations for DFT exceed that of the full FFT even for 2% of
the points. Let me check our Goertzel as I am not familiar with it

amar

"Aleksandr Baranov" <baranov@verizon.net> wrote in message news:<In44d.12648$%42.10767@trndny08>...
> Use DFT directly or Goertzel algorithm of DFT > Alex. > "amara vati" <amaraavati@yahoo.com> wrote in message > news:f89b870.0409202130.deef21f@posting.google.com... > > which is the best fft method if want the spectrum only for a selective > > set of points, say only 10-20% of the points in the entire spectrum. > > > > amar
Hello Amar,

Computational effort is commonly estimated by required multiplications.
These are O(N*N) for DFT and O(N*log2(N)) for FFT (where N is computed field length).
Hence if you're intressted in e.g. 12.5% of the points (1/8) than
multiplications of a DFT of N=256 are nearly the same of a limited DFT.
For N>256 FFT is still faster for N<256 DFT is faster.
From that we can estimate that your length is 512 (leading to the theoretical value of 2%)
or 1024 (as summation is an issue but not mentioned in the estimation).
Am I right ?

                        Wolfgang


amara vati wrote:
> which is the best fft method if want the spectrum only for a selective > set of points, say only 10-20% of the points in the entire spectrum.
If the points are equally spaced on the unit circle, you can use the chirp-z transform. Regards, Andor
Wolfgang wrote:

> Hello Amar, > > Computational effort is commonly estimated by required multiplications. > These are O(N*N) for DFT and O(N*log2(N)) for FFT (where N is computed field length). > Hence if you're intressted in e.g. 12.5% of the points (1/8) than > multiplications of a DFT of N=256 are nearly the same of a limited DFT. > For N>256 FFT is still faster for N<256 DFT is faster. > From that we can estimate that your length is 512 (leading to the theoretical value of 2%) > or 1024 (as summation is an issue but not mentioned in the estimation). > Am I right ? > > Wolfgang
Even at 64 points, FFT convolution is faster than transversal. An often unrecognized bonus it that speed and accuracy increase together. Greater speed comes from fewer calculations, which in turn contribute fewer round-off errors. (FFT scaling nullifies this somewhat with integer calculations.) Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
"Andor Bariska" <an2or@nospam.net> wrote in message
news:41517f90@pfaff2.ethz.ch...
> amara vati wrote: > > which is the best fft method if want the spectrum only for a selective > > set of points, say only 10-20% of the points in the entire spectrum. > > If the points are equally spaced on the unit circle, you can use the > chirp-z transform. > > Regards, > Andor >
Don't you get the same thing just doing a shorter FFT? Puzzled Mike
Are the points in a continuous frequency interval?

Dirk Bell

amaraavati@yahoo.com (amara vati) wrote in message news:<f89b870.0409202130.deef21f@posting.google.com>...
> which is the best fft method if want the spectrum only for a selective > set of points, say only 10-20% of the points in the entire spectrum. > > amar
Dear Amar,
you can check what could give a "downconverter" approach :

- Do a digital downconvertion of your band of interest to DC or to a low IF
(mixing your input signal with a DDS-generated digital sine wave with a
fixed frequency close to your band of interest, then low pass filter it and
decimate it with a CIC and/or FIR filter. This way you get a signal that
includes only the information you are looking for...
- Do a FFT on the downconverted signal, with a sample rate 10 times lower
than your input signal...

For 10% I'm quite sure it will not be cost effective in terms of Mips with a
full FFT, however for very narrow analysis bandwidth it could be efficient,
no ?

Cheers,

Robert Lacoste
ALCIOM - The mixed signal experts
www.alciom.com


"amara vati" <amaraavati@yahoo.com> a &#2013265929;crit dans le message de
news:f89b870.0409202130.deef21f@posting.google.com...
> which is the best fft method if want the spectrum only for a selective > set of points, say only 10-20% of the points in the entire spectrum. > > amar
Mike Yarwood wrote:
> "Andor Bariska" <an2or@nospam.net> wrote in message > news:41517f90@pfaff2.ethz.ch... > >>amara vati wrote: >> >>>which is the best fft method if want the spectrum only for a selective >>>set of points, say only 10-20% of the points in the entire spectrum. >> >>If the points are equally spaced on the unit circle, you can use the >>chirp-z transform. >> >>Regards, >>Andor >> > > > Don't you get the same thing just doing a shorter FFT?
I don't understand your question: shorter than what? The N point DFT evaluates the spectrum at N evenly spaced points on the whole unit circle. The chirp z transform can evaluate the spectrum at N points evenly spaced on any subinterval of the unit circle (perhaps you have heard of zoom FFT?). The N point chirp z transform can be implemented using two N point FFTs plus an N point convolution (I think). Regards, Andor