On Sun, 06 Jul 2003 12:31:18 GMT, ricklyon@REMOVE.onemain.com (Rick Lyons) wrote:>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-]Rick, all, Sorry to be coming into this late... Usually Goertzel's algorithm is used as a shortcut to simplify computation of DFT bins of interest, so the identified conceptual relationship to DFTs does tend to get in the way sometimes. Realize, though, that even for DFTs the indices are integers to maintain orthogonality wrt the reference functions, but if one wants to interpolate in the frequency domain with a DFT then k doesn't have to be an integer there, either. As Steve pointed out the Goertzel algorithm does have some flexibility in matching k and N to achieve the desired output. The sliding-window DFT bins can be adjusted similarly. As usual, as long as one keeps track of what they're doing many things are possible, but there may be tradeoffs. Wasn't there an article about such things in a recent SP Mag? BTW, Rick, congratulations on becoming an IEEE Fellow! ...didja think we wouldn't notice? ;) Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
Another Goertzel question
Started by ●July 5, 2003
Reply by ●July 7, 20032003-07-07
Reply by ●July 7, 20032003-07-07
On Mon, 07 Jul 2003 06:25:53 GMT, eric.jacobsen@ieee.org (Eric Jacobsen) wrote: (snipped)>> >>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-] > > >Rick, all, > >Sorry to be coming into this late... > >Usually Goertzel's algorithm is used as a shortcut to simplify >computation of DFT bins of interest, so the identified conceptual >relationship to DFTs does tend to get in the way sometimes. > >Realize, though, that even for DFTs the indices are integers to >maintain orthogonality wrt the reference functions, but if one wants >to interpolate in the frequency domain with a DFT then k doesn't have >to be an integer there, either. As Steve pointed out the Goertzel >algorithm does have some flexibility in matching k and N to achieve >the desired output. > >The sliding-window DFT bins can be adjusted similarly. As usual, as >long as one keeps track of what they're doing many things are >possible, but there may be tradeoffs. > >Wasn't there an article about such things in a recent SP Mag? > >BTW, Rick, congratulations on becoming an IEEE Fellow! > >...didja think we wouldn't notice? ;) >Hi Eric, thanks for the nice words, but I have no idea what you're referring to. (Sorry for the poor grammar.) Is it possible that you have me mixed up with some other 'Lyons'? Humm, I wonder how I can check this out. Thanks, [-Rick-]
Reply by ●July 7, 20032003-07-07
Rick Lyons wrote:> > "You can use the Goertzel algorithm to compute the > k-th bin of an N-point DFT."Yup. ADI's DTMF decoding app note also indicates that k should be an integer, and they spent a fair amount of space showing how you could choose N such that k is an integer but minimize the frequency error. In reality, N affects the bandwidth of the "bin" so there's not really that much freedom to play around with it. About the third or fourth time I implemented this (when I had to account for a variety of possible sample rates), I asked myself the same question - why should k be an integer? Finding no reason, I abandoned the conventional wisdom, and the resulting DTMF decoder worked great. -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (703) 779-7770 Getting an inch of snow is like winning ten cents in the lottery - Calvin
Reply by ●July 7, 20032003-07-07
ricklyon@REMOVE.onemain.com (Rick Lyons) wrote in news:3f092dd4.11305359 @news.earthlink.net:> On Mon, 07 Jul 2003 06:25:53 GMT, eric.jacobsen@ieee.org (Eric > Jacobsen) wrote: > > (snipped) >>> >>>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-] >> >> >>Rick, all, >> >>Sorry to be coming into this late... >> >>Usually Goertzel's algorithm is used as a shortcut to simplify >>computation of DFT bins of interest, so the identified conceptual >>relationship to DFTs does tend to get in the way sometimes. >> >>Realize, though, that even for DFTs the indices are integers to >>maintain orthogonality wrt the reference functions, but if one wants >>to interpolate in the frequency domain with a DFT then k doesn't have >>to be an integer there, either. As Steve pointed out the Goertzel >>algorithm does have some flexibility in matching k and N to achieve >>the desired output. >> >>The sliding-window DFT bins can be adjusted similarly. As usual, as >>long as one keeps track of what they're doing many things are >>possible, but there may be tradeoffs. >> >>Wasn't there an article about such things in a recent SP Mag? >> >>BTW, Rick, congratulations on becoming an IEEE Fellow! >> >>...didja think we wouldn't notice? ;) >> > > Hi Eric, > thanks for the nice words, but I have no idea what you're > referring to. (Sorry for the poor grammar.) > Is it possible that you have me mixed up with some > other 'Lyons'? > > Humm, I wonder how I can check this out. > > Thanks, > [-Rick-] > >The IEEE award in question went to Richard Lyon (not Lyons). I'm sure our Rick deserves some kind of award as well, maybe next time..... -- Al Clark Danville Signal Processing, Inc. -------------------------------------------------------------------- Purveyors of Fine DSP Hardware and other Cool Stuff Available at http://www.danvillesignal.com
Reply by ●July 7, 20032003-07-07
On Mon, 07 Jul 2003 16:26:57 GMT, Al Clark <dsp@danvillesignal.com> wrote:>ricklyon@REMOVE.onemain.com (Rick Lyons) wrote in news:3f092dd4.11305359 >@news.earthlink.net: > >> On Mon, 07 Jul 2003 06:25:53 GMT, eric.jacobsen@ieee.org (Eric >> Jacobsen) wrote: >> >> (snipped) >>>> >>>>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-] >>> >>> >>>Rick, all, >>> >>>Sorry to be coming into this late... >>> >>>Usually Goertzel's algorithm is used as a shortcut to simplify >>>computation of DFT bins of interest, so the identified conceptual >>>relationship to DFTs does tend to get in the way sometimes. >>> >>>Realize, though, that even for DFTs the indices are integers to >>>maintain orthogonality wrt the reference functions, but if one wants >>>to interpolate in the frequency domain with a DFT then k doesn't have >>>to be an integer there, either. As Steve pointed out the Goertzel >>>algorithm does have some flexibility in matching k and N to achieve >>>the desired output. >>> >>>The sliding-window DFT bins can be adjusted similarly. As usual, as >>>long as one keeps track of what they're doing many things are >>>possible, but there may be tradeoffs. >>> >>>Wasn't there an article about such things in a recent SP Mag? >>> >>>BTW, Rick, congratulations on becoming an IEEE Fellow! >>> >>>...didja think we wouldn't notice? ;) >>> >> >> Hi Eric, >> thanks for the nice words, but I have no idea what you're >> referring to. (Sorry for the poor grammar.) >> Is it possible that you have me mixed up with some >> other 'Lyons'? >> >> Humm, I wonder how I can check this out. >> >> Thanks, >> [-Rick-] >> >> > >The IEEE award in question went to Richard Lyon (not Lyons). I'm sure our >Rick deserves some kind of award as well, maybe next time.....Ack! It's not the same guy!? My apologies. This means that there are two of them loose out there doing nearly the same things! Whoulda thot... Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
Reply by ●July 7, 20032003-07-07
"Jim Thomas" <jthomas@bittware.com> wrote in message news:3F097A52.6E2CEFEC@bittware.com...> Rick Lyons wrote: > > > > "You can use the Goertzel algorithm to compute the > > k-th bin of an N-point DFT." > > Yup. ADI's DTMF decoding app note also indicates that k should be an > integer, and they spent a fair amount of space showing how you could > choose N such that k is an integer but minimize the frequency error.I think app note contributes considerably to the "k must be integer" misconception. Since they go to such great lengths to pick just the right N so that k is close to an integer for all frequencies of interest, one assumes that k must be an integer. They even go so far as to use slightly different N's for the fundamental vs. the 2nd harmonic. It's a bit of a shame because other than that issue, it is an excellent article, very easy to read and understand.> In reality, N affects the bandwidth of the "bin" so there's not really > that much freedom to play around with it.Correct, but at least you don't have to worry about picking a certain "magic" value. You just need a value that gives you the ball-park correct bin width.> About the third or fourth time I implemented this (when I had to account > for a variety of possible sample rates), I asked myself the same > question - why should k be an integer? Finding no reason, I abandoned > the conventional wisdom, and the resulting DTMF decoder worked great.So far, I'm only on my first!> -- > Jim Thomas Principal Applications Engineer Bittware, Inc > jthomas@bittware.com http://www.bittware.com (703) 779-7770 > Getting an inch of snow is like winning ten cents in the lottery - > Calvin
Reply by ●July 8, 20032003-07-08
Hey Rick no fair. This was the exact same thing I was pointing out in my dsp posts back in 3/3/2003 to 3/8/2003. At that time all you guys were poo-pooing me. Now you want to give hero status for the same thing to Jon Harris. The old boy network Heh? Dennis ricklyon@REMOVE.onemain.com (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-]
Reply by ●July 9, 20032003-07-09
Dennis@NoSpam.com wrote in message news:<aremgvs5p4q751m1bsvifnndp9dv9vk2ki@4ax.com>...> Hey Rick no fair. > > This was the exact same thing I was pointing out in my dsp posts back in > 3/3/2003 to 3/8/2003. > At that time all you guys were poo-pooing me. Now you want to give hero status > for the same thing to Jon Harris. > > The old boy network Heh? > > Dennis >Maybe 2 points need to be stressed regarding dft. 1) The equation for dft is actually no different from that of analog fourier tm. It is in terms of an integral. Specifically, the basis functions of dft are actually ANALOG complex exponentials. ( The integral reduces to a summation since the signal analysed is discrete-time. ) 2) The time-limits in above integral is really [-inf, inf]. Because, this is the range in which the basis functions are defined. Any two exponentials of different frequency are orthogonal over this range. (does somebody know how to prove this ?) 3) The dft gives exact samples of spectrum if a. The signal analysed is zero outside the range analysed and nyquist criteria is metin sampling ( i know time-limited is not bandlimited :=) ) OR b. The signal analysed is originally discrete-time and periodic. ( ie , we did not do any sampling of the signal. ) There is no sense in making k a non-integer in Goertzel if you know that the original signal is periodic. (This should open the eyes of those who always bring in some periodic assumption of analysed signal. ) ( When computing a fourier series, you have to make use of the fact that only fundamental and harmonics are present. ) Of course, dft can be viewed entirely in a linear algebraic setting. Here, dft defines an orthogonal basis. Using non-integer k will amount to using basis vectors which are not orthogonal. ( Will such a basis span the vector space ? ) Assuming that we multiplied the original signal by a rect window and then took dft and goertzel ( for non-bin values ), i am wondering whether the bin-values will be more accurate than non-bin values. (there would be spectral leakage. ) Please correct me if i am wrong. shankar
Reply by ●July 9, 20032003-07-09
How about zero padding - heh? Essentially you can make the time series as long as you want by adding zeros on the end (assuming you have taken the mean out if there is one and etc). Thus any frequency can be found by Goertzel at or between the i/N's. With Goertzel I can find frequency k/M where M>>N and N is the number of data points because I've appended M-N zeros. Goerzel provides almost perfect interpolation. Dennis> >Maybe 2 points need to be stressed regarding dft. > >1) The equation for dft is actually no different from that of analog >fourier tm. It is in terms of an integral. Specifically, the basis >functions of dft are actually ANALOG complex exponentials. ( The >integral reduces to a summation since the signal analysed is >discrete-time. ) > >2) The time-limits in above integral is really [-inf, inf]. Because, >this is the range in which the basis functions are defined. Any two >exponentials of different frequency are orthogonal over this range. >(does somebody know how to prove this ?) > >3) The dft gives exact samples of spectrum if > >a. The signal analysed is zero outside the range analysed and nyquist >criteria is metin sampling ( i know time-limited is not bandlimited >:=) ) OR > >b. The signal analysed is originally discrete-time and periodic. ( ie >, we did not do any sampling of the signal. ) > > >There is no sense in making k a non-integer in Goertzel if you know >that the original signal is periodic. (This should open the eyes of >those who always bring in some periodic assumption of analysed signal. >) ( When computing a fourier series, you have to make use of the fact >that only fundamental and harmonics are present. ) > > >Of course, dft can be viewed entirely in a linear algebraic setting. >Here, dft >defines an orthogonal basis. Using non-integer k will amount to using >basis vectors which are not orthogonal. ( Will such a basis span the >vector space ? ) > >Assuming that we multiplied the original signal by a rect window and >then took dft and goertzel ( for non-bin values ), i am wondering >whether the bin-values will be more accurate than non-bin values. >(there would be spectral leakage. ) > >Please correct me if i am wrong. > > shankar
Reply by ●July 9, 20032003-07-09
<Dennis@NoSpam.com> wrote in message news:aremgvs5p4q751m1bsvifnndp9dv9vk2ki@4ax.com...> Hey Rick no fair. > > This was the exact same thing I was pointing out in my dsp posts back in > 3/3/2003 to 3/8/2003. > At that time all you guys were poo-pooing me. Now you want to give herostatus> for the same thing to Jon Harris. > > The old boy network Heh?Who you callin' old? :-) I'm no hero, I found the info in an even older comp.dsp post from 1996. -Jon (recently turned 30)> Dennis > > ricklyon@REMOVE.onemain.com (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-] >
