4 ms·
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
by mdda 15y 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 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.
- adrianbg 15y agoGoertzel is just actually just computing a single DFT term... not that crazy.
- skew 15y agoThis looks like a row of a DFT, but using the history variables and the single cosine to avoid computing the coefficients from scratch.