# Upsampling DFT at frequency domain

Suppose we have a vector of length N of DFT, which every odd index (in frequency) equals 0:

$$X[k] = 0\quad \forall k:\, k\mod2\equiv1$$

What does that mean for the series in the time domain?

• Are you getting those zero bins by 2x expanding an already computed DFT ? – Fat32 Jul 1 '16 at 12:02

It can mean the following: Consider any signal $x_{N}[n]$ of length $N$, and form the length $2N$ signal $x_{2N}[n]$ by repeating a copy of $x_{N}[n]$, then compute $2N$-Point DFT of this new signal $x_{2N}[n]$ whose every odd bin will be zero. i.e. $$X_{2N}[k] = 0 ~~,~~ \text{for}~~ k=1,3,5...,2N-1$$

whose demonstration can be performed with the following Octave/Matlab code:

 N = 16;
x = randn(1,N);         % form an arbitrary signal x[n]
x2 = [x x];             % repeat it once
X2 = fft(x2,2*N);       % take DFT of length 2N
figure,stem(abs(X2));   % display the result


Therefore it can mean that if you are performing an $M$ point DFT on your original signal $x[n]$, the signal $x[n]$ could actually be periodic with $\frac M2$ for $M$ even.

A more mathematical derivation of the result can be seen as follows:

Consider a signal $x_N[n]$ of length $N$ and its repetition $x_{2N}[n]$ of length $2N$ such that $x_{2N}[n]=x_N[n \mod N]$ for $n=0,1,\ldots,2N-1$.

Let's denote $N$-Point DFT of $x_N[n]$ as $X_N[k]$ for $k=0,1,\ldots,N-1$ and $2N$-Point DFT of $x_{2N}[n]$ as $X_{2N}[k]$ for $k=0,1,\ldots,2N-1$:

\begin{align} &{\text{Start with defining $2N$-Point DFT of $x_{2N}[n]\ldots$}}\\ X_{2N}[k] &= \sum_{n=0}^{2N-1} {x_{2N}[n] e^{-j\frac{2\pi}{2N}nk}} \\ \\ &{\text{first split the sum and then substitude $n=n-N$ in the $2^{nd}$}}\\ &= \sum_{n=0}^{N-1} {x_{2N}[n] e^{-j\frac{2\pi}{N}n(k/2)}} + \sum_{n=N}^{2N-1} {x_{2N}[n] e^{-j\frac{2\pi}{2N}nk}} \\ \\ &{\text{recognise $x_{2N}[n]=x_N[n]$, $x_{2N}[n+N]=x_N[n]$ }}\\ &= \sum_{n=0}^{N-1} {x_{2N}[n] e^{-j\frac{2\pi}{N}n(k/2)}} + \sum_{n=0}^{N-1} {x_{2N}[n+N] e^{-j\frac{2\pi}{2N}(n+N)k}} \\ \\ &{\text{Expand the 2nd sum's multiplier factor}}\\ &= \sum_{n=0}^{N-1} {x_N[n] e^{-j\frac{2\pi}{N}n(k/2)}} + \sum_{n=0}^{N-1} {x_N[n] e^{-j\frac{2\pi}{N}(n+N)(k/2)}} \\ \\ &{\text{Replace $e^{-2j\frac\pi N}$ with $W_N$ for simplicity }} \\ &= \sum_{n=0}^{N-1} {x_N[n] W_N^{nk/2}} + W_N^{Nk/2}\sum_{n=0}^{N-1} {x_N[n] W_N^{nk/2}} \\ \\ &{\text{Recognise the sums as $N$-Point DFT $X[k]$ of $x[n]$, at $\frac k2$}}\\ &= X_N[k/2] + e^{-j\pi k} X_N[k/2] \\ \\ &= X_N[k/2] \cdot \big( 1 + (-1)^k \big) \\ \\ &= \begin{cases} 2 X_N[k/2] , &\scriptstyle{\text{k=0,2,4,...,2N-2 }}\\ 0 , &\scriptstyle{\text{k=1,3,5,...,2N-1 }}\\ \end{cases} \end{align}

Shows that for such a defined signal , its odd DFT bins will be zero...

• Thanks, but why is what your'e saying true mathematically? – Codevan Jul 1 '16 at 12:10
• ok let me put a more rigorous explanation... – Fat32 Jul 1 '16 at 12:21

If only the even numbered FFT bins are non zero, then the time domain is the sum of only the even numbered basis vectors. The left and right half side of all the even numbered DFT basis vectors are identical to the other half side, so must be the sum, and thus the time domain signal.