zero padding radix - 2 FFT

For starters, I'm still a newbie muddling my way through the various
texts and fourier terminologies.    I'm of the impression that given an
FFT with an odd size.  Zero padding the FFT to the next power of two
amounts will do the trick.  Barring efficiency reasons with regards to
odd sizes, I'm only interested in how the padded and non padded version
could be equivalent.   Now utilizing matlab as my analysis tool.
Given:

>> x=[0,1,2,3,4]
x =
     0     1     2     3     4
>> y=fft(x)'

y =
  10.0000
  -2.5000 - 3.4410i
  -2.5000 - 0.8123i
  -2.5000 + 0.8123i
  -2.5000 + 3.4410i

Now zero pad to the next power of two.

>> x=[0,1,2,3,4,0,0,0]
x =
     0     1     2     3     4     0     0     0
>> y=fft(x)'

y =

  10.0000
  -5.4142 + 4.8284i
   2.0000 - 2.0000i
  -2.5858 + 0.8284i
   2.0000
  -2.5858 - 0.8284i
   2.0000 + 2.0000i
  -5.4142 - 4.8284i

>>

How is the result from the result from the padded and non-padded
version equivalent or is there my understanding flawed?

Thanks in advance

Hallo,

In the N-points signal x(t), usually we pad with zeors up to L , L>N so
it becomes L-point DFT.
There is no much eye catching information in time domain regarding to
this padding, but in the frequency this will result a better frequency
resolution. Therefore, from your result its showed a better resolution
than unpadded one.

This also can be named as spectral interpolation.

Regards 

Mohadig Widha

The larger the size of the DFT, the smaller the sampling interval in
the frequency domain. If you have, for instance,

x = [1:1000];
X = fft( x, [], );
Xpadded = fft( x, 4096 );

Both X and Xpadded represent the same function, viz. the spectrum of x,
the difference is in the sampling of the spectrum. The sample spacing
for X is 2*pi/1000, while for Xpadded it is 2*pi/4096. Zero-padding
does not increase resolution, it only decreases the sampling interval.

On 13 May 2006 12:29:50 -0700, forums_mp@hotmail.com wrote:

>For starters, I'm still a newbie muddling my way through the various
>texts and fourier terminologies.    I'm of the impression that given an
>FFT with an odd size.  Zero padding the FFT to the next power of two
>amounts will do the trick.  Barring efficiency reasons with regards to
>odd sizes, I'm only interested in how the padded and non padded version
>could be equivalent.   Now utilizing matlab as my analysis tool.
>Given:
>
>>> x=[0,1,2,3,4]
>x =
>     0     1     2     3     4
>>> y=fft(x)'
>
>y =
>  10.0000
>  -2.5000 - 3.4410i
>  -2.5000 - 0.8123i
>  -2.5000 + 0.8123i
>  -2.5000 + 3.4410i
>
>Now zero pad to the next power of two.
>
>>> x=[0,1,2,3,4,0,0,0]
>x =
>     0     1     2     3     4     0     0     0
>>> y=fft(x)'
>
>y =
>
>  10.0000
>  -5.4142 + 4.8284i
>   2.0000 - 2.0000i
>  -2.5858 + 0.8284i
>   2.0000
>  -2.5858 - 0.8284i
>   2.0000 + 2.0000i
>  -5.4142 - 4.8284i
>
>>>
>
>How is the result from the result from the padded and non-padded
>version equivalent or is there my understanding flawed?
>
>Thanks in advance

Hi forums_mp,

  ah ha, you're startin' to learn about 
the discrete Fourier transform.  This is good.

The sequence x=[0,1,2,3,4] has continuous Fourier transform 
(an infinite-resolution transform) that is called 
the Discrete-time Fourier Transform, the "DTFT".
For simple sequences, that DTFT can be obtained 
with pencil & paper algebra.   However, we can 
approximate (compute) the DTFT of x on a computer 
by "padding' the x sequence with many many 
zero-valued samples and perform a very large-sized 
DFT (using the FFT algorithm).

OK, here's where I'm going.  The discrete Fourier 
transform (DFT) of x computes a *sampled* version 
of the DTFT of x.  Computing a 5-point DFT of x 
will give your five samples on the full DTFT curve
for the time sequence x.
If you pad x with three zero-valued samples and 
perform an 8-point DFT you'll obtain eight samples 
of the full DTFT curve for the time sequence x.

If you pad x with 2043 zero-valued samples and 
perform an 2048-point DFT you'll obtain 2048 samples 
of the full DTFT curve for the 5-sample sequence x.
In this case, you'll have a very accurate 
(very highly sampled) representation of 
the true Fourier tansform of your original 
5-sample x sequence.

Hope that made some sense.

Good Luck,
[-Rick-]





 

forums_mp@hotmail.com wrote:
> For starters, I'm still a newbie muddling my way through the various
> texts and fourier terminologies.    I'm of the impression that given an
> FFT with an odd size.  Zero padding the FFT to the next power of two
> amounts will do the trick.  Barring efficiency reasons with regards to
> odd sizes, I'm only interested in how the padded and non padded version
> could be equivalent.   Now utilizing matlab as my analysis tool.
> Given:
> 
>>> x=[0,1,2,3,4]
> x =
>      0     1     2     3     4
>>> y=fft(x)'
> 
> y =
>   10.0000
>   -2.5000 - 3.4410i
>   -2.5000 - 0.8123i
>   -2.5000 + 0.8123i
>   -2.5000 + 3.4410i
> 
> Now zero pad to the next power of two.
> 
>>> x=[0,1,2,3,4,0,0,0]
> x =
>      0     1     2     3     4     0     0     0
>>> y=fft(x)'
> 
> y =
> 
>   10.0000
>   -5.4142 + 4.8284i
>    2.0000 - 2.0000i
>   -2.5858 + 0.8284i
>    2.0000
>   -2.5858 - 0.8284i
>    2.0000 + 2.0000i
>   -5.4142 - 4.8284i
> 
> 
> How is the result from the result from the padded and non-padded
> version equivalent or is there my understanding flawed?

They are both sets of points on (samples of) the same underlying continuous
complex curve, just spaced differently.  The longer you pad your sequence
the closer the sample points get to each other in the frequency dimension.


Bob
-- 

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

                                             A. Einstein

Rick Lyons wrote:
[.....]

>
>   ah ha, you're startin' to learn about
> the discrete Fourier transform.  This is good.
Indeed.  How do you folks do it :)?   It seems intimidating - but I
suspect this is because I'm new to things so I have more questions than
answers.

[...]

>
> If you pad x with 2043 zero-valued samples and
> perform an 2048-point DFT you'll obtain 2048 samples
> of the full DTFT curve for the 5-sample sequence x.
> In this case, you'll have a very accurate
> (very highly sampled) representation of
> the true Fourier tansform of your original
> 5-sample x sequence.
>
> Hope that made some sense.
Got it.  If only I'd have seen that in the text.

Part of my curiosity stemmed from a project I'm perusing here,  where
taylor weights  ( still haven't quite gotten my head around what the
taylor window is buying me but I'll keep reading ) was precomputed.
The weights ( an array 32 deep ) were then applied (multiplied) to a
sequence - call it x of size 32..  An forward transform was run on the
result.

I'm thinking.. lets take this a step further.  How about a forward
transform 64 deep.  IOW:  zero pad to 64.  The question then became
would the result be the same?  I now konw my answer lies in your
paragraph above.

Thanks alot