AAC | ADPCM | Convolution | DAFx | FFT | IIR | Mixer | MP3 | MPEG | MPEG-4

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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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...)
Director of Engineering
DSP Global Inc.
475 Jefferson Blvd.
Warwick, RI 02886
Tel. 401-737-9900
FAX: 401-739-4197
www.dspglobal.com

----- Original Message ----- 
From: Suciu Radu <radusuciu@radu...>
To: <Audiodsp@Audi...>
Sent: Tuesday, October 23, 2001 6:35 AM
Subject: [audiodsp] zeroing the FFT
	> 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
>
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Hi,

Hint: the simple difference is that FFT is working
on two PERIOD data sets( periods: 900 samples,
1024 samples ). What is your window function ? 
 
michael strothjohann
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

First of all, thanks everybody for your prompt response.
I think I should have been more clearer in explaining my problem.

I am writing my own FFT algorithms, and in order to have an optimal FFT 
(faster, less power and area consuming), I must use numbers that are a power 
of 2. I am not using just radix 2, I am deriving my own algorithms for 
specific applications. Ex: 1K, 2K, 3K, etc. FFT.
The algorithms are based on the classical radixes: 2, 4, that are rearanged 
and recombined to better suit my needs.
So, more concrete: having a 1K (1024) FFT algorithm, based on radix 2 (for 
simplicity). It will work ONLY for this size.
But can I perform an FFT on a smaller data size using the same algorithm? 
Ex: f(x)=x, x=0:900.
If I put the 0:900 discrete data at the imput of my algorithm, and pad the 
rest with zero, the result will be something else than FFT(f(x)).

It will be something on 1024 discrete values.

Thus the question: how to get from the 1024 discrete output to 900 discrete 
values that would equal FFT(f(x))? I imagine some interpolation function?

And to end, I am not involved in audio processing, only in FFT's in general.

Thanks again,

Radu
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Michael,

You are primarily correct on both issues. However, it
is more a matter of my choice of words, than my knowledge
of the subject. I should have been more articulate.

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.

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Hi Michael,

Not really:-)
    How about taking a 10 tap FIR filter, by taking a 10 point DFT and then
taking a 1024 point DFT over the same..  Cause it anyway had zeros at the
tail.. so more the zeros more the resolution.

    But you are completely right, if you take continuous data and window it
.. you dont resolve any further, by adding more zeros.

-Akshay.
	----- Original Message -----
From: Michael Strothjohann <strothjohann@stro...>
To: Tony Zampini <tony@tony...>
Cc: <Audiodsp@Audi...>; Suciu Radu <radusuciu@radu...>
Sent: Wednesday, October 24, 2001 12:53 PM
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
>
>
>
> _____________________________________
> 
>
>
> 
>
>
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

> Thus the question: how to get from the 1024 discrete output to 900
discrete
> values that would equal FFT(f(x))? I imagine some interpolation function?

Interpolating linearly between two frequency magnitude points would add a
time domain noise which is sinc^2.

-Akshay.

----- Original Message -----
From: Suciu Radu <radusuciu@radu...>
To: <Audiodsp@Audi...>
Sent: Wednesday, October 24, 2001 3:46 PM
Subject: Re: [audiodsp] zeroing the FFT
	>
> First of all, thanks everybody for your prompt response.
> I think I should have been more clearer in explaining my problem.
>
> I am writing my own FFT algorithms, and in order to have an optimal FFT
> (faster, less power and area consuming), I must use numbers that are a
power
> of 2. I am not using just radix 2, I am deriving my own algorithms for
> specific applications. Ex: 1K, 2K, 3K, etc. FFT.
> The algorithms are based on the classical radixes: 2, 4, that are
rearanged
> and recombined to better suit my needs.
> So, more concrete: having a 1K (1024) FFT algorithm, based on radix 2 (for
> simplicity). It will work ONLY for this size.
> But can I perform an FFT on a smaller data size using the same algorithm?
> Ex: f(x)=x, x=0:900.
> If I put the 0:900 discrete data at the imput of my algorithm, and pad the
> rest with zero, the result will be something else than FFT(f(x)).
>
> It will be something on 1024 discrete values.
>
> Thus the question: how to get from the 1024 discrete output to 900
discrete
> values that would equal FFT(f(x))? I imagine some interpolation function?
>
> And to end, I am not involved in audio processing, only in FFT's in
general.
>
> Thanks again,
>
> Radu
>
>
>
> _____________________________________
> 
>
>
> 
>
>
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Jeff,
    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.

-Akshay.

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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.
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	_____________________________________

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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)
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	_____________________________________

	
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Michael Strothjohann 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.

But it does.  The DFT samples a function in the frequency domain the
same way the original data samples a function in the time domain.  Both
contain values between samples.  They are just redundant and not needed
to fully reconstruct the function from the samples.  Sinc interpolation
gives those values exactly if the function is band limited by the
Nyquist criterion.  A zero padded DFT gives the same values as if the
higher resolution point had been calculated by sinc interpolation.

A way to think of the DFT that makes this clearer is to look at the
original definition.  Each "complex" point is just the result of taking
the inner product of a sampled time sequence with a sampled sinusoid
(real part) and its quadrature cosinusoid (imaginary part) at each
frequency that is an integer multiple of that frequency which has a
wavelength equal to the length of the time sequence and limited by the
Nyquist criterion.  Each of those inner products is fully accurate
regardless of how many zeros have been appended to the time sequence. 
The DFT is just a sampling method.  The FFT does the same operation
faster by factoring out redundant computation.  As the length of the
time series increases so does the number of sinusoids that will fit in
the length of the time series.  That increased resolution is quite real.

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

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Jeff,

    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.

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

Why *not*?

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

FFT is just a representation of the original signal in time domain

When you represent a point in 3D-space, you just need 3 vectors..
You can represent it , with 32 others vectors if you want . but using 32
vectors do not increase your resolution...

FFT is the same..
In this case, you need 900 point to describe perfectly your signal..
If you do zero padding, you can use a 1024 point-FFT which algorithm must be
faster (radix-2),
You dont have the same representation (the same vectors in geometry space),
but you dont have more resolution...

Anyone agree with me ??
	> 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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

--- Jeff Brower <jbrower@jbro...> wrote:
> 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
> 

How are you defining "resolve"?

If the waves are added together, they cannot be
"resolved" by zero padding.

Mark
markrages@mark...
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

"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

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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