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
selective fft
Started by ●September 21, 2004
Reply by ●September 21, 20042004-09-21
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
Reply by ●September 22, 20042004-09-22
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
Reply by ●September 22, 20042004-09-22
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
Reply by ●September 22, 20042004-09-22
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
Reply by ●September 22, 20042004-09-22
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 ? > > WolfgangEven 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. �����������������������������������������������������������������������
Reply by ●September 22, 20042004-09-22
"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
Reply by ●September 22, 20042004-09-22
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
Reply by ●September 23, 20042004-09-23
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 �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
Reply by ●September 23, 20042004-09-23
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
