Zero padded FFt

Hi,
In order to increase resolution of my FFT (reduce midbin loss), I want
to use a 2N point FFT, N is a power of 2, last N points are zeroes.
What is the efficient way to compute this?
TIA
BRMADHUKAR

Madhukar wrote:

> Hi,
> In order to increase resolution of my FFT (reduce midbin loss), I want
> to use a 2N point FFT, N is a power of 2, last N points are zeroes.
> What is the efficient way to compute this?
> TIA
> BRMADHUKAR

Zero padding doesn't increase resolution. It increases the number of 
points in the plot by interpolating. You can do as well with a French 
curve and a practiced eye.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:

> 
> 
> Zero padding doesn't increase resolution. It increases the number of 
> points in the plot by interpolating. You can do as well with a French 
> curve and a practiced eye.

Here we go again.  If you define resolution as the number of 
points per unit frequency that are calculated of the 
underlying continuous function then it does increase 
resolution in that it gives an exact value for what the IR 
will do to the additional frequency points.  It's going to 
be pretty hard to do this with a French curve on a two 
valued function.

As far as the original question, I don't think there is a 
more efficient way than just tacking on the zeros and doing 
an FFT.


Bob
-- 

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

                                              A. Einstein

"Madhukar" <brmadhukar@hotmail.com> asked in message
news:2c04c006.0403030122.411bd92b@posting.google.com...

> In order to increase resolution of my FFT (reduce midbin loss), I want
> to use a 2N point FFT, N is a power of 2, last N points are zeroes.
> What is the efficient way to compute this?

One question worth considering is:  What does the
answer (2N point FFT output) mean?  If the FFT
is meant to estimate the spectrum of the underlying
continuous-time signal, then the continuous-time
signal corresponding to the N original samples followed
by N zeroes is *not* the same as the signal that gave
us the N original samples.  For example, for N = 4
what is the continuous-time signal corresponding to
(+1, +1, -1, -1) ?  What is the continuous-time
signal corresponding to (+1, +1, -1, -1, 0, 0, 0, 0)?

If you *do* want to compute the 2N-point FFT of N
data points followed by N zeroes, then the first
step in effect copies the N data points into the zero
locations and multiplies them by twiddle factors.
There is some minor savings in the first step based on
recognizing the fact that one input to each butterfly
is zero, thus avoiding some additions/subtractions
or multiplications.

Bob Cain wrote:

> 
> Here we go again.  If you define resolution as the number of points per 
> unit frequency that are calculated of the underlying continuous function 
> then it does increase resolution in that it gives an exact value for 
> what the IR will do to the additional frequency points.  It's going to 
> be pretty hard to do this with a French curve on a two valued function.
> 

An illustration of this point just occured to me.  It 
involves extending the frequency domain function by zeros 
and taking the inverse rather than extending the time domain 
but the principle works both ways.

Consider the time sequence:

   ...+1,-1,+1,-1,+1,+1,-1,+1,-1,+1...

where ... can be of any length, but let's make it big.  If 
you pad the FFT of that to twice it's length and then take 
the IFFT you may (or may not) be surprised at what appears 
between the original +1,+1 samples.  If ... is infinity then 
the value that appears in between will be infinite but those 
original finite valued samples contain all the information 
needed to represent that infinite value and it's still band 
limited.

To me this is increasing resolution no matter how it is 
defined.  I frequently find these kinds of surpises in the 
low frequency response of microphone FIR's that are short 
after I zero extend them to be long.  Convolving the short 
FIR against a sin sweep verifies those surprises.

This had led me to wish that audio editors like Adobe 
Audition performed the same kind of sinc interpolation on 
its FFT displays as it does on it's time domain display to 
connect the dots.


Bob
-- 

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

                                              A. Einstein

Bob Cain wrote:
> Jerry Avins wrote:
>=20
>>
>>
>> Zero padding doesn't increase resolution. It increases the number of=20
>> points in the plot by interpolating. You can do as well with a French =

>> curve and a practiced eye.
>=20
>=20
> Here we go again.  If you define resolution as the number of points per=
=20
> unit frequency that are calculated of the underlying continuous functio=
n=20
> then it does increase resolution in that it gives an exact value for=20
> what the IR will do to the additional frequency points.  It's going to =

> be pretty hard to do this with a French curve on a two valued function.=

>=20
> As far as the original question, I don't think there is a more efficien=
t=20
> way than just tacking on the zeros and doing an FFT.
>=20
>=20
> Bob

A French curve with a sin(x)/x shape will do the job very good.

Ren=E9

Bob Cain <arcane@arcanemethods.com> wrote in message news:<c25ajg01cuc@enews2.newsguy.com>...
> Jerry Avins wrote:
> 
> > 
> > 
> > Zero padding doesn't increase resolution. It increases the number of 
> > points in the plot by interpolating. You can do as well with a French 
> > curve and a practiced eye.
> 
> Here we go again.  If you define resolution as the number of 
> points per unit frequency that are calculated of the 
> underlying continuous function then it does increase 
> resolution in that it gives an exact value for what the IR 
> will do to the additional frequency points.  It's going to 
> be pretty hard to do this with a French curve on a two 
> valued function.

Eh... I'm not sure I understand what you mean. I interpret you as saying 
something like 

  "the DFT of N points zero-padded to 2N, measures the same spectrum 
   as the original continuous process being sampled 2N times."

I am not at all sure that's what you mean (I surely hope it isn't), 
but let's play with that idea.

Now, why would you need N samples, then? The same argument should work 
in the other direction: N/2 samples should give the same results as 
the N samples you have. So throw away half of those samples, to save work.

But why end there? Throw away half of those samples too, and continue 
until you have only one sample left. Zero-pad this sample to a sequence
of a length of your choosing, and enlightenment will prevail: Anything 
worth knowing about the original continuous process is revealed to you.

Sorry. I just couldn't resist...

Rune

Bob Cain wrote:

> Jerry Avins wrote:
> 
>> 
>> 
>> Zero padding doesn't increase resolution. It increases the number of
>> points in the plot by interpolating. You can do as well with a French
>> curve and a practiced eye.
> 
> Here we go again.  If you define resolution as the number of
> points per unit frequency that are calculated of the
> underlying continuous function then it does increase
> resolution in that it gives an exact value for what the IR
> will do to the additional frequency points.  It's going to
> be pretty hard to do this with a French curve on a two
> valued function.

Indeed.

No doubt there are many interpolation techniques which will give
you equally "pretty" curves joining the dots, but most of them
will not give you exact samples of Fourier transform, Jerry's French
curve method included. (I'm also puzzled about exactly what a
complex French curve looks like and how the practiced eye algorithm
works :-)

Of the three obvious ways I can think of to calculate more densely
spaced exact samples, the zero padding technique is the second
most efficient but probably the easiest to implement for powers
of 2.

Getting exact Fourier transform samples is important for the OP's
application, because you need to oversample by a factor of at least
2 if you're going calculate samples of the spectrum from the Fourier
transform samples (even if you intend to use other techniques to
interpolate the resulting spectrum samples).

Regards
--
Adrian Hey

Rune Allnor wrote:

> Bob Cain <arcane@arcanemethods.com> wrote in message
> news:<c25ajg01cuc@enews2.newsguy.com>...
>> Jerry Avins wrote:
>> 
>> > 
>> > 
>> > Zero padding doesn't increase resolution. It increases the number of
>> > points in the plot by interpolating. You can do as well with a French
>> > curve and a practiced eye.
>> 
>> Here we go again.  If you define resolution as the number of
>> points per unit frequency that are calculated of the
>> underlying continuous function then it does increase
>> resolution in that it gives an exact value for what the IR
>> will do to the additional frequency points.  It's going to
>> be pretty hard to do this with a French curve on a two
>> valued function.
> 
> Eh... I'm not sure I understand what you mean. I interpret you as saying
> something like
> 
>   "the DFT of N points zero-padded to 2N, measures the same spectrum
>    as the original continuous process being sampled 2N times."
> 
> I am not at all sure that's what you mean (I surely hope it isn't),

That is clearly not what Bob is saying. The underlying continuous function
Bob is talking about is the Fourier transform.

But methinks you knew that already, so what's the point in misrepresenting
his post?

> but let's play with that idea.
> 
> Now, why would you need N samples, then? The same argument should work
> in the other direction: N/2 samples should give the same results as
> the N samples you have. So throw away half of those samples, to save work.
> 
> But why end there? Throw away half of those samples too, and continue
> until you have only one sample left. Zero-pad this sample to a sequence
> of a length of your choosing, and enlightenment will prevail: Anything
> worth knowing about the original continuous process is revealed to you.
> 
> Sorry. I just couldn't resist...

Perhaps you should try a bit harder in future.

Regards
--
Adrian Hey

Hello Bob,

I think the arguments center around what we mean by resolution. Certainly
zero padding will not give us more information than was already contained in
the original samples. And a lot of people will associate the term resolution
with information. Imagine we have two sine waves close together in
frequency, and we collect N samples, and N is such that both sines fit in
the same spectral bin. Now zero padding is not going to let us tell the two
frequencies apart. If we wish to resolve the two frequencies, we need to let
N be bigger.

Now another meaning of "resolution" is what I believe you may be thinking
about concerns the interpolation of a discretely sampled signal. If we plot
the data for a sinusoid whose frequency is say 45% of the sampling rate, we
will not visually perceive a sine wave, yet we know from the WKS sampling
theorem that all of the info is there. So in this case it is our visual
system that fails, so we can fix it by oversampling. And yes I agree that
zero padding makes it look better (CoolEdit does a good interpolation on its
waveform display) but it adds no new info. A mathematical analysis of what
zero padding before doing an FFT actually does shows it is really an
interpolation with a periodic sinc function (i.e., the Dirichlet kernal).
Since it can be written mathematically as an interpolation one can see again
no new info is created. But for display purposes it can make the spectrum
look better to the eye. So when argue about increasing the resolution we
have to be careful to state whether we are increasing the analysis
resolution or the displayed resolution, and zero padding the FFT only does
the latter.

I hope this helps.

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz



"Bob Cain" <arcane@arcanemethods.com> wrote in message
news:c267de02nn4@enews4.newsguy.com...
> Bob Cain wrote:
>
> >
> > Here we go again.  If you define resolution as the number of points per
> > unit frequency that are calculated of the underlying continuous function
> > then it does increase resolution in that it gives an exact value for
> > what the IR will do to the additional frequency points.  It's going to
> > be pretty hard to do this with a French curve on a two valued function.
> >
>
> An illustration of this point just occured to me.  It
> involves extending the frequency domain function by zeros
> and taking the inverse rather than extending the time domain
> but the principle works both ways.
>
> Consider the time sequence:
>
>    ...+1,-1,+1,-1,+1,+1,-1,+1,-1,+1...
>
> where ... can be of any length, but let's make it big.  If
> you pad the FFT of that to twice it's length and then take
> the IFFT you may (or may not) be surprised at what appears
> between the original +1,+1 samples.  If ... is infinity then
> the value that appears in between will be infinite but those
> original finite valued samples contain all the information
> needed to represent that infinite value and it's still band
> limited.
>
> To me this is increasing resolution no matter how it is
> defined.  I frequently find these kinds of surpises in the
> low frequency response of microphone FIR's that are short
> after I zero extend them to be long.  Convolving the short
> FIR against a sin sweep verifies those surprises.
>
> This had led me to wish that audio editors like Adobe
> Audition performed the same kind of sinc interpolation on
> its FFT displays as it does on it's time domain display to
> connect the dots.
>
>
> Bob
> -- 
>
> "Things should be described as simply as possible, but no
> simpler."
>
>                                               A. Einstein