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

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.

>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

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

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

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
 

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

On Fri, 18 Oct 2013 09:00:34 -0700, techsavyjoe wrote:

> I too was searching for an answer to this problem,(I too am learning
> DSP).
> I think u can find the idft using goertzel algorithm with the fact that
> time is reciprocal to frequency.
> 
> so dft{dft{x(n)}}=dft{X(k)}=N*x(-n)
> N is the length of the dft sequence.
> 
> so u actually find the dft of X(k) which is nothing but N*x(-n).

The Goertzel algorithm is, in my opinion, a honey trap set out to entrap 
beginners to DSP.

It is a supposedly-efficient way of finding just one bin of the DFT.  As 
such, it can come in handy when you need to separate out just one 
frequency component from a signal.

If you need lots of frequency information then the fast Fourier transform 
is more efficient.

If you want to trade off clarity in your software for storage space, then 
doing a multiply and accumulate reads much easier and assuming a pre-
calculated sine table should actually take fewer clock ticks on modern 
processors, and many fewer clock ticks on a DSP with dedicated MAC 
hardware.

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.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I too was searching for an answer to this problem,(I too am learning DSP).
I think u can find the idft using goertzel algorithm with the fact that time is reciprocal to frequency.

so dft{dft{x(n)}}=dft{X(k)}=N*x(-n)
N is the length of the dft sequence.

so u actually find the dft of X(k) which is nothing but N*x(-n).

On Thu, 22 Dec 2011 16:01:52 -0600, aredo3606gif wrote:

>>On Thu, 22 Dec 2011 12:01:00 -0600, aredo3606gif wrote:
>>
>>>>On Thu, 22 Dec 2011 07:48:25 -0600, 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.
>>>>
>>>>Faster, yes.  More accurate -- no; the errors tend to build up, so
>>>>inaccuracies in the initial computations are going to be magnified at
>>>>the
>>> 
>>>>end.
>>>>
>>>>> However what I don't get is that I can't find any example for the
> IDFT
>>>>> of the Goertzel algorithm.
>>>>
>>>>Probably because it is a really odd thing to try.  To get an inverse
> DFT
>>>>you need _all_ the bins, from a _complete_ DFT.  You could use the
>>>>Goertzel structure as an oscillator, and you could probably get things
>>>>working, but compared to the IFFT, it would be very inefficient.
>>>>
>>>>> 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?
>>>>
>>>>It isn't that simple, no.
>>>>
>>>>> 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?
>>>>
>>>>You are confused.  A discrete Fourier transform is not limited to 2^N
>>>>samples in any way shape or form.  The early popular versions of the
>>>>fast
>>> 
>>>>Fourier transform (FFT) were, but modern algorithms handle any number
> of
>>>>input samples.
>>>>
>>>>What would surely lead to errors is using one or two bins out of a
>>>>larger
>>> 
>>>>transform, and trying to do an IFFT on just those.
>>>>
>>>>> If anyone could explain to me more clearly and provide a way to do
>>>>> inverse Goertzel both 1st order and 2nd order.. Thanks.
>>>>
>>>>Yes -- don't do it, and learn some DSP theory so you know why.
>>> 
>>> So the Goertzel Algorithm for forward DFT provided by Burrus in 1985,
> as
>>> found here in its Fortran version:
>>> 
>>> http://cnx.org/content/m17369/latest/
>>> 
>>> would be a wrong choice based on what you told me?
>>> 
>>> Doesn't that algorithm provide the same results as of regular DFT ?
>>
>>A wrong choice for what?  Doing an inverse DFT?  Yes.
>>
>>The Goertzel algorithm, _in theory_ provides the same results as _one
>>bin_ of a regular DFT.  If you want to do a complete N-point DFT using
>>Goertzel, you need to have N Goertzel filters running, and you need to
>>run them over N points.  So you need to do something like 3 * N^2
>>multiply/adds, and because the Goertzel tends to propagate errors, they
>>need to be of higher precision than otherwise.
>>
>>An FFT will do a complete N-point DFT in something like k * N * log(N),
>>where k depends on the cleverness of the programmer and whether N is
>>prime or easily factorable (and N = 2^n is _really_ easily factorable).
>>I couldn't quote k values at you -- but I wouldn't try to implement a
>>complete DFT using a Goertzel under any circumstances.
>>
>>--
>>My liberal friends think I'm a conservative kook. My conservative
>>friends think I'm a liberal kook. Why am I not happy that they have
>>found common ground?
>>
>>Tim Wescott, Communications, Control, Circuits & Software
>>http://www.wescottdesign.com
> 
> Searching on the subject I found this document dated 2004 where
> researchers there implemented an improved recursive based DFT/IDFT
> algorithm based on Goertzel. Do you think it would be worth trying to
> implement their ideas in actual code or it's just not worth it in any
> way regardless? Their explanations seem to point out that it can be an
> efficient solution for DFT calculation:
> 
What are you really trying to _do_?  Just dink around with the Goertzel 
-- in that case, go have fun.  Solve some specific problem?  In that 
case, tell us, and we'll tell you what we think is the best solution.

(Well, each of us will tell you what we think is the best solution, and 
then we'll fall to arguing amongst ourselves about why each of is right 
and everyone else is wrong.  But you'll learn something).

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com