Talk:Goertzel algorithm

From Wikipedia, the free encyclopedia

[edit] How does this work?

I see sample code in C but nothing in English that describes the algorithm. --Damian Yerrick (☎) 19:30, 25 March 2006 (UTC)

There have been numerous edits that have fleshed out the article since the tag was added so I removed it. Feel free to add it back, but please leave some specific suggestions as to how the article could be improved. Lunch 02:36, 21 November 2006 (UTC)

I have used the C code and have found that the number of samples used can have a signeficant effect on the accuracy of the filter. I would like to know more about the practical selection of the value for GOERTZEL_N. --R Parker ANU 00:32, 14 February 2007 (UTC)

[edit] Problems with the article

Here are some things that should be fixed, but which I don't have time to fix now:

  • Goertzel can be used to compute any frequency output of the DTFT (for a finite/windowed signal), not just the discrete "bins" of the DFT.
  • The operation counts cited for "the" FFT are for radix-2 Cooley-Tukey only (and are only the leading N log2 N term); it is incorrect to attribute them to "the" FFT algorithm in general (there are many distinct FFT algorithms).
  • The question of comparing Goertzel to FFT algorithms is made more complicated than the article suggests by the existence of "pruned" FFT algorithms, which compute M outputs in O(N log M) time instead of Θ(N log N), and may be faster than Goertzel (in my experience) for M as small as 10. See http://www.fftw.org/pruned.html (for example).
  • The article intro should clearly state that Goertzel computes M outputs of a DFT (or DTFT) from N samples in Θ(N M) time, the same as evaluating the DFT or DTFT formula directly, and that the advantage of Goertzel over the naive DTFT formula lies in the reduction of the constant coefficient.
  • The article should also point out that Goertzel's computational advantages come at a price: it is more susceptible to roundoff error than the DTFT formula, and much more susceptible than a typical FFT (that is, its roundoff errors grow faster with N). (This is well-known in the literature; see this Usenet thread for references, more precise statements, and some example numbers.)

—Steven G. Johnson 05:45, 3 January 2007 (UTC)