Zero Padding in radix 2 FFT

Hello all,

Sorry for starting this topic all over again. I had seen some previous
discussions on zero padding and when I started reading them I
completely got lost.

When I am provided with samples which are not of power of 2 and I need
to implement FFT, I zero pad the samples to the next highest power of
2.  I  do FFT using Cooley Tukey algo and observe that the frequency
componets in several bin - ie there is spectral leakage even though the
signal given to me had a single tone.

I did think of using some of the algos given to interpolate  and find
the exact signal frequency. But then this would work only if the
samples given to me were of single tone, the problem is I would have no
idea of the kind of signal I am looking at.

Next I used MATLAB and resampled the samples to the next higest power
of 2 and then fed it to radix2 FFT algo. It seems to work fine.

Here are my questions:

1. Does it mean zero padding is not after all a good idea if you have
no idea of the signal.   Because by zero padding I am assuming that
there is a dead band ( as to say) for the next few samples.

2. Is it a good idea to resample and then apply or use a different FFT
algo like Chrip-Z or prime factor.

Please do let me know if I have gone wrong in my understanding and
correct me.  Sorry for starting the whole discussion again as I have
read some  heated dsicussions on the topic in this forum earlier.

Wishing You all a very Happy New Year

Regards

Iqbal

"Iqbal" <iqbalbawa@gmail.com> wrote in message 
news:1135921115.661301.31030@f14g2000cwb.googlegroups.com...
> Hello all,
>
> Sorry for starting this topic all over again. I had seen some previous
> discussions on zero padding and when I started reading them I
> completely got lost.
>
> When I am provided with samples which are not of power of 2 and I need
> to implement FFT, I zero pad the samples to the next highest power of
> 2.  I  do FFT using Cooley Tukey algo and observe that the frequency
> componets in several bin - ie there is spectral leakage even though the
> signal given to me had a single tone.
>
> I did think of using some of the algos given to interpolate  and find
> the exact signal frequency. But then this would work only if the
> samples given to me were of single tone, the problem is I would have no
> idea of the kind of signal I am looking at.
>
> Next I used MATLAB and resampled the samples to the next higest power
> of 2 and then fed it to radix2 FFT algo. It seems to work fine.
>
> Here are my questions:
>
> 1. Does it mean zero padding is not after all a good idea if you have
> no idea of the signal.   Because by zero padding I am assuming that
> there is a dead band ( as to say) for the next few samples.
>
> 2. Is it a good idea to resample and then apply or use a different FFT
> algo like Chrip-Z or prime factor.
>
> Please do let me know if I have gone wrong in my understanding and
> correct me.  Sorry for starting the whole discussion again as I have
> read some  heated dsicussions on the topic in this forum earlier.
>

Igbal,

There are some fundamentals worth noting:

1) the only time there will not be apparent spectral leakage with a pure 
sinusoid is if the temporal epoch is an integer number of cycles.  This 
includes the zero padding.  Otherwise, for general signals there will always 
be spectral leakage.  Windowing can help.  Try transforming (M +1/2) cycles 
of a sinusoid and see what you get.  M is an integer.

2) Let's assume that you have 80 samples that represent 4 cycles of a 
sinusoid exactly - call it frequency "f".  The Fourier Transform will be a 
pair of samples at -f and +f.  Now, if you zero pad to 160 samples the 
spectral leakage will be evident and you will see the spectrum with 
alternating zeros which fall on the old sample points in frequency. 
However, if you zero pad to 128 samples, the periodic zeros won't be so 
evident as in the case of the M+1/2 cycle signal.  If you zero pad to 2048 
samples then you will see the spectral leakage and may be able to discern 
interim points where zeros would occur if you were to interpolate.

Fred 

On 2005-12-30 01:38:35 -0400, "Iqbal" <iqbalbawa@gmail.com> said:

> Hello all,
> 
> Sorry for starting this topic all over again. I had seen some previous
> discussions on zero padding and when I started reading them I
> completely got lost.
> 
> When I am provided with samples which are not of power of 2 and I need
> to implement FFT, I zero pad the samples to the next highest power of
> 2.  I  do FFT using Cooley Tukey algo and observe that the frequency
> componets in several bin - ie there is spectral leakage even though the
> signal given to me had a single tone.

FFTs come in many sizes. Powers of two are for describing in a one page
appendix of an introductory text book. Using 2s, 3s, and 5s will get you
a lot more flexibility so that the frequencies implied by the length of
the transform and your sampling rate will be the ones you are looking for.

All the technicalities of the effects of finite duration will be much
less intrusive. The loss of the efficiency of powers of two (actually
there is a formal arguement that powers of 3 are better) is more fiction
than fact and the gain from using a more suitable size will more than
compensate for the loss, if any.

> I did think of using some of the algos given to interpolate  and find
> the exact signal frequency. But then this would work only if the
> samples given to me were of single tone, the problem is I would have no
> idea of the kind of signal I am looking at.
> 
> Next I used MATLAB and resampled the samples to the next higest power
> of 2 and then fed it to radix2 FFT algo. It seems to work fine.
> 
> Here are my questions:
> 
> 1. Does it mean zero padding is not after all a good idea if you have
> no idea of the signal.   Because by zero padding I am assuming that
> there is a dead band ( as to say) for the next few samples.
> 
> 2. Is it a good idea to resample and then apply or use a different FFT
> algo like Chrip-Z or prime factor.
> 
> Please do let me know if I have gone wrong in my understanding and
> correct me.  Sorry for starting the whole discussion again as I have
> read some  heated dsicussions on the topic in this forum earlier.
> 
> Wishing You all a very Happy New Year
> 
> Regards
> 
> Iqbal

"Gordon Sande" <g.sande@worldnet.att.net> wrote in message 
news:2005123009494716807-gsande@worldnetattnet...
> On 2005-12-30 01:38:35 -0400, "Iqbal" <iqbalbawa@gmail.com> said:

>...........so that the frequencies implied by the length of
> the transform and your sampling rate will be the ones you are looking for.
>
> All the technicalities of the effects of finite duration will be much
> less intrusive.

Gordon,

It seems you're saying something rather profound here but I'm not sure I 
quite get it.

"The frequencies implied by the length of the transform" ???  Do you simply 
mean the frequency sample interval here or ...?

The last sentence I don't understand yet.  I should think that finite 
duration pretty much sets things up for leakage, desire for windowing, etc., 
no?  Other than windowing, how might it be "less intrusive"?

Or, did you mean that if one picks exactly the right temporal epoch for a 
particular sinusoid then the effects of leakage will be hidden or absent or 
whatever term you like to use there....?

Fred 

> The loss of the efficiency of powers of two (actually
> there is a formal arguement that powers of 3 are better)

Are you referring to Cooley & Tukey's argument in their 1965 paper?
I'm pretty sure that argument was erroneous (it assumed that the
radix-r butterfly requires O(r^2) operations instead of O(r log r),
forgetting that the butterfly can itself use an FFT).

Of course, in practice the lowest arithmetic counts have been achieved
for split-radix and friends (including recent developments, see
jdj.mit.edu/~stevenj/newsplit.pdf), which as radix 2/4 could be thought
of as "averaging" to radix 3, but e.g. recent work by Swamy et al. have
shown that the same arithmetic counts as traditional split radix can be
achieved with radix 2/8, 2/16, etcetera.

I agree, however, that the loss of efficiency from not using powers of
two is not borne out in practice.  It is true that most FFT
implementations tend to be much more optimized for the power-of-two
case because it is so common, but this gain is usually outweighed by
the loss of padding to a much larger size.  Also, thanks to limited
cache associativity, non-powers-of-two can have some inherent
advantages.

Cordially,
Steven G. Johnson

Fred Marshall wrote:
> 1) the only time there will not be apparent spectral leakage with a pure
> sinusoid is if the temporal epoch is an integer number of cycles.  This
> includes the zero padding.  Otherwise, for general signals there will always
> be spectral leakage.  Windowing can help.  Try transforming (M +1/2) cycles
> of a sinusoid and see what you get.  M is an integer.

it doesn't have to be a single pure sinusoid.  it can be a sum of
harmonically related sinusoids or, in other words, an arbitrary
periodic function with period of N (or a sub-multiple of N), the size
of the DFT/FFT.

r b-j

robert bristow-johnson wrote:
> Fred Marshall wrote:
> 
>>1) the only time there will not be apparent spectral leakage with a pure
>>sinusoid is if the temporal epoch is an integer number of cycles.  This
>>includes the zero padding.  Otherwise, for general signals there will always
>>be spectral leakage.  Windowing can help.  Try transforming (M +1/2) cycles
>>of a sinusoid and see what you get.  M is an integer.
> 
> 
> it doesn't have to be a single pure sinusoid.  it can be a sum of
> harmonically related sinusoids or, in other words, an arbitrary
> periodic function with period of N (or a sub-multiple of N), the size
> of the DFT/FFT.

Robert,

The FFT is a marvelously simplified way to calculate the Fourier series 
that represents a particular periodic function f(t). It also cloaks the 
calculation in such trickery that what's actually happening is hidden 
from ordinary mortals. To understand the process, they should try this:

 From the period, calculate the fundamental frequency, w.

Calculate all the integrals sin(nwt)f(t)dt and cos(nwt)f(t)dt over a 
period for n = 0, 1, .... [high enough]. Note that for n = 0 the sine 
integral is zero and the cosine integral is the function's average value 
(DC).

All the integrals are the coefficients a_n and b_n in the series 
a_n*sin(nwt)f(t)dt + b_n*cos(nwt)f(t)dt.

The usual FFT gives results for the exponential form, further disguising 
the nature of what it actually computes. Without these confusions, your 
added comment wouldn't likely have been needed.

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

Jerry Avins wrote:
> robert bristow-johnson wrote:
> > Fred Marshall wrote:
> >
> >>1) the only time there will not be apparent spectral leakage with a pure
> >>sinusoid is if the temporal epoch is an integer number of cycles.  This
> >>includes the zero padding.  Otherwise, for general signals there will always
> >>be spectral leakage.  Windowing can help.  Try transforming (M +1/2) cycles
> >>of a sinusoid and see what you get.  M is an integer.
> >
> >
> > it doesn't have to be a single pure sinusoid.  it can be a sum of
> > harmonically related sinusoids or, in other words, an arbitrary
> > periodic function with period of N (or a sub-multiple of N), the size
> > of the DFT/FFT.
>
> The FFT is a marvelously simplified way to calculate the Fourier series
> that represents a particular periodic function f(t). It also cloaks the
> calculation in such trickery that what's actually happening is hidden
> from ordinary mortals. To understand the process, they should try this:
>
>  From the period, calculate the fundamental frequency, w.
>
> Calculate all the integrals sin(nwt)f(t)dt and cos(nwt)f(t)dt over a
> period for n = 0, 1, .... [high enough]. Note that for n = 0 the sine
> integral is zero and the cosine integral is the function's average value
> (DC).
>
> All the integrals are the coefficients a_n and b_n in the series
> a_n*sin(nwt)f(t)dt + b_n*cos(nwt)f(t)dt.
>
> The usual FFT gives results for the exponential form, further disguising
> the nature of what it actually computes. Without these confusions, your
> added comment wouldn't likely have been needed.

well, even though i do not think about the real Fourier series
(prefering the complex one) you know that i am a partisan for the
notion that the DFT maps a discrete and periodic function of period N
to another discrete and periodic sequence (also fully defined by N
complex coefs.

r b-j

Jerry Avins wrote:
> The FFT is a marvelously simplified way to calculate the Fourier series
> that represents a particular periodic function f(t).

Um, since when was the DFT the same as the Fourier series?  Let's not
confuse approximation with definition.

Jerry Avins wrote:
> The FFT is a marvelously simplified way to calculate the Fourier series
> that represents a particular periodic function f(t).

Um, since when was the DFT the same as the Fourier series?  Let's not
confuse approximation with definition.