Hi Guys! I'm quite a newby to all the stuff - but a motivated one - and have a question resp. a problem: at the moment i'm just working with some test-data - 1024 resp. 4096 samples. i'm trying to read a code from the spectrum, ie: at some well-defined frqs the can be a peak or not (will be 8-10 bins). doing this with the help of a full fft (dsp-powered) seems to be to slow for further applications. my research let me to the two algorithms: - goertzel - bluestein (chirp-z-transform, there should be also some interleaved version) which one would you suggest? speed is the critiria and some of the parameters can still be adjusted. thanx in advance, quaste

# goertzel vs. bluestein

Started by ●February 4, 2007

Reply by ●February 4, 20072007-02-04

quaste wrote:> Hi Guys! > > I'm quite a newby to all the stuff - but a motivated one - and have a > question resp. a problem: > > at the moment i'm just working with some test-data - 1024 resp. 4096 > samples. i'm trying to read a code from the spectrum, ie: at some > well-defined frqs the can be a peak or not (will be 8-10 bins). > > doing this with the help of a full fft (dsp-powered) seems to be to slow > for further applications. my research let me to the two algorithms: > - goertzel > - bluestein (chirp-z-transform, there should be also some interleaved > version) > > which one would you suggest? speed is the critiria and some of the > parameters can still be adjusted.What does resp. mean? Do you know the frequency of the interesting peak in advance? Goertzel is a spotlight you need to know where to point, not useful if you need a floodlight. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Reply by ●February 5, 20072007-02-05

Reply by ●February 5, 20072007-02-05

me again - giving further info about my problem. due to temperature and other influences the peak-position may vary and the number of peaks will be around 8. all this information makes me kind of sad, because the number of the bins to calculate exceeds 5/6*log2(N) (Goertzel) and the chirp-z-trans seems to be even slower. Does anyone have experience with Zoom-FFT or approximate FFTs? Is there any chance to get quite proper phase-info on the approximate FFTs? I think I will have to increase my hardware-power, but maybe there is somebody out there with a brilliant idea - keyword 'to grasp at straws'. Thanks, q

Reply by ●February 5, 20072007-02-05

quaste wrote:> respectively"1024 respectively 4096 samples"? Is English your mother tongue? Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Reply by ●February 5, 20072007-02-05

>quaste wrote: >> respectively > >"1024 respectively 4096 samples"? Is English your mother tongue? > >Jerry >-- >Engineering is the art of making what you want from things you can get. >¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ >no, my mother tounge is german - does it change anything about my problem? what's wrong about the formulation? ignore the 4096-version. quaste

Reply by ●February 5, 20072007-02-05

On Feb 4, 3:02 pm, "quaste" <thomas.wald...@ctr.at> wrote:> at the moment i'm just working with some test-data - 1024 resp. 4096 > samples. i'm trying to read a code from the spectrum, ie: at some > well-defined frqs the can be a peak or not (will be 8-10 bins). > > doing this with the help of a full fft (dsp-powered) seems to be to slow > for further applications. my research let me to the two algorithms: > - goertzel > - bluestein (chirp-z-transform, there should be also some interleaved > version) > > which one would you suggest? speed is the critiria and some of the > parameters can still be adjusted.Let me make sure I understand you. The problem is that you want to compute 8-10 bins of an DFT, and therefore the full FFT is somewhat wasteful, and you want to know what will be better? Let me phrase it more generally: you have data of length N and you want to compute K << N outputs of the DFT. One option is to use either Goertzel or the DFT formula directly. Both of these have O(N K) complexity, but Goertzel has a constant factor better by several times, at the expense of sacrificing some floating-point stability for frequencies near zero. Another option is a "pruned" FFT algorithm, which is an FFT with the unwanted operations thrown out. This has O(N log K) complexity. Whether it is worthwhile in practice depends strongly on N and K and which output bins you want, but I've observed it to be faster than Goertzel for the K lowest-frequency bins for K as small as 10 if N is large; see www.fftw.org/pruned.html for some example code and more information. However, I'm guessing that this isn't worth it for N=4096 and K=10. I don't think Bluestein's algorithm is going to buy you any performance if you want the same bins as the ordinary DFT, as opposed to a finer interpolation of some portion of the spectrum. At best, it would require you to implement a pruned convolution algorithm, which is at least as hard as a pruned FFT and arguably harder. At worst, the most common way to implement Bluestein is to use a *pair* of FFTs of length > 2N-2, and this is obviously worse than doing the full FFT. Cordially, Steven G. Johnson

Reply by ●February 6, 20072007-02-06

On Feb 5, 10:16 am, "quaste" <thomas.wald...@ctr.at> wrote:> >quaste wrote: > >> respectively > > >"1024 respectively 4096 samples"? Is English your mother tongue? > > >Jerry > >-- > >Engineering is the art of making what you want from things you can get. > >=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF==AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF> > no, my mother tounge is german - does it change anything about my > problem? > what's wrong about the formulation? > ignore the 4096-version. > > quasteIt explains why I don't understand the way you use "respectively". My computer died and this Google interface is the worst yet, so I'm sorry for any errors of form. Steven Johnson's response is better than any I could have made, so I apologize for having been a distraction. Jerry