zeroing the FFT

> Adding zeros = increasing the FFT length, which increases
> resolution -- you can
> see more detail.  Why else would you do it?
	The extra resolution u get is only some kind of interpolation. its not
the
original signal. The error b/w the interpolated result and the actual signal
has been well documented in our literature.

- Kishore
	>
> 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
>
>
> _____________________________________
> 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/
>
>

This e-mail is subject to the disclaimer set out below.
---

But AFAIK adding zeros *doesn't* increase the FFT length....
	-----Original Message-----
From: Jeff Brower [mailto:jbrower@jbro...]
Sent: 24 October 2001 16:29
To: Akshay Joshi
Cc: audiodsp@audi...; Tony Zampini; Suciu Radu; Michael
Strothjohann
Subject: Re: [audiodsp] zeroing the FFT
	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
	_____________________________________
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/
	---
This e-mail message is confidential and for use by the addressee only. If
you are not the intended recipient, you must not use, disclose, copy or
forward this transmission.  Please return the message to the sender by
replying to it and then delete the message from your computer.  The Generics
Group provides e-mail services for both itself and a number of its
independent spin-out companies.  The Generics Group shall not be held liable
to any person resulting from the use of any information contained in this
e-mail and shall not be liable to any person who acts or omits to do
anything in reliance upon it. The Generics Group does not accept
responsibility for changes made to this message after it was sent.
	

I think we are all correct for the most part, just that we are
looking at the issue from different angles.
I can give you an example where Jeff's point, that zero padding
improves resolution in the frequency domain,
is correct; and another example, where zero padding doesn't
improve spectrum resolution, and only doing a longer FFT will
help.
Jeff's mention to Radu about windowing, should be taken
seriously. In Radu's zero padded case (1024 pts.), the FFT
doesn't know that the validity of the original signal only
spans 900 points. It will assume that the padded zeros actually
existed in the original sampled signal. This is why windowing
is so important. It minimizes the ill-effects of the discontinuity
caused by abruptly adding zeros to a signal (as Jeff already pointed
out).
Recall that zero padding can be analyzed by interpreting the
zero padded signal as the original signal multiplied by a rectangular
signal that equals 1 from 1-900, and zero from 901 to 1024. Now recall
that multiplication in the time domain, is equivalent to convolution
in the frequency domain. The spectrum of a rectangular signal (window) is
a sinc function. The wider the rectangular, the narrower the sinc
function in the frequency domain. What the window does is help
reduce the sidelobes of the spectrum of the rectangular window,
(at the expense of widening the main lobe). Different windows behave
differently, but the idea is the same.

One last point. Windowing is important whether or not zero padding
is used. The window, in all cases, should cover only actual signal samples.
The padded zeros should be outside the window (a point obvious to most of
us,but perhaps not to beginners).

Sorry to be so long winded...
Tony

----- Original Message -----
From: McClean, Lesley-Ann <LMcClean@LMcC...>
To: 'Jeff Brower' <jbrower@jbro...>; Tony Zampini
<tony@tony...>
Cc: <audiodsp@audi...>
Sent: Wednesday, October 24, 2001 10:36 AM
Subject: RE: [audiodsp] zeroing the FFT
	> This e-mail is subject to the disclaimer set out below.
> --
-
>
> Guys,
>
> I'm not by any means an expert on this subject, but I think you are
> confusing 2 separate issues.
>
> Zero-padding increases the number of data points you have on your
frequency
> plot (due to way DFT is defined), and so when you
apply (the same length)
> FFT to a much longer data series you are able to see more on the plot
(might
> make you think you're getting a better
resolution when in fact you're
seeing
> more detail on the same plot by having more points
plotted)
>
> (For example, if you plotted a sinuosoid, you could do it with 3 points in
> every quarter, or you could do it with 20 points in every
> quarter...frequency is same, you just see so much detail in the signal)
>
> On the other hand, increasing the length of the FFT does increase the
> resolution you can obtain (irregardless of zero-padding present or not),
and
> hence can distinguish two much closer sinusoids. 
This is why you'd use a
> longer FFT, to determine if you've actually got more frequency
components
> present than you can see with a shorter FFT.
>
> These are just my thoughts on the matter!
>
> Lesley-Ann
>
>
>
> -----Original Message-----
> From: Jeff Brower [mailto:jbrower@jbro...]
> Sent: 24 October 2001 15:14
> To: Tony Zampini
> Cc: audiodsp@audi...; Suciu Radu; Michael Strothjohann
> 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
>
>
> --
-
> This e-mail message is confidential and for use by
the addressee only. If
> you are not the intended recipient, you must not use, disclose, copy or
> forward this transmission.  Please return the message to the sender by
> replying to it and then delete the message from your computer.  The
Generics
> Group provides e-mail services for both itself and
a number of its
> independent spin-out companies.  The Generics Group shall not be held
liable
> to any person resulting from the use of any
information contained in this
> e-mail and shall not be liable to any person who acts or omits to do
> anything in reliance upon it. The Generics Group does not accept
> responsibility for changes made to this message after it was sent.
>
>
	

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.

    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.

-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: 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
>
>
> _____________________________________
> 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/
>
>
	

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

By adding zeros you don't add any information ...
..Then you don't increase resolution..

Increase FFT length does not mean increase resolution (offten but not
always.)
	

Euh..
I all read carrefully ..
... The problem is what you call "resolution"....
Frequency resolution and Time resolution is not the same..

If you have a 900 samples signal... Perform a FFT with 900 point represent
perfectly your signal ( You do not need more point !!)..

If you perform a 1024 point FFT (after zero-padding) .. the fft - spectrum
is different..(you just have more rays ... more precision in frequency
domain)  .. but you dont increase the resolution :
If you do a IFFT you wont have a more precisly signal ..

One more thing... sorry for my English.. !!
..
(by the fact, i am a young audio dsp engineer)
	

Michael-

Increasing FFT size does in fact increase frequency resolution and will allow 
you to see greater detail; for example, a more sharply defined peak or dual 
peaks that would have previously blurred between two "bins" with wider
spacing. 
Otherwise, larger FFTs would be worthless and of course they are not and people 
use larger FFT sizes when system resources permit every day.

As for prime factor FFTs, why suggest that for an engineering solution?  Power 
of 2 size algorithms are convenient, lots of different DSP and coding examples 
are available, they are faster, take less code space, etc.  It sounds to me like

Radu is trying to make something practical so PF would be out.

The main issue that Radu needs to be concerned about in using zero filling is 
the edge; i.e. where his data stops and zeros start.  The FFT will see this as 
wideband noise, caused by an artifact that's not really there.  He may want
to 
apply a window to his 900 pts and run 2 FFTs, with the second one also windowed 
but overlapped 50% from the first).

Jeff Brower
DSP sw/hw engineer
Signalogic
	On Wed, 24 Oct 2001, Michael Strothjohann <strothjohann@stro...> 
wrote:
>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
	

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

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

First of all, the DFT (or FFT) is a discrete version of the DTFT.  The DTFT
is a continuous function and the DFT is discrete.  Performing a DFT on a
signal provides you a "discretized" picture of the DTFT.  So, by zero
padding the time-series data and then performing the DFT gives you a finer
spacing in the frequency domain, effectively giving you more frequency
resolution (fs/N).  There is no more information gained by this, but you get
to see the structure of the true DTFT.  As N->inf, the DFT->DTFT.  

There is a good treatment of this topic in Oppenheim.

Jim
	-----Original Message-----
From: Jeff Brower
To: Akshay Joshi
Cc: audiodsp@audi...; Tony Zampini; Suciu Radu; Michael Strothjohann
Sent: 10/24/2001 8:28 AM
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
	_____________________________________
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/