Forums

Another Goertzel question

Started by Rick Lyons 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. �����������������������������������������������������������������������
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-]