5
$\begingroup$

whats is the effect of pading zeroes to a sequence in FFT? for eg: x[n]=[2 3 4 5] corresponds to X[K]=[14 -2+2i -2 -2-2i]

while x[n]=[2 3 4 5 0 0 0 0] corresponds to X[K]=[14 0.58-9.65i -2+2i -3.414+1.65i -2 3.414-1.65i -2-2i 0.58+9.65i]

so what is the relation between X[0] , X[1] and X[2] in the new sequence?

please help

$\endgroup$
13
$\begingroup$

All that is happening when you zero-pad the input signal prior to a DFT, is that you are interpolating the frequency domain representation.

For example, you might get a certain shape as the output of your absolute magnitude of the DFT, and this shape has 10 points. If you zero-padded the input of your DFT to say, 100 points, you will get the same shape as before, but it will have more points, and will look smoother. That is all a zero-padding does for you. One may ask what type of relationship, and this relationship is simply a sinc-interpolation relationship.

A picture is worth a thousand words, so here you go:

enter image description here

As you can see, the shape of the DFT output (magnitude in this case) remains the same, but the granularity increases.

People will usually zero-pad for a variety of reasons:

  • Peak picking: A smoother DFT output allows a peak-picking algorithm to gain more accuracy as to the frequency of the actual peak.
  • Interpolation in the frequency domain for further processing downstream
  • Linear Convolution: If linear convolution is sought, then performing it as a multiplication of two spectra in the frequency domain means that the DFT outputs must be of length $N+M-1$, where $N$ is the length of the first signal, and $M$ is the length of the second signal it is being convolved with.
$\endgroup$
  • $\begingroup$ i Agree that the reaponse becomes more smoothened out But is there a Specific Relation Between the new terms due to padding? As in relation between 1st, 2nd and 3rd term of the new sequence of my example $\endgroup$ – Kaustubh Aug 12 '13 at 15:44
  • $\begingroup$ @Kaustubh You give me two points, 1 and 2. You ask me to interpolate between 1 and 2 such that I now have three points, 1, 1.5, and 2. What is the relationship between 1, 2, and 1.5? You might say, "This is the average of the two points". That is a form of linear interpolation with degree one. In this case it is the same, you are always doing an interpolation, but the relationship is given by the sinc-interpolator. $\endgroup$ – Tarin Ziyaee Aug 12 '13 at 18:30
3
$\begingroup$

Zero padding in the time domain corresponds to interpolation in the frequency domain (and vice versa). The specific relationship is sync interpolation, sometimes also known as Whittaker-Shannon interpolation.

http://en.wikipedia.org/wiki/Whittaker%E2%80%93Shannon_interpolation_formula

In case of the FFT the linear integral/sum has to be replaced with a circular sum. The formula works for both real and complex numbers.

$\endgroup$
0
$\begingroup$

They are more closely spaced high quality interpolations of the non-zero padded FFT result.

$\endgroup$
  • $\begingroup$ Yeah...agreed But is there a Specific Relation in the new terms? $\endgroup$ – Kaustubh Aug 12 '13 at 15:45
  • $\begingroup$ Not a specific relationship of just those 3 bins. A high quality interpolation of bin 1 will use more information than in bins 0 and 2 to do a higher degree or larger kernel interpolation. Might be close to halfway between, or potentially very different, depending on other nearby bins. $\endgroup$ – hotpaw2 Aug 12 '13 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.