# Discrete Fourier Transform by hand

I have an assignment where I'm given the DFT of a sequence $x[n]$ as $X[k]=\{4,3,2,1,0,1,2,3\}$ and also $$y[n] = \left\{ \begin{array}[cc] xx[n/2] & \text{if n is even} \\ 0 & \text{otherwise} \end{array} \right.$$

and I'm supposed to find and sketch the DFT of $y[n]$.

So $y[n] = \{x[0], 0, x[1], 0 ... x[7], 0\}$ and it's not complicated to find $Y[k]$ if we know $x[n]$

I know how to use the definition of the DFT and IDFT to calculate $x[n]$ but it's a tedious task to do by hand, especially when the sequence is longer than a few items. Is there a quicker way to calculate the DFT and IDFT by hand without using a program like Matlab?

• Hint: start by figuring out the $z$-transform of this system. Oct 2, 2014 at 19:33
• I'm sure your class covered that special case of inserting zeros into a time domain representation as it is used for upsampling. The effect this procedure has on the spectrum of the signal is rather simple. So I'd suggest you look that up and use it to answer the question. If you know how it works this question takes 10 seconds to do. Oct 3, 2014 at 10:24

$$Y[k] = \sum_{n=0}^{2N-1}y[n]e^{\frac{-2\pi k n}{2N}}$$ Now, substituting the definition of $y[n]$ you get:
$$Y[k] = \sum_{n=0}^{N-1}x[n]e^{\frac{-2\pi k (2n)}{2N}} = \sum_{n=0}^{N-1}x[n]e^{\frac{-2\pi k n}{N}}$$
So, for $0\leq k < N$ you get that $$Y[k] = X[k]$$ and for $k\geq N$ you get $$Y[k] = \sum_{n=0}^{N-1}x[n]e^{\frac{-2\pi k n}{N}} = \sum_{n=0}^{N-1}x[n]e^{\frac{-2\pi (k-N) n}{N}} = Y[k-N]$$
Therfore, $$Y[k] = \begin{cases}X[k] & 0\leq k < N \\ X[k-N] & k\geq N\end{cases}$$ or $X[k]=\{4,3,2,1,0,1,2,3,4,3,2,1,0,1,2,3\}$