5 ms·
The Goertzel Algorithm
- Thrymr 15y agoCool, but news? Article is from 2002.
- Kliment 15y agoIt was definitely new to me. I don't mind old technical articles if they are still relevant, and this one definitely is.
- 3oheme 15y agoWell, it's some kind of news because I've never heard about that :-D I find it really interesting
- tef____ 15y agoHow about this then? http://en.wikipedia.org/wiki/Discrete_Hartley_transform http://en.wikipedia.org/wiki/Discrete_Hartley_transform
- scott_s 15y agoDespite the name of the site, it's accepted that not everything that is posted is exclusively "news."
- deleted 15y ago[deleted]
- wbhart 15y agoShouldn'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 15y agoYou are correct. The title is very misleading.
- amalcon 15y agoIndeed, 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 15y ago[deleted]
- mdda 15y agoNot 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 15y ago> with N if it's a power of 2. with N if it's highly composite. See, e.g. http://www.fftw.org/ http://www.fftw.org/ which works fairly well even for non-powers of 2.
- mdda 15y agoVery 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 15y agoIf you only want to detect one frequency, can't you jut use the "slow" fourier transform?
- mahadri 15y agoYes, 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.
- shollos 15y agoYou can find C code for the Goertzel algorithm at: http://www.exstrom.com/journal/sigproc/index.html http://www.exstrom.com/journal/sigproc/index.html
- adrianbg 15y agoThere's a good derivation in http://www.mstarlabs.com/dsp/goertzel/goertzel.html http://www.mstarlabs.com/dsp/goertzel/goertzel.html