Forums

goertzel vs. bluestein

Started by quaste February 4, 2007
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


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. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
respectively
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
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. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
>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
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
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. > > quaste
It 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