> Date: Mon, 29 Oct 2001 10:48:22 -0800
> From: Bob Cain <arcane@arca...>
> 
> Sorry to send this to you twice, Akshay, but once again I expected
> "Reply" to go to the list like it does with other lists and with
> usenet.  Can that be fixed or is it an unchangable yahooism?
> 
> Akshay Joshi wrote:
> > 
> > Bob,
> > 
> > It is more to do with how you define "increased resolution"
> > 
> > > While it is usually stated in the time domain the sampling
theorem
> > > applies equally to the frequency domain.
> > 
> > Exactly.  If we zero pad the FFT (by adding zeros from pi/2 to -pi/2
.. )
> > ..and obtain the time domain signal .., we get the upsampled the time
domain
> > signal.. but between two adjacent samples, we are interpolating... if
that's
> > what you call increasing the resolution, we agree.
> 
> Yep.  We agree.  I think that what we are agreeing on is what people
> generally want when they ask if they can get increased resolution by
> zero extension.

Dear both,

Since one of the previous emails (of Bob) referred to my email, I'd like
to add that I also meant interpolation (as I stated in one of my previous
emails to this list) is the result of zero-padding. So we agree if
we would call interpolation as increasing the resolution. 

I am sorry Bob that I did not resend my replys to your emails on that
last Friday (or when it was) -- I was reall in a hurry to do something.

Regards,
Andrew

> 
> 
> Bob
> -- 
> 
> "Things should be described as simply as possible, but no
simpler."
> 
>                                              A. Einstein
> 
>

Sorry to send this to you twice, Akshay, but once again I expected
"Reply" to go to the list like it does with other lists and with
usenet.  Can that be fixed or is it an unchangable yahooism?

Akshay Joshi wrote:
> 
> Bob,
> 
> It is more to do with how you define "increased resolution"
> 
> > While it is usually stated in the time domain the sampling theorem
> > applies equally to the frequency domain.
> 
> Exactly.  If we zero pad the FFT (by adding zeros from pi/2 to -pi/2 .. )
> ..and obtain the time domain signal .., we get the upsampled the time
domain
> signal.. but between two adjacent samples, we are interpolating... if
that's
> what you call increasing the resolution, we agree.

Yep.  We agree.  I think that what we are agreeing on is what people
generally want when they ask if they can get increased resolution by
zero extension.
	Bob
-- 

"Things should be described as simply as possible, but no simpler."

                                             A. Einstein
	////////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

 To contribute your unused processor cycles to the fight against cancer:

     http://www.intel.com/cure

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\///////////////////////////////////////

Bob,

It is more to do with how you define "increased resolution"

> While it is usually stated in the time domain the
sampling theorem
> applies equally to the frequency domain.

Exactly.  If we zero pad the FFT (by adding zeros from pi/2 to -pi/2 .. )
..and obtain the time domain signal .., we get the upsampled the time domain
signal.. but between two adjacent samples, we are interpolating... if
that's
what you call increasing the resolution, we agree.

-Akshay.

----- Original Message -----
From: Bob Cain <arcane@arca...>
To: <audiodsp@audi...>
Sent: Saturday, October 27, 2001 1:53 AM
Subject: Re: [audiodsp] Re: zeroing the FFT
	> "Andrew V. Nesterov" wrote:
> >
> >
> > yes, since adding a bunch of zeroes does not add additional
> > information to the sampled signal, thus zero padding would
> > not increase frequency resolution.
>
> What do you mean then by resolution?  If it covers the same space with
> more samples of it is this not increased resolution?  The sampling
> theorem shows how to determine any value between samples exactly by sinc
> interpolation when the sampled function is band limited by the Nyquist
> criterion.  That the new information which comes from zero padding is
> redundant when it comes to reconstructing the function does not negate
> the validity of the new information.
>
> While it is usually stated in the time domain the sampling theorem
> applies equally to the frequency domain.
>
> Bob
> --
>
> "Things should be described as simply as possible, but no
simpler."
>
>                                              A. Einstein
>
>
>
////////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\\\
>
>  To contribute your unused processor cycles to the fight against cancer:
>
>      http://www.intel.com/cure
>
>
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\////////////////////////////////////
///
>
>
>
> _____________________________________
> Note: If you do a simple "reply" with your email client, only the
author
of this message will receive your answer.  You need to do a "reply
all" if
you want your answer to be distributed to the entire group.
>
> _____________________________________
> About this discussion group:
>
> To Join:  audiodsp-subscribe@audi...
>
> To Post:  audiodsp@audi...
>
> To Leave: audiodsp-unsubscribe@audi...
>
> Archives: http://groups.yahoo.com/group/audiodsp
>
> Other DSP-Related Groups: http://www.dsprelated.com
>
>
> ">http://docs.yahoo.com/info/terms/
>
>

Jeff,

> Do you know of a DSP-friendly (i.e. real-time)
technique that can be used
to
> resolve your mixed your example?

It is impossible, to resolve them. .. without making assumptions on the
nature of signal.

-Akshay

----- Original Message -----
From: Jeff Brower <jbrower@jbro...>
To: Akshay Joshi <ajoshi@ajos...>
Cc: <audiodsp@audi...>; Tony Zampini <tony@tony...>; Suciu
Radu <radusuciu@radu...>; Michael Strothjohann
<strothjohann@stro...>
Sent: Sunday, October 28, 2001 10:31 PM
Subject: Re: [audiodsp] zeroing the FFT
	> Akshay-
>
> >    It should be a signal, which has been mixed, i.e C = A + B, where
you
> >would want to resolve A and B. The point is to resolve two mixed
signals
and
> >*not* take FFT of two signals separately and
demonstrate the shift on a
> >plot.
> >    You can't resolve A and B components by padding any number of
zeros
to
> >the FFT of C.
>
> In the example you gave, if you add the sinusoids together as you indicate
> (later but not in the original example), no length of FFT will allow the
> sinusoids to be resolved.  There is not enough time history data.  Either
more
> time data has to be provided, or a non-FFT
technique has to be used, for
example
> a phase shift detection, interpolated FFT, maximum
entropy, etc.
>
> Do you know of a DSP-friendly (i.e. real-time) technique that can be used
to
> resolve your mixed your example?
>
> Jeff Brower
> DSP sw/hw engineer
> Signalogic
>
>
> >----- Original Message -----
> >From: Jeff Brower <jbrower@jbro...>
> >To: Akshay Joshi <ajoshi@ajos...>
> >Cc: <audiodsp@audi...>; Tony Zampini <tony@tony...>; Suciu
> >Radu <radusuciu@radu...>; Michael Strothjohann
> ><strothjohann@stro...>
> >Sent: Thursday, October 25, 2001 7:14 AM
> >Subject: Re: [audiodsp] zeroing the FFT
> >
> >
> >> Akshay-
> >>
> >> On Wed, 24 Oct 2001, "Akshay Joshi"
<ajoshi@ajos...> wrote:
> >> >Jeff,
> >> >    Tony has explained this. Adding zeros does not increase
the
> >resolution.
> >> >It merely reduces the spacing between two frequency bins. If
you have
two
> >> >sinusoids
> >> >A = sin(2*pi*i/16) and B = sin(2*pi*i*255/4096). You
can't resolve
them
> >with
> >> >64 point data. You won't resolve them by taking a 4096 pt
FFT by
padding
> >> >zeros over 64 point data.
> >>
> >> Absolutely, completely, 100% wrong.
> >>
> >> Click here to see plots:
> >>
> >>   http://www.signalogic.com/sine.htm
> >>
> >> Sinea is your A above, sineb is your B.  Clearly they cannot be
resolved
> >with a
> >> 64 pt. FFT, and just as clearly they can with 4096 pt. FFT.  Input
data
is
> >the
> >> same in each case -- except the 64 pt. FFT has none of those pesky
zeros,
> >and
> >> the 4096 pt. FFT has 4032 of them.
> >>
> >> I have no idea why you think making the FFT longer and adding
zeros
will
> >not
> >> increase resolution and help resolve frequency domain detail.  Any
> >discrete,
> >> finite Fourier transform is an approximation of the continuous
transform;
> >if you
> >> make it longer the approximation improves.
> >>
> >> >    Padding zeros is not useless. For taking FFT of radix 2
and so on,
it
> >is
> >> >most convenient for computation speed.. you know all about it,
but
there
> >> >should be no confusion. On a 900 pt
data, you don't get more
resolution
> >out
> >> >of 4096 pt FFT than a 1024 point FFT.
> >> >
> >> >    Padding zeros is effective method to get a frequency
response of
say
> >an
> >> >FIR filter. It anyway has zeros at the tail.. so, this is the
best
place,
> >> >where you can actually say that
padding zeros "improves" resolution.
> >>
> >> The frequency response of an FIR filter can be calculated many
ways;
its
> >use as
> >> an FFT example is irrelevant.  The fundamental use for FFTs is on
real
> >world
> >> input data that needs to be analyzed.  Zero padding -- and every
other
key
> >FFT
> >> technique -- applies to that, not FIR filters.
> >>
> >> Jeff Brower
> >> Signalogic

Akshay-

>    It should be a signal, which has been mixed,
i.e C = A + B, where you
>would want to resolve A and B. The point is to resolve two mixed signals and
>*not* take FFT of two signals separately and demonstrate the shift on a
>plot.
>    You can't resolve A and B components by padding any number of zeros
to
>the FFT of C.

In the example you gave, if you add the sinusoids together as you indicate 
(later but not in the original example), no length of FFT will allow the 
sinusoids to be resolved.  There is not enough time history data.  Either more 
time data has to be provided, or a non-FFT technique has to be used, for example

a phase shift detection, interpolated FFT, maximum entropy, etc.

Do you know of a DSP-friendly (i.e. real-time) technique that can be used to 
resolve your mixed your example?

Jeff Brower
DSP sw/hw engineer
Signalogic
	>----- Original Message -----
>From: Jeff Brower <jbrower@jbro...>
>To: Akshay Joshi <ajoshi@ajos...>
>Cc: <audiodsp@audi...>; Tony Zampini <tony@tony...>; Suciu
>Radu <radusuciu@radu...>; Michael Strothjohann
><strothjohann@stro...>
>Sent: Thursday, October 25, 2001 7:14 AM
>Subject: Re: [audiodsp] zeroing the FFT
>
>
>> Akshay-
>>
>> On Wed, 24 Oct 2001, "Akshay Joshi" <ajoshi@ajos...>
wrote:
>> >Jeff,
>> >    Tony has explained this. Adding zeros does not increase the
>resolution.
>> >It merely reduces the spacing between two frequency bins. If you
have two
>> >sinusoids
>> >A = sin(2*pi*i/16) and B = sin(2*pi*i*255/4096). You can't
resolve them
>with
>> >64 point data. You won't resolve them by taking a 4096 pt FFT
by padding
>> >zeros over 64 point data.
>>
>> Absolutely, completely, 100% wrong.
>>
>> Click here to see plots:
>>
>>   http://www.signalogic.com/sine.htm
>>
>> Sinea is your A above, sineb is your B.  Clearly they cannot be
resolved
>with a
>> 64 pt. FFT, and just as clearly they can with 4096 pt. FFT.  Input data
is
>the
>> same in each case -- except the 64 pt. FFT has none of those pesky
zeros,
>and
>> the 4096 pt. FFT has 4032 of them.
>>
>> I have no idea why you think making the FFT longer and adding zeros
will
>not
>> increase resolution and help resolve frequency domain detail.  Any
>discrete,
>> finite Fourier transform is an approximation of the continuous
transform;
>if you
>> make it longer the approximation improves.
>>
>> >    Padding zeros is not useless. For taking FFT of radix 2 and so
on, it
>is
>> >most convenient for computation speed.. you know all about it, but
there
>> >should be no confusion. On a 900 pt data, you don't get more
resolution
>out
>> >of 4096 pt FFT than a 1024 point FFT.
>> >
>> >    Padding zeros is effective method to get a frequency response
of say
>an
>> >FIR filter. It anyway has zeros at the tail.. so, this is the best
place,
>> >where you can actually say that padding zeros "improves"
resolution.
>>
>> The frequency response of an FIR filter can be calculated many ways;
its
>use as
>> an FFT example is irrelevant.  The fundamental use for FFTs is on real
>world
>> input data that needs to be analyzed.  Zero padding -- and every other
key
>FFT
>> technique -- applies to that, not FIR filters.
>>
>> Jeff Brower
>> Signalogic

"Andrew V. Nesterov" wrote:
> 
> 
> yes, since adding a bunch of zeroes does not add additional
> information to the sampled signal, thus zero padding would
> not increase frequency resolution.

What do you mean then by resolution?  If it covers the same space with
more samples of it is this not increased resolution?  The sampling
theorem shows how to determine any value between samples exactly by sinc
interpolation when the sampled function is band limited by the Nyquist
criterion.  That the new information which comes from zero padding is
redundant when it comes to reconstructing the function does not negate
the validity of the new information. 

While it is usually stated in the time domain the sampling theorem
applies equally to the frequency domain.

Bob
-- 

"Things should be described as simply as possible, but no simpler."

                                             A. Einstein
	////////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

 To contribute your unused processor cycles to the fight against cancer:

     http://www.intel.com/cure

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\///////////////////////////////////////

Jeff, Michael, Tony:

On 24 Oct 2001 audiodsp@audi... wrote:

>    Date: Wed, 24 Oct 2001 09:40:51 -0400
>    From: "Tony Zampini" <tony@tony...>
> 
> On the first issue, I was trying to say that by zero padding,
> you end up with a finer resolution of your bin spacing.
> In other words, the resulting frequency spectrum is
> sampled at more closely spaced points. To put it yet another way,
> the frequency bins are more closely spaced in frequency.

Zero-padding in time domain results in harmonic interpolation in
frequency domain. Frequency bins are closer to each other, and

> Although my words seem to indicate, I did NOT MEAN
to imply
> that, for example, zero-padding would allow you to better
> resolve two closely spaced sinusoids.

yes, since adding a bunch of zeroes does not add additional
information to the sampled signal, thus zero padding would
not increase frequency resolution.

This is what any interpolation process would do, more closely
spaced table, the same information about original signal (spectrum).

> Regards,
> Tony

> Date: Wed, 24 Oct 2001 14:13:49 GMT
> From: Jeff Brower <jbrower@jbro...>
> 
> >Although my words seem to indicate, I did NOT MEAN to imply
> >that, for example, zero-padding would allow you to better
> >resolve two closely spaced sinusoids.
> 
> Why not?  If the time data was sampled often enough then what else can
> you do?  The sinusoids either have the same frequency or they do not.
> A continuous Fourier transform would allow you to distinguish, so a
> finite FFT transform of sufficient length would also allow you to
> distinguish.

Correct, but you have to sample the signal at enough rate to resolve
close frequencies. Zero padding does not resolve them.

> Jeff Brower
> DSP sw/hw engineer
> Signalogic
> 

Regards,
Andrew

Michael-

>Your plots don't address the issue here. 
Generate a signal with two sine 
>waves close together in frequency.  Take a 64 sample block, a 64 sample 
>block zero-padded to 4096 and a 4096 sample block, and plot these signals 
>to see the difference.

They exactly address the issue.  Given the two 64 pt. blocks of data as 
described by Akshay, if the FFT was not lengthened and zeros added, the two 
sinusoids could not be resolved.

Stretching the two time samples to 4096 pts. and using 4096 pt. FFTs allows the 
sinusoids to be resolved without further processing; I'm not sure what that
adds 
to the discussion except possibly to demonstrate in another way that 4k FFT 
length is enough to resolve this particular example.

Jeff Brower
DSP sw/hw engineer
Signalogic

Akshay-

On Wed, 24 Oct 2001, "Akshay Joshi"
<ajoshi@ajos...> wrote:
>Jeff,
>    Tony has explained this. Adding zeros does not increase the resolution.
>It merely reduces the spacing between two frequency bins. If you have two
>sinusoids
>A = sin(2*pi*i/16) and B = sin(2*pi*i*255/4096). You can't resolve them
with
>64 point data. You won't resolve them by taking a 4096 pt FFT by
padding
>zeros over 64 point data.

Absolutely, completely, 100% wrong.

Click here to see plots:

  http://www.signalogic.com/sine.htm

Sinea is your A above, sineb is your B.  Clearly they cannot be resolved with a 
64 pt. FFT, and just as clearly they can with 4096 pt. FFT.  Input data is the 
same in each case -- except the 64 pt. FFT has none of those pesky zeros, and 
the 4096 pt. FFT has 4032 of them.

I have no idea why you think making the FFT longer and adding zeros will not 
increase resolution and help resolve frequency domain detail.  Any discrete, 
finite Fourier transform is an approximation of the continuous transform; if you

make it longer the approximation improves.

>    Padding zeros is not useless. For taking FFT of
radix 2 and so on, it is
>most convenient for computation speed.. you know all about it, but there
>should be no confusion. On a 900 pt data, you don't get more resolution
out
>of 4096 pt FFT than a 1024 point FFT.
>
>    Padding zeros is effective method to get a frequency response of say an
>FIR filter. It anyway has zeros at the tail.. so, this is the best place,
>where you can actually say that padding zeros "improves"
resolution.

The frequency response of an FIR filter can be calculated many ways; its use as 
an FFT example is irrelevant.  The fundamental use for FFTs is on real world 
input data that needs to be analyzed.  Zero padding -- and every other key FFT 
technique -- applies to that, not FIR filters.

Jeff Brower
Signalogic
	>----- Original Message -----
>From: Jeff Brower <jbrower@jbro...>
>To: Akshay Joshi <ajoshi@ajos...>
>Cc: <audiodsp@audi...>; Tony Zampini <tony@tony...>; Suciu
>Radu <radusuciu@radu...>; Michael Strothjohann
><strothjohann@stro...>
>Sent: Wednesday, October 24, 2001 8:58 PM
>Subject: Re: [audiodsp] zeroing the FFT
>
>
>> Akshay-
>>
>> >    I think there is some confusion. Basically Toni and Michael are
>right.
>> >You don't resolve any further. Given a window of data, you
dont resolve
>any
>> >further by padding zeros.
>>
>> Adding zeros = increasing the FFT length, which increases resolution --
>you can
>> see more detail.  Why else would you do it?
>>
>> Jeff Brower
>> DSP sw/hw engineer
>> Signalogic
>>
>>
>> >----- Original Message -----
>> >From: Jeff Brower <jbrower@jbro...>
>> >To: Tony Zampini <tony@tony...>
>> >Cc: <audiodsp@audi...>; Suciu Radu <radusuciu@radu...>;
>Michael
>> >Strothjohann <strothjohann@stro...>
>> >Sent: Wednesday, October 24, 2001 7:43 PM
>> >Subject: Re: [audiodsp] zeroing the FFT
>> >
>> >
>> >> Tony-
>> >>
>> >> >On the first issue, I was trying to say that by zero
padding,
>> >> >you end up with a finer resolution of your bin spacing.
>> >> >In other words, the resulting frequency spectrum is
>> >> >sampled at more closely spaced points. To put it yet
another way,
>> >> >the frequency bins are more closely spaced in frequency.
>> >> >Although my words seem to indicate, I did NOT MEAN to
imply
>> >> >that, for example, zero-padding would allow you to better
>> >> >resolve two closely spaced sinusoids.
>> >>
>> >> Why not?  If the time data was sampled often enough then what
else can
>you
>> >do?
>> >> The sinusoids either have the same frequency or they do not. 
A
>continuous
>> >> Fourier transform would allow you to distinguish, so a finite
FFT
>> >transform of
>> >> sufficient length would also allow you to distinguish.
>> >>
>> >> (Please note that I'm avoiding a situation where you have
to
>distinguish a
>> >phase
>> >> difference between same or similar sinusoids -- a different
problem and
>> >one FFTs
>> >> do not help with much.)
>> >>
>> >> Jeff Brower
>> >> DSP sw/hw engineer
>> >> Signalogic
>> >>
>> >>
>> >> >On the second matter, I'm still not sure of the
original
>> >> >question. However, clearly, a DFT on exactly the 900
original
>> >> >samples (with no zero padding), whether implemented with a
>> >> >brute force DFT algorithm, or some form of FFT algorithm
>> >> >(which, you are correct, is doable on a non-power of 2
length),
>> >> >should yield exactly the same results. It is simply an
issue
>> >> >of the method of computation.
>> >> >
>> >> >Now, if you wish to compare the FFT done on only the 900
points
>> >> >to the FFT done on the 1024 points (900+124 zeros),
you will get
>> >> >two different samplings of the same underlying spectra.
This
>> >> >is analagous to sampling a 1000Hz sinewave at a sampling
rate of
>> >> >8000Hz, and comparing these samples to the samples of a
1000Hz
>> >> >sinewave sampled, say, at 9000Hz. The samples will not
look the same,
>> >> >although, they represent the same underlying 1000Hz
sinewave.
>> >> >
>> >> >By the way, Michael, I am a mathematician.
>> >> >
>> >> >Regards,
>> >> >Tony
>> >> >
>> >> >----- Original Message -----
>> >> >From: Michael Strothjohann <strothjohann@stro...>
>> >> >To: Tony Zampini <tony@tony...>
>> >> >Cc: <Audiodsp@Audi...>; Suciu Radu
<radusuciu@radu...>
>> >> >Sent: Wednesday, October 24, 2001 3:23 AM
>> >> >Subject: Re: [audiodsp] zeroing the FFT
>> >> >
>> >> >
>> >> >> Toni,
>> >> >>
>> >> >> First: Zero-padding isnt realy increasing the
resolution of your
>> >> >> spectra. I'm very,very sorry about that, but
>> >> >> think twice: If it would possible to increase the
resolution
>> >> >> by simply adding some zero-samples, you would be able
to
>> >> >> get super-super-high resolution by adding a very
large number of
>> >> >> zeros. Now comes the bad news: this dosnt work.
>> >> >>
>> >> >> Second: FFT with (say) 900 samples is possible.
>> >> >> The number of samples is NOT required to be a power
of 2.
>> >> >> In most textbooks FFT is presented to the students
>> >> >> in the form of the very well known butterfly-diagra.
>> >> >> Reading the orginal papers in your library, you will
>> >> >> find out that sometimes the prime-factorisation will
helb you
>> >> >> to do a FFT of a number of samples NOT a power of
two.
>> >> >> Have a nice time in reading these papers presented to
>> >> >> the community some 30 years ago. Stop - you may also
>> >> >> ask an old mathematican if you know one.
>> >> >> ( sorry: the papers are 30 years old, so you
>> >> >> would need to find a very, very old mathematican )
>> >> >>
>> >> >> michael strothjohann
>> >> >>
>> >> >>
>> >> >>
>> >> >> Tony Zampini schrieb:
>> >> >> >
>> >> >> > Radu,
>> >> >> >
>> >> >> > Adding zeros to the end of your data is called
zero-padding and
>> >> >> > is commonly done to increase the resolution in
the resulting
>> >> >> > FFT frequency data. I'm not sure what you
mean by your statement:
>> >> >> > "The results are different from the FFT
done on the 900 samples".
>> >> >> > How did you do an FFT on the 900 samples? Did
you do a DFT (which
>> >> >> > is not limited to powers of 2)? Give us some
more information, and
>> >> >> > we can help you further.
>> >> >> >
>> >> >> > Best Regards,
>> >> >> > Tony
>> >> >> > ______________________________
>> >> >> > Tony Zampini (tony@tony...)
>> >> >> >
>> >> >> > ----- Original Message -----
>> >> >> > From: Suciu Radu <radusuciu@radu...>
>> >> >> >
>> >> >> > > I have an FFT algorithm that works for
example only for 1024,
>but I
>> >> >have
>> >> >> > > only , say 900 discrete values to calculate
the FFT on.
>> >> >> > > I put the other 124 values to zero (from
position 901 to 1024).
>> >> >> > > The results are different from the FFT done
on the 900 samples
>> >(1024
>> >> >> > > frequency samples).
>> >> >> > > Does anybody know how to get it done?
>> >> >> > >
>> >> >> > > Thanks,
>> >> >> > > Radu