Another Goertzel question

Dennis@NoSpam.com wrote in message news:<5j7pgvkoj9637fi7u26f7omischauc0bno@4ax.com>...
> 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


Come to think of it, Goertzel with non-integer k is equivalent to
zero-padding ( with appropriate number of zeros to bring the freq to
the center of a bin of dft ).

[ With zero padding, u are just computing the inner product over
an increased time in which the basis function has an integral number of cycles.
( But this operation is redundant since the signal is anyway zero 
outside the original duration. )  ]

Both should give identical results.

Funny that people were ok with zero padding, but not fractional k.

             shankar

"kbc" <kbc32@yahoo.com> wrote in message
news:a382521e.0307100409.1b886c27@posting.google.com...
> Dennis@NoSpam.com wrote in message
news:<5j7pgvkoj9637fi7u26f7omischauc0bno@4ax.com>...
> > 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
>
>
> Come to think of it, Goertzel with non-integer k is equivalent to
> zero-padding ( with appropriate number of zeros to bring the freq to
> the center of a bin of dft ).
>
> [ With zero padding, u are just computing the inner product over
> an increased time in which the basis function has an integral number of
cycles.
> ( But this operation is redundant since the signal is anyway zero
> outside the original duration. )  ]
>
> Both should give identical results.

Are you sure about that?  I would think that with zero padding, not only
would the bin centers change, but also the bin width.  On the other hand,
with fractional k, the bin center would change but the width would be
constant.  I haven't done any analysis, but that's my intuition.

Anyone else care to comment?

-Jon

On Thu, 10 Jul 2003 18:03:07 -0700, Jon Harris wrote:
> Are you sure about that?  I would think that with zero padding, not only
> would the bin centers change, but also the bin width.  On the other
> hand, with fractional k, the bin center would change but the width would
> be constant.  I haven't done any analysis, but that's my intuition.

I agree with you.  With zero padding, you are increasing the value of N,
and bin width is proportional to N.  Fractional and integral k have the
same N, so the bin width is the same.

-- 
Matthew Donadio (m.p.donadio@ieee.org)

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

dft is related to cyclic convolution due to point b above.  ( I think
this is why people bring in periodic notion. )

> 
> Are you sure about that?  I would think that with zero padding, not only
> would the bin centers change, but also the bin width.  On the other hand,
> with fractional k, the bin center would change but the width would be
> constant.  I haven't done any analysis, but that's my intuition.
> 
> Anyone else care to comment?
> 
> -Jon

The equations  are identical.

Please verify. I have no matlab.

Zero padding might have been suggested only to get the benefit of
using the fft algorithm to speed up.  ( No need to use it if u want
only few interpolated points. )

          shankar

"Jon Harris" <jon_harrisTIGER@hotmail.com> wrote:

>> Come to think of it, Goertzel with non-integer k is equivalent to
>> zero-padding ( with appropriate number of zeros to bring the freq to
>> the center of a bin of dft ).
>>
>> [ With zero padding, u are just computing the inner product over
>> an increased time in which the basis function has an integral number of
>cycles.
>> ( But this operation is redundant since the signal is anyway zero
>> outside the original duration. )  ]
>>
>> Both should give identical results.
>
>Are you sure about that?  I would think that with zero padding, not only
>would the bin centers change, but also the bin width.  On the other hand,
>with fractional k, the bin center would change but the width would be
>constant.  I haven't done any analysis, but that's my intuition.
>
>Anyone else care to comment?

I was only using zero padding as an example of extending the series to an
arbitrary infinite length so the any frequency within the i/N bins can be found
with Goertzel.

With the Goertzel algorithm adding zeros on the end does not change the result
of the frequency magnitude.  If you don't believe me try it.  Add 100 zeros on
the end of your data and Goertzel will produce the exact same frequency
magnitude.  With this in mind, then you could imagine adding millions of zeros
on the end of the series and find any almost non-integer frequency  between the
i/N bins.  Since the frequency magnitude is the same whether you pad zeros to
the end or not, the non-integer frequency is proved.

What about that?

Dennis

> 
> With the Goertzel algorithm adding zeros on the end does not change the result
> of the frequency magnitude.  If you don't believe me try it.  Add 100 zeros on
> the end of your data and Goertzel will produce the exact same frequency
> magnitude.  With this in mind, then you could imagine adding millions of zeros
> on the end of the series and find any almost non-integer frequency  between the
> i/N bins.  Since the frequency magnitude is the same whether you pad zeros to
> the end or not, the non-integer frequency is proved.
> 
> What about that?
> 
> Dennis

Actually , the whole thing is as trivial as saying that :

(x,y) = (a,b)
(,) is inner product

a = [x,  zeros(1,N)]
b = [y,  z]
z is any vector of size N

On Tue, 08 Jul 2003 16:45:31 -0500, Dennis@NoSpam.com wrote:

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

Hi Dennis,
  I haven't checked any old posts to see if you're right 
about this, but I have no reason to believe you're 
wrong.  If you did point this idea, I wasn't paying enough 
attention, and I aplogize.  I now formally convey upon you 
the official 'comp.dsp authorization' to 
pat yourself on the back.

By the way, we don't refer to me (Rick) as an 
"old boy".  I'm the old fart.  (But not as old as 
Jerry Avins.  Jerry knew Abraham Lincoln personally.)
:-)     :-)   :-)


Thanks Dennis,
[-Rick-]

ricklyon@REMOVE.onemain.com (Rick Lyons) wrote:

>I now formally convey upon you 
>the official 'comp.dsp authorization' to 
>pat yourself on the back.

Well the short history is I posted a question on this ng about an easy way to
determine amplitudes and phases of unevenly spaced frequencies other than the
Burg(MESA) algorithm.  You guys said Goertzel, but only at the bin centers.
After much computing with Goertzel I came back that Goertzel can find any
frequency within the fs/2 band. You guys said nope. Then I discovered that the
Goertzel phase was incorrect if not at a bin center and pointed out the
Bonzanigo phase correction. You guys said nope.  

I decline the official 'comp.dsp' pat myself on the back award but appreciate
and enjoy the back and forth correspondence and helpfulness of this ng.

>By the way, we don't refer to me (Rick) as an 
>"old boy".  I'm the old fart.  (But not as old as 
>Jerry Avins.  Jerry knew Abraham Lincoln personally.)

I formally apologize for calling anyone on the dsp ng an "Old Boy".  Perhaps I
should have said  "the dsp gang network heh?" :-)

Dennis

On Sun, 13 Jul 2003 16:39:41 -0500, Dennis@NoSpam.com wrote:

>ricklyon@REMOVE.onemain.com (Rick Lyons) wrote:
>
>>I now formally convey upon you 
>>the official 'comp.dsp authorization' to 
>>pat yourself on the back.
>
>Well the short history is I posted a question on this ng about an easy way to
>determine amplitudes and phases of unevenly spaced frequencies other than the
>Burg(MESA) algorithm.  You guys said Goertzel, but only at the bin centers.
>After much computing with Goertzel I came back that Goertzel can find any
>frequency within the fs/2 band. You guys said nope. Then I discovered that the
>Goertzel phase was incorrect if not at a bin center and pointed out the
>Bonzanigo phase correction. You guys said nope.  
>
>I decline the official 'comp.dsp' pat myself on the back award but appreciate
>and enjoy the back and forth correspondence and helpfulness of this ng.
>
>>By the way, we don't refer to me (Rick) as an 
>>"old boy".  I'm the old fart.  (But not as old as 
>>Jerry Avins.  Jerry knew Abraham Lincoln personally.)
>
>I formally apologize for calling anyone on the dsp ng an "Old Boy".  Perhaps I
>should have said  "the dsp gang network heh?" :-)
>
>Dennis

Dennis,

It sounds to me like you're engaging in the time-tested practice of
generalizing attributions.  I don't know who this "dsp gang network"
or "you guys" are, but internet newsgroups are collections of
individuals (well, usually, this one certainly is, anyway).  My
recollections of the threads you mention above certainly don't come to
the conclusion of "you guys said nope."  e.g., You brought up the
correction thing and demonstrated that it can be useful, from what I
could see.  Other opinions may differ, which is the whole point, I
think.

Try not to fall into the trap of attributing a particular opinion to
some imagined organized block of contributors here, because such a
thing does not exist.


Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org