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
	

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
>
	

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
	

Toni,

First: Zero-padding isnt realy increasing the resolution of your
spectra. I'm very,very sorry about that, but 
think twice: If it would possible to increase the resolution 
by simply adding some zero-samples, you would be able to 
get super-super-high resolution by adding a very large number of
zeros. Now comes the bad news: this dosnt work.  

Second: FFT with (say) 900 samples is possible. 
The number of samples is NOT required to be a power of 2.
In most textbooks FFT is presented to the students 
in the form of the very well known butterfly-diagra.
Reading the orginal papers in your library, you will 
find out that sometimes the prime-factorisation will helb you 
to do a FFT of a number of samples NOT a power of two.
Have a nice time in reading these papers presented to
the community some 30 years ago. Stop - you may also
ask an old mathematican if you know one.
( sorry: the papers are 30 years old, so you 
would need to find a very, very old mathematican )    
 
michael strothjohann
	Tony Zampini schrieb:
> 
> Radu,
> 
> Adding zeros to the end of your data is called zero-padding and
> is commonly done to increase the resolution in the resulting
> FFT frequency data. I'm not sure what you mean by your statement:
> "The results are different from the FFT done on the 900 samples".
> How did you do an FFT on the 900 samples? Did you do a DFT (which
> is not limited to powers of 2)? Give us some more information, and
> we can help you further.
> 
> Best Regards,
> Tony
> ______________________________
> Tony Zampini (tony@tony...)
>
> ----- Original Message -----
> From: Suciu Radu <radusuciu@radu...>
> 
> > I have an FFT algorithm that works for example only for 1024, but I
have
> > only , say 900 discrete values to calculate the FFT on.
> > I put the other 124 values to zero (from position 901 to 1024).
> > The results are different from the FFT done on the 900 samples (1024
> > frequency samples).
> > Does anybody know how to get it done?
> >
> > Thanks,
> > Radu
	

First of all, 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
	

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

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
>
>
>
> _____________________________________
> Note: If you do a simple "reply" with your email client, only the
author
of this message will receive your answer.  You need to do a "reply
all" if
you want your answer to be distributed to the entire group.
>
> _____________________________________
> About this discussion group:
>
> To Join:  audiodsp-subscribe@audi...
>
> To Post:  audiodsp@audi...
>
> To Leave: audiodsp-unsubscribe@audi...
>
> Archives: http://groups.yahoo.com/group/audiodsp
>
> Other DSP-Related Groups: http://www.dsprelated.com
>
>
> ">http://docs.yahoo.com/info/terms/
>
>
	

> 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
>
>
>
> _____________________________________
> Note: If you do a simple "reply" with your email client, only the
author
of this message will receive your answer.  You need to do a "reply
all" if
you want your answer to be distributed to the entire group.
>
> _____________________________________
> About this discussion group:
>
> To Join:  audiodsp-subscribe@audi...
>
> To Post:  audiodsp@audi...
>
> To Leave: audiodsp-unsubscribe@audi...
>
> Archives: http://groups.yahoo.com/group/audiodsp
>
> Other DSP-Related Groups: http://www.dsprelated.com
>
>
> ">http://docs.yahoo.com/info/terms/
>
>
	

Jeff,
    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
>
>
> _____________________________________
> Note: If you do a simple "reply" with your email client, only the
author
of this message will receive your answer.  You need to do a "reply
all" if
you want your answer to be distributed to the entire group.
>
> _____________________________________
> About this discussion group:
>
> To Join:  audiodsp-subscribe@audi...
>
> To Post:  audiodsp@audi...
>
> To Leave: audiodsp-unsubscribe@audi...
>
> Archives: http://groups.yahoo.com/group/audiodsp
>
> Other DSP-Related Groups: http://www.dsprelated.com
>
>
> ">http://docs.yahoo.com/info/terms/
>
>
	

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

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.