Talk:Goertzel algorithm

Intent to rewrite

After referring to this article to see how well it covered the most important cases of applying the algorithm to real-valued data — and being disappointed — I continued studying why the article presentation seemed uneven. Here is my ill-considered list of problems, inaccuracies, and presentation glitches. My notations, if you wish to track details, are "Paragraph within section" counting parts separated by equation lines as if they were separate paragraphs, and "Sentence" within each paragraph.

Intro

P1S1 ambiguous grammar.
P1S2 misses the fundamental relationship that Goertzel algorithm and FFT algorithms are both means of computing terms of the DFT. Discussions should centre on the DFT, since this is what matters the most.
The introduction misses the important facts that the implementation code is small and well suited to small processors, and friendly to real-valued arithmetic. That might be more important than anything else in the introductory section.

Explanation

P1 Presentation is fragmented. The algorithm produces y(n) given an input sequence x(n). The s(n) terms are only intermediate. The entire filter should be presented up front, not just the IIR stage.
P2S3 It is false that omega parameter "should be" less than 1/2. That is entirely dependent on the application. While there are reasons related to sampling theory and the Nyquist limit for paying attention to this, the algorithm works just fine thank you for other values, even negative ones. Case in point: half of the calculations for a complex-valued DFT violate the stated "should be" rule.
P3 "For real inputs" is extraneous to the development of the algorithm and belongs later in the discussion of real-valued implementations. Unfortunately, that topic is essentially missing from the rest of the article.
P4 "Applying an additional FIR transform" — this will no longer seem plucked out of the air after P1 is improved. Then both of the Z transforms can be introduced together and dispensed with at one time.
P8 "...or, the equation for the (n+1) sample DFT sequence of x." This, unforunately, is seriously wrong. A simple change of notation that will make this clear. Replace w with K/N, where K is the DFT term index, and where N is the number of terms in the DFT input sequence. This will reveal (by comparing with the DFT definition) that this is NOT the expression for a N+1 term DFT, because then the frequency terms would have the form K/(N+1).The upper limit on the summation is not consistent with the definition of a DFT. This can become a serious problem if the algorithm is not terminated correctly.
P9 "which corresponds to the chosen frequency as..." Unfortunately, the equation isn't quite correct. Comparing to the immediately preceding equation, the value of y(n) should be used, otherwise the algorithm has not run to completion. However, there are conditions under which using the next-to-the-last term is valid... not discussed.
P11 "power does not depend on the phase factor" True... but if the presentation is done in a cleaner way, you don't need to think about it, because at least for DFT calculations, all of the extra phase terms have reduced to constant 1 and drop out, which is not obvious.
Though the theory is there, this article does not cover the important application details of applying the Goertzel algorithm to compute the value of a DFT term, in the same way that it does signal power. This is somewhat tricky (see P8 above). Wikipedia could do a great service by pointing out where implementations can easily go wrong.
In general, there is considerable notational ambiguity between n, the current term that the filter is calculating, and N, the particular term at which the filter finishes calculating.

Implementation

P1 "When implemented in a general purpose processor..." Unclear. If you don't save the filter states one way or another, the filtering won't work on any kind of processor.
The fact that the FIR filter is not evaluated until the last step is assumed but never mentioned specifically. This is actually a major feature of the algorithm, contributing to is efficiency, and this omission is a strange oversight.
The particular choice of a direct-form II IIR filter for the first stage is an important feature of the algorithm, because in general, the internal state representation of an IIR filter is not unique, and would not necessarily preserve the required history terms for the FIR filter to use. Not stating this explicitly is an oversight.

Complexity

I note that some of Steven Johnson's points were not addressed and should be.
My practical experience is that on some processors, the math is cheap but operations in external memory (i.e. large code, lookup tables, things that don't fit into registers and level-1 cache) suffer from a large latency penalty. For this reason, the complexity order predictions can underrate the Goertzel algorithm performance compared to an FFT.
"For real-valued input sequences, the amount of computation is halved in both cases." Well, this is approximately true, but only for the case of FFT variants specialized for real-valued data.
"must compute all N bins in parallel" Order of execution does not seem relevant to a complexity analysis.

Overall I am proposing a rewrite that will cover all of the issues above while discarding very little from what is currently in the article. Not ready to post, I need some numerical validation first. So past contributors, do not panic. Your contributions should still be there, but maybe located in a different place, maybe with some different dressing. Mostly, a much greater emphasis on more specific and orderly presentation with respect to practical calculations of DFT terms. I have some concerns about overall bulk. ParaTechNoid (talk) 00:45, 29 October 2012 (UTC)[reply]

Straying from topic

The author of the C code was obviously pleased with his efforts and wanted to show it off, but this is not really the place. And the example is far too long for the purpose of demonstrating the algorithm. If used at all, it should demonstrate just the algorithm, not the application, and this is already more appropriately done in the pseudo-code. Not all readers will be C programmers, it should be more generally applicable. The bulk of the topic is a discussion of DTMF which is hardly the point nor the only application. Only a small part of the code is in fact related to the Goertzel algorithm. I'd remove it except that it might look like vandalism. This is not the place to publish school your projects ;) —Preceding unsigned comment added by 217.40.148.115 (talk) 12:19, 26 March 2009 (UTC)[reply]

Did the C code work? Because I tried implementing the pseudo-code in C and it does not appear to work. The returned values vary dramatically depending on the value of N samples I give the algorithm. Perhaps there should be some explanation on how to implement it properly? --24.91.253.46 (talk) 06:54, 25 April 2012 (UTC)[reply]

Funny

If you enter the word goertzel in Google, this article is the second hit. I started this article and posted the working C code. I had spent years perfecting this code and it was part of a telecom switch. It actually worked and there is the remote chance that if you have used a telephone, you may have exercised this code as you pushed the buttons on your phone. I posted the code hoping to save some fragments of knowledge from a dying industry and in hopes that others smarter than me would make comments on the code and show how such a simple code segment could do such magical work as to extract digits out of signal samples.

Well the code is now gone and is replaced by a mathematical discourse that is quite clear to the small fraction of the population who has survived several years of advanced mathematics and who probably already has several textbooks lying around covered with dust and which contain the same information as presented on this page in its current form.

I also have a stack of 10 or 20 books on signal processing purchased at various times at thrift stores for perhaps a 50 cents or a dollar a book. Which basically tells you the value of mathematical writings of this sort.

To the above poster: If perhaps you would like to make the world a better place, instead of having fun taunting those who have less education than yourself, you might consider sharing some of your knowledge in a form that matters more than those thrift store books. —Preceding unsigned comment added by 70.102.57.178 (talk) 21:49, 28 October 2010 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Algorithm in reverse?

Is there a good external link that could be added (or academic reference) that explains how the algorithm is used in practice in reverse, say to generate DTMF tones? I have some DTMF generation code (the DtmfGenerator code by Plyashkevich Viatcheslav that's floating around in C and Java - don't know where it originally came from) that I think uses Goertzel in reverse for generating as well as recognizing the DTMF signal. But it doesn't explicitly say that, and the math is way over my head to try to figure it out from the code alone - it uses a transform function that goes by the name MPY48SR as part of the algorithm, and looks like it iteratively modifies and shifts a matrix of 6 values. That's all I can see from the code, anyway.. Anyway, anybody know a reference for theory and practice of reversing the algorithm for generation? — Preceding unsigned comment added by Jimw338 (talk • contribs) 20:55, 1 April 2012 (UTC)[reply]