2
$\begingroup$

While reading a description on FFT from this book, I found the following statement:

...diluting the time domain with zeros corresponds to a duplication of the frequency spectrum.

How can I prove this intuitively or otherwise? I have read some properties of Fourier Transform, such as a circular shift in time domain and frequency domain etc, but I am unable to deduce how duplication in frequency domain will happen. Following illustrate this:

Time domain samples 

x(0)=a x(1)=b x(2)=c x(3)=d

Frequency domain samples 

X(0)=A X(1)=B X(2)=C X(3)=D

Dilution with 0 in time domain 

x(0)=a x(1)=0 x(2)=b x(3)=0 x(4)=c x(5)=0 x(6)=d x(7)=0

Frequency domain samples having duplicate values 

X(0)=A X(1)=B X(2)=C X(3)=D X(4)=A X(5)=B X(6)=C X(7)=D

Frequency domain samples have duplicate values. Why?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Why don't you write out the explicit equations for $X[i], 0 \leq i \leq 3$ in the first case -- no summation signs, just the sum of four terms -- and compare to the explicit equations for $\hat{X}[i], 0 \leq i \leq 7$ in the second case, again written out in detail without any summation signs and taking advantage of the fact that $\hat{x}[i] = 0$ for $i$ odd and $\hat{x}[2i] = x[i], i = 0,1,2,3$? $\endgroup$ Commented Apr 4, 2013 at 15:34
  • $\begingroup$ This answer may help- dsp.stackexchange.com/a/1781/923 $\endgroup$ Commented Apr 5, 2013 at 13:38

1 Answer 1

Reset to default
2
$\begingroup$

Unfortunately I can't come up with an intuitive explanation for this, but lemme try to prove this. During reading please be very careful with indexes as they can be confusing! I use zero-based indexing. And please correct me if I'm wrong.

Let eq1 be our undiluted time domain of N elements.

So, diluted vector looks like this: eq2

Frequency spectrum of x is given by eq3.

Frequency spectrum of y, teh diluted x is eq4. Note the length of Y equals 2N.

Now I'd like to prove that the right half of the diluted frequency domain is "copied" from the left half, that is eq5. I guess it's sufficent to prove only the last equation, but the first two are good for grasping the idea.

By expanding a sum for Y[0] and Y[N] we get:

eq6

eq7

The fact that Y[0] and Y[N] are equal can easily be seen by noticing that eq8 because of it's periodic nature- see Euler's relation: euler's relation. Later we will exploit this property of exp(j*phi) to "move" exponent back or forward by 2nPi.

The next (unnecessary, but good to examine) step is to prove that Y[1] = Y[N+1]. Let's expand: eq10 eq11

Because Y[1] = Y[N+1] must hold regardless of x values, the only way that it can do so is when exponents next to proper xn's are equal. Let's prove that eq12. If we can do this, then when a=0, we prove that exponents next to x0 in Y[1] and Y[N+1] are equal. When a=1, exponents near x1 are proven to be equal and so on, until a=N-1.

eq13

As you can see, it was not hard. It's more like showing than proving. If you are wondering why did 2pi*a dissapear, look again at the Euler's relation and maybe rewrite the middle step of the proof in cos - isin form. It should be clearer now that you can add or subtract 2pi from argument of the sine or cosine function without affecting it's value.

Okay, let's move on to the next, (the only necessary) part. Y[k]=Y[k+N]. eq14 enter image description here

Like the last time, let's show equality of exponentials near xn's: eq16

The idea is the same, only the last point has the least numbers and the most variables, making it the most general case. It's general enough that I think it's the end of the proof.

Hope it helps :)

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.