The Goertzel Algorithm(eetimes.com)
eetimes.com
The Goertzel Algorithm
http://www.eetimes.com/design/embedded/4024443/The-Goertzel-Algorithm
6 comments
You are correct. The title is very misleading.
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.
[deleted]
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.
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.
> 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.
with N if it's highly composite. See, e.g. http://www.fftw.org/ which works fairly well even for non-powers of 2.
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...
If you only want to detect one frequency, can't you jut use the "slow" fourier transform?
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.
As with everything, there are trade-offs associated with these three options.
This looks like a row of a DFT, but using the history variables and the single cosine to avoid computing the coefficients from scratch.
You can find C code for the Goertzel algorithm at:
http://www.exstrom.com/journal/sigproc/index.html
[deleted]
Cool, but news? Article is from 2002.
It was definitely new to me. I don't mind old technical articles if they are still relevant, and this one definitely is.
Despite the name of the site, it's accepted that not everything that is posted is exclusively "news."
Well, it's some kind of news because I've never heard about that :-D
I find it really interesting
I find it really interesting
How about this then? http://en.wikipedia.org/wiki/Discrete_Hartley_transform
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.