On Thursday, December 22, 2011 8:48:25 AM UTC-5, aredo3606gif wrote:> Hello, > > > > I found various documents regarding the Goertzel Algorithm along with > > formulas, pseudocodes and Fortran implementations as a way for performing a > > faster and more accurate DFT in real-time on a small number of samples. > > However what I don't get is that I can't find any example for the IDFT of > > the Goertzel algorithm. What is the trick to get the inverse computation > > out of using Goertzel either 1st order or 2nd order? > > Is it as simple as with DFT where a sign inversion practically inverses the > > transform or is it more difficult to achieve? > > Otherwise while Goertzel is not limited to 2^N input number of samples the > > standard IDFT is so using IDFT on a Goertzel computed DFT would surely lead > > to errors,right? > > If anyone could explain to me more clearly and provide a way to do inverse > > Goertzel both 1st order and 2nd order.. > > Thanks.In theory you can do the inverse transform via a Goertzel process, but let's go over why that brings new problems to the table. Standard Goertzel is a process whereby you recursively compute a single value of the DFT given a series of real valued data. To go the other way will work the same if your DFT's frequency values are all real valued and you make the oscillator rotate the other way. However, having only real valued frequency data is unlikely to be the case. Now the Goerzel algo is one version of using a driven oscillator to find a single DFT value, so you can drive the oscillator with complex values to achieve the desired result, but the extra computational machinery is going to nullify the savings that standard Goertzel brings to the table. The driven oscillator idea extends to doing cosine transforms as well, and you can find some .jpg engines using this algo. Clay
Goertzel Algorithm
Started by ●December 22, 2011
Reply by ●October 18, 20132013-10-18
Reply by ●October 18, 20132013-10-18
I thought the Goertzel was used to reduce computation when only a few frequency bin outputs are needed, not to reduce the number of input time samples. Mark
Reply by ●October 18, 20132013-10-18
On Fri, 18 Oct 2013 12:54:51 -0700 (PDT), makolber@yahoo.com wrote:>I thought the Goertzel was used to reduce computation when only a few frequency bin outputs are needed, not to reduce the number of input time samples. > >MarkPretty much. One of the driving applications was DTMF detection for telephone key presses. In that case there are only a few known tones to detect and it must be done quickly and cheaply. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
Reply by ●October 18, 20132013-10-18
On 10/19/2013 04:43 AM, Eric Jacobsen wrote:> On Fri, 18 Oct 2013 12:54:51 -0700 (PDT), makolber@yahoo.com wrote: > >> I thought the Goertzel was used to reduce computation when only a few frequency bin outputs are needed, not to reduce the number of input time samples. >> >> Mark > > Pretty much. One of the driving applications was DTMF detection for > telephone key presses. In that case there are only a few known tones > to detect and it must be done quickly and cheaply.I think it only got associated with DTMF detection because of a few application notes. Goertzel has been widely used for tone detection, especially on the PSTN, where the frequency of the expected tone is well known, but the duration doesn't need to be detected precisely. Of course, tone detection is trivial. Avoiding false detection is where things get interesting, and a wide range of approaches have been combined with Goertzel to deal with false detections. For things like 2280Hz/2600Hz signalling, where the duration of the tone needs to be passed on precisely, a purely time domain approach has generally proved more suitable. Steve
Reply by ●October 19, 20132013-10-19
>On Fri, 18 Oct 2013 09:00:34 -0700, techsavyjoe wrote: >[Snipped by Lyons]> >Even assuming that you've got an environment where the Goertzel is more >efficient, the IDFT isn't useful to do one bin at a time -- one "bin" of >the IDFT is just the signal value at one particular delay, and you're >generally interested in enough of them that it's far more efficient to do>the whole thing using the fast Fourier transform algorithm.Hi Tim, I agree with what you're saying here. I wonder if the DSP beginners in this thread understand that implementing the Goertzel algorithm, over N time- domain samples, produces a *SINGLE* frequency- domain sample. And when they write about performing an IDFT using Goertzel, are they thinking about producing a *SINGLE* time-domain sample? If they *ARE* talking about producing a single time-domain sample based on N freq-domain samples, it seems to me that you could do this using the Goertzel algorithm. I haven't tried this out, but I'm willing to bet one bottle of beer that you could (1) conjugate all your freq-domain samples, (2) perform a standard N-point Goertzel process to produce a single complex-valued time- domain sample, and (3) conjugate that single time-domain sample to arrive at your final result. Just a thought, [-Rick-] _____________________________ Posted through www.DSPRelated.com
Reply by ●October 23, 20132013-10-23
On Friday, October 18, 2013 3:43:25 PM UTC-5, Eric Jacobsen wrote:> On Fri, 18 Oct 2013 12:54:51 -0700 (PDT), makolber@yahoo.com wrote: > > > > >I thought the Goertzel was used to reduce computation when only a few frequency bin outputs are needed, not to reduce the number of input time samples. > > > > > >Mark > > > > Pretty much. One of the driving applications was DTMF detection for > > telephone key presses. In that case there are only a few known tones > > to detect and it must be done quickly and cheaply. > > > > > > > > Eric Jacobsen > > Anchor Hill Communications > > http://www.anchorhill.comAND, using slow, fixed-point, inefficient processors.
Reply by ●October 23, 20132013-10-23
On Wed, 23 Oct 2013 14:48:38 -0700 (PDT), maury <maury001@core.com> wrote:>On Friday, October 18, 2013 3:43:25 PM UTC-5, Eric Jacobsen wrote: >> On Fri, 18 Oct 2013 12:54:51 -0700 (PDT), makolber@yahoo.com wrote: >> >> >> >> >I thought the Goertzel was used to reduce computation when only a few frequency bin outputs are needed, not to reduce the number of input time samples. >> >> > >> >> >Mark >> >> >> >> Pretty much. One of the driving applications was DTMF detection for >> >> telephone key presses. In that case there are only a few known tones >> >> to detect and it must be done quickly and cheaply. >> >> >> >> >> >> >> >> Eric Jacobsen >> >> Anchor Hill Communications >> >> http://www.anchorhill.com > >AND, using slow, fixed-point, inefficient processors.Exactly. So having a really simple algorithm with low computational complexity was necessary for the job. Not having many multiplies helped, since on many of the candidate processors multiplies tended to take way longer than adds/subtracts. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
