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

# Another Goertzel question

Started by ●July 5, 2003

Reply by ●July 5, 20032003-07-05

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. �����������������������������������������������������������������������

Reply by ●July 5, 20032003-07-05

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

Reply by ●July 6, 20032003-07-06

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

Reply by ●July 6, 20032003-07-06

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

Reply by ●July 6, 20032003-07-06

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

Reply by ●July 6, 20032003-07-06

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

Reply by ●July 6, 20032003-07-06

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, > SteveI 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

Reply by ●July 6, 20032003-07-06

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

Reply by ●July 6, 20032003-07-06

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. > >JerryThanks, I'll check it out. [-Rick-]