Another Goertzel question

Hi Guys,

  our DSP pal Jon Harris and I have exchanged a few 
E-mails regarding the Goertzel algorithm.  If you 
recall, the Geortzel algorithm is implemented with 
an IIR filter structure with a 2cos(2*pi*k/N) feedback 
coefficient and an -exp(-j2*pi*k/N) feedforward 
coefficient.  The value k, which defines the 
frequency at which the filter resonates, is typically 
specified to be an integer.  (With k as an integer, 
the Goertzel algorithm computes the value of a 
single bin of an N-point DFT.)

Jon pointed out to me that k need not be an integer, 
and that non-integer values of k enhance the Goertzel 
algorithm's spectrum analysis capability because we 
can center our filter at *any* frequency between 
-Fs/2 and +Fs/2. (Not merely at integer multiples 
of Fs/N.)
SHEECE!!!  Now why in the heck didn't I think of that??

I did a little MATLAB modeling of this idea, and the 
Goertzel algorithm has the same frequency-domain 
behavior with a non-integer k as with an integer k.
As far as I can tell, Jon Harris should receive 
official comp.dsp authorization to reach around and 
pat himself on the back.

Anyway, have any of you guys run across this notion that 
k need not be an integer in the Goertzel algorithm.

Thanks,
[-Rick-]

Rick Lyons wrote:
> 
> Hi Guys,
> 
>   our DSP pal Jon Harris and I have exchanged a few
> E-mails regarding the Goertzel algorithm.  If you
> recall, the Geortzel algorithm is implemented with
> an IIR filter structure with a 2cos(2*pi*k/N) feedback
> coefficient and an -exp(-j2*pi*k/N) feedforward
> coefficient.  The value k, which defines the
> frequency at which the filter resonates, is typically
> specified to be an integer.  (With k as an integer,
> the Goertzel algorithm computes the value of a
> single bin of an N-point DFT.)
> 
> Jon pointed out to me that k need not be an integer,
> and that non-integer values of k enhance the Goertzel
> algorithm's spectrum analysis capability because we
> can center our filter at *any* frequency between
> -Fs/2 and +Fs/2. (Not merely at integer multiples
> of Fs/N.)
> SHEECE!!!  Now why in the heck didn't I think of that??
> 
> I did a little MATLAB modeling of this idea, and the
> Goertzel algorithm has the same frequency-domain
> behavior with a non-integer k as with an integer k.
> As far as I can tell, Jon Harris should receive
> official comp.dsp authorization to reach around and
> pat himself on the back.
> 
> Anyway, have any of you guys run across this notion that
> k need not be an integer in the Goertzel algorithm.
> 
> Thanks,
> [-Rick-]

Guys at Rice have massaged Old Man Goertzel pretty well, even showing
code to run his algorithm on old eight bitters fast enough for telephone
service. Why not poke around their web site a bit. Surely, you have the
credentials to be welcomed if you start a conversation.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Rick Lyons wrote:
> Hi Guys,
> 
>   our DSP pal Jon Harris and I have exchanged a few 
> E-mails regarding the Goertzel algorithm.  If you 
> recall, the Geortzel algorithm is implemented with 
> an IIR filter structure with a 2cos(2*pi*k/N) feedback 
> coefficient and an -exp(-j2*pi*k/N) feedforward 
> coefficient.  The value k, which defines the 
> frequency at which the filter resonates, is typically 
> specified to be an integer.  (With k as an integer, 
> the Goertzel algorithm computes the value of a 
> single bin of an N-point DFT.)

I'm unclear why you would think that k should be an integer. I have 
never thought (or constrained) it to be. You can't always optimise N as 
well for a non-integer k, but few real world uses of Geortzel use a 
properly optimised N, for a variety of reasons, anyway. Are you sure k 
should be an integer is a widely held misbelief, or is it just your own?

Regards,
Steve

Rick Lyons wrote:

> 
> Hi Guys,
> 
>   our DSP pal Jon Harris and I have exchanged a few
> E-mails regarding the Goertzel algorithm.  If you
> recall, the Geortzel algorithm is implemented with
> an IIR filter structure with a 2cos(2*pi*k/N) feedback
> coefficient and an -exp(-j2*pi*k/N) feedforward
> coefficient.  The value k, which defines the
> frequency at which the filter resonates, is typically
> specified to be an integer.  (With k as an integer,
> the Goertzel algorithm computes the value of a
> single bin of an N-point DFT.)
>
> Jon pointed out to me that k need not be an integer,
> and that non-integer values of k enhance the Goertzel
> algorithm's spectrum analysis capability because we
> can center our filter at *any* frequency between
> -Fs/2 and +Fs/2. (Not merely at integer multiples
> of Fs/N.)
> SHEECE!!!  Now why in the heck didn't I think of that??

Errm.. I dunno :-)
 
> I did a little MATLAB modeling of this idea, and the
> Goertzel algorithm has the same frequency-domain
> behavior with a non-integer k as with an integer k.
> As far as I can tell, Jon Harris should receive
> official comp.dsp authorization to reach around and
> pat himself on the back.
> 
> Anyway, have any of you guys run across this notion that
> k need not be an integer in the Goertzel algorithm.

Nope, to be honest, I can't say I have.
(Maybe Jon should apply for a patent :-)

Regards
--
Adrian Hey

IIRC, this is done in DTMF decoding algorithms.

Dirk

"Rick Lyons" <ricklyon@REMOVE.onemain.com> wrote in message
news:3f07695a.17445812@news.earthlink.net...
>
> Hi Guys,
>
>   our DSP pal Jon Harris and I have exchanged a few
> E-mails regarding the Goertzel algorithm.  If you
> recall, the Geortzel algorithm is implemented with
> an IIR filter structure with a 2cos(2*pi*k/N) feedback
> coefficient and an -exp(-j2*pi*k/N) feedforward
> coefficient.  The value k, which defines the
> frequency at which the filter resonates, is typically
> specified to be an integer.  (With k as an integer,
> the Goertzel algorithm computes the value of a
> single bin of an N-point DFT.)
>
> Jon pointed out to me that k need not be an integer,
> and that non-integer values of k enhance the Goertzel
> algorithm's spectrum analysis capability because we
> can center our filter at *any* frequency between
> -Fs/2 and +Fs/2. (Not merely at integer multiples
> of Fs/N.)
> SHEECE!!!  Now why in the heck didn't I think of that??
>
> I did a little MATLAB modeling of this idea, and the
> Goertzel algorithm has the same frequency-domain
> behavior with a non-integer k as with an integer k.
> As far as I can tell, Jon Harris should receive
> official comp.dsp authorization to reach around and
> pat himself on the back.
>
> Anyway, have any of you guys run across this notion that
> k need not be an integer in the Goertzel algorithm.
>
> Thanks,
> [-Rick-]
>

"Steve Underwood" <steveu@dis.org> wrote in message
news:be81o6$oem$1@hfc.pacific.net.hk...
> Rick Lyons wrote:
> > Hi Guys,
> >

> I'm unclear why you would think that k should be an integer. I have
> never thought (or constrained) it to be. You can't always optimise N as
> well for a non-integer k, but few real world uses of Geortzel use a
> properly optimised N, for a variety of reasons, anyway. Are you sure k
> should be an integer is a widely held misbelief, or is it just your own?

Hello Steve,
The thought that k should be an integer carrys forward from the notion that
the Goertzel is just another way of calculating the DFT (single bin anyway)
But changing paradigms to it being a filter of course says make k whatever
you want.

Clay

p.s.   Rick, I've seen non integral k used for DTMF decoding even ones that
use Parseval's relation.

>
> Regards,
> Steve
>

Clay S. Turner wrote:
> "Steve Underwood" <steveu@dis.org> wrote in message
> news:be81o6$oem$1@hfc.pacific.net.hk...
> 
>>I'm unclear why you would think that k should be an integer. I have
>>never thought (or constrained) it to be. You can't always optimise N as
>>well for a non-integer k, but few real world uses of Geortzel use a
>>properly optimised N, for a variety of reasons, anyway. Are you sure k
>>should be an integer is a widely held misbelief, or is it just your own?
> 
> Hello Steve,
> The thought that k should be an integer carrys forward from the notion that
> the Goertzel is just another way of calculating the DFT (single bin anyway)
> But changing paradigms to it being a filter of course says make k whatever
> you want.

That makes some sense, but look at the equations - is there anything 
remotely integery about the k? I guess this is one of those not seeing 
the wood for the trees things.

I first met Goertzel in the early TI app note about DTMF. The app note 
was useless as a reference model for a DTMF decoder, as it just didn't 
work anything like to spec. - the basic ideas were good building blocks, 
but the implementation wasn't - and like any good app note the 
description, the code and the comments describe three different 
implementations :-\ I guess having met Goertzel like that, with k freely 
chosen, I never questioned the idea of constraining it.

Regards,
Steve

Steve Underwood <steveu@dis.org> wrote in message news:<be81o6$oem$1@hfc.pacific.net.hk>...
> Rick Lyons wrote:
> > Hi Guys,
> > 
> >   our DSP pal Jon Harris and I have exchanged a few 
> > E-mails regarding the Goertzel algorithm.  If you 
> > recall, the Geortzel algorithm is implemented with 
> > an IIR filter structure with a 2cos(2*pi*k/N) feedback 
> > coefficient and an -exp(-j2*pi*k/N) feedforward 
> > coefficient.  The value k, which defines the 
> > frequency at which the filter resonates, is typically 
> > specified to be an integer.  (With k as an integer, 
> > the Goertzel algorithm computes the value of a 
> > single bin of an N-point DFT.)
> 
> I'm unclear why you would think that k should be an integer. I have 
> never thought (or constrained) it to be. You can't always optimise N as 
> well for a non-integer k, but few real world uses of Geortzel use a 
> properly optimised N, for a variety of reasons, anyway. Are you sure k 
> should be an integer is a widely held misbelief, or is it just your own?
> 
> Regards,
> Steve

I thought of sharing few comments regarding k.
k can be defined by the following formula:
k=fi*N/fs where fi is DTMF tones i.e 697,770,852 Hz etc.,fs is
sampling frequency i.e 8000Hz. and N is DFT points. Typically as
described in [1]
N is chosen as 205.

We get the following table for k values(floating) using the above
formula:

Tone       Floating value      Nearest integer         Absolute error
in Hz       of k                     k


697        17.861                 18                      0.139
770        19.731                 20                      0.269

similarly we can compute all 8 tones. We can also compute relative
error[1].
If Rick considers k as integer he has to accept this error and if N is
optimized to get minimum error then chosing k as integer is no harm
and may not degrade performance.

Regards,
Santosh   


[1] http://ptolemy.eecs.berkeley.edu/papers/96/dtmf_ict/www/node3.html

On Sun, 06 Jul 2003 13:45:06 +0800, Steve Underwood <steveu@dis.org>
wrote:

>Clay S. Turner wrote:
>> "Steve Underwood" <steveu@dis.org> wrote in message
>> news:be81o6$oem$1@hfc.pacific.net.hk...
>> 
>>>I'm unclear why you would think that k should be an integer. I have
>>>never thought (or constrained) it to be. You can't always optimise N as
>>>well for a non-integer k, but few real world uses of Geortzel use a
>>>properly optimised N, for a variety of reasons, anyway. Are you sure k
>>>should be an integer is a widely held misbelief, or is it just your own?
>> 
>> Hello Steve,
>> The thought that k should be an integer carrys forward from the notion that
>> the Goertzel is just another way of calculating the DFT (single bin anyway)
>> But changing paradigms to it being a filter of course says make k whatever
>> you want.
>
>That makes some sense, but look at the equations - is there anything 
>remotely integery about the k? I guess this is one of those not seeing 
>the wood for the trees things.
>
>I first met Goertzel in the early TI app note about DTMF. The app note 
>was useless as a reference model for a DTMF decoder, as it just didn't 
>work anything like to spec. - the basic ideas were good building blocks, 
>but the implementation wasn't - and like any good app note the 
>description, the code and the comments describe three different 
>implementations :-\ I guess having met Goertzel like that, with k freely 
>chosen, I never questioned the idea of constraining it.
>
>Regards,
>Steve

Hi Steve,
    Clay's explanation of my "narrow view" of the values of k is
 correct.  Every Goertzel description I've ever read starts out with:

     "You can use the Goertzel algorithm to compute the 
       k-th bin of an N-point DFT."

And then the author gives the math derivation of how Goertzel 
computes some N-point DFT bin result.
Because the bin indices (k = 0,1,2,3..) for the DFT are integers 
I fell into the trap of thinking k had to be an integer.
But when you look at the equations, and the Goertzel block 
diagram, as you say there's nothing there forcing k to be 
an integer.

Live and learn, huh?
This newsgroup is the greatest!
[-Rick-]

On Sat, 05 Jul 2003 21:46:38 -0400, Jerry Avins <jya@ieee.org> wrote:

  (snipped)
>
>Guys at Rice have massaged Old Man Goertzel pretty well, even showing
>code to run his algorithm on old eight bitters fast enough for telephone
>service. Why not poke around their web site a bit. Surely, you have the
>credentials to be welcomed if you start a conversation.
>
>Jerry

Thanks, I'll check it out.

[-Rick-]