The Goertzel Algorithm

http://www.eetimes.com/design/embedded/4024443/The-Goertzel-Algorithm

by dhotson • 15 years ago

82 17 15 years ago

Thrymr• 15 years ago

Cool, but news? Article is from 2002.

Kliment• 15 years ago

It was definitely new to me. I don't mind old technical articles if they are still relevant, and this one definitely is.

3oheme• 15 years ago

Well, it's some kind of news because I've never heard about that :-D

I find it really interesting

tef____• 15 years ago

How about this then? http://en.wikipedia.org/wiki/Discrete_Hartley_transform

scott_s• 15 years ago

Despite the name of the site, it's accepted that not everything that is posted is exclusively "news."

wbhart2• 15 years ago

Shouldn't this be "faster tone detection algorithm".

I don't see how to perform a convolution with this algorithm, which I would be able to do if it was an FFT.

There are many algorithms for FFT that are faster, e.g. the split radix FFT, Gentleman and Sande's approach, the Matrix Fourier Algorithm and scores of variations on a theme. The article doesn't make clear whether this is one of them.

colanderman• 15 years ago

You are correct. The title is very misleading.

dhotson• 15 years ago

My apologies, this stuff is still pretty new to me.

amalcon• 15 years ago

Indeed, a faster multi-frequency fourier transform would be a huge deal. It would speed up everything that involves multiplying large numbers (encryption, but also lots of biology and other scientific problems), due to FFT multiplication.

mdda2• 15 years ago

Not explicitly stated in the article : The reason this is so fast is that you're only detecting a single frequency. If you wanted to detect a few (M, say), you'd have to keep updating M sets of Qs. While M<<N this is really efficient (and each one looks like a notch filter, or something).

But for larger M, it's better to do the FFT, since that gives you back O(N) frequencies in O(NlogN) time - because of the tricks it can do with N if it's a power of 2.

wnoise• 15 years ago

> with N if it's a power of 2.

with N if it's highly composite. See, e.g. http://www.fftw.org/ which works fairly well even for non-powers of 2.

mdda2• 15 years ago

Very interesting : I was actually thinking about redoing the spectrometer music visualization for MythTV to be use 'piano keyboard' pitches (rather than the FFT that they're using at the moment). And I came to the conclusion that some kind of recurrence (short) resonant filter would do the trick (with 88 different copies) - but never got further than that, since I had limited imagination about what algorithms to search for. Unfortunately, I've got overwhelmed with other projects now...

shasta• 15 years ago

If you only want to detect one frequency, can't you jut use the "slow" fourier transform?

mahadri• 15 years ago

Yes, the discrete Fourier transform (DFT) detects N frequencies in parallel, where N is the block size, and you can disregard the uninteresting frequencies. The fast Fourier transform (FFT) is an efficient algorithm that computes the DFT. For detecting M frequencies where M << N, the Goertzel algorithm requires less computation than the FFT. Also, the Goertzel algorithm allows targeting more exact frequencies regardless of the sampling rate (Fs), while the FFT's bins have a fixed spacing of ±Fs/N.

As with everything, there are trade-offs associated with these three options.

skew• 15 years ago

This looks like a row of a DFT, but using the history variables and the single cosine to avoid computing the coefficients from scratch.

shollos• 15 years ago

You can find C code for the Goertzel algorithm at: http://www.exstrom.com/journal/sigproc/index.html

The Goertzel Algorithm

Related Stories