Another Goertzel question

Started by July 5, 2003
```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.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```
```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
--

```
```IIRC, this is done in DTMF decoding algorithms.

Dirk

"Rick Lyons" <ricklyon@REMOVE.onemain.com> wrote in message
>
> 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

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-]

```