How to prove that Dilution of a time domain signal results in duplication in Frequncy domain?

Question

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?

Answer 1

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 be our undiluted time domain of N elements.

So, diluted vector looks like this:

Frequency spectrum of x is given by .

Frequency spectrum of y, teh diluted x is . 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 . 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:

The fact that Y[0] and Y[N] are equal can easily be seen by noticing that because of it's periodic nature- see 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:

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 . 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.

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].

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

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 :)