# 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. – Phonon Oct 2 '14 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. – Jazzmaniac Oct 3 '14 at 10:24

If you use the DFT formula, you get:
$$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\}$

• Hi, I just came across this answer and had a few questions. How come you replaced N+1 with 2N +1 (is this because the length of Y(k) is twice as long?) Why is there no "i" term in the DFT formula? How come the 2N+1 disappeared the the second step. Is the final result X[k] supposed to be Y[k]? – Tim Mottram May 24 '18 at 9:03

For getting $n=0\ldots N$ we simply substitute values:

$y[0]=x[0], y[1]=0,y[2]=x[1],y[3]=0;y[4]=x[2],y[5]=0, y[6]=x[3],y[7]=0$

now use the formula:

$$F[n]=\sum_{k=0}^{N-1}x[k]e^{\dfrac{-j2\pi kn}{N}}$$

• That's what I mentioned in the OP, but doing that means calculating values k*n times (here 8*8=64). That takes a long time by hand and I was wondering if there was a quicker way to do it by hand. – dingari Oct 3 '14 at 8:41
• what about matlab code? fft(x,N) – dato datuashvili Oct 3 '14 at 9:14
• I know how to do it in Matlab, but the question is from last years final exam and they don't allow computers during such exams so there must be a better way to do it by hand. That's what I was asking for; How to do it by hand. – dingari Oct 3 '14 at 10:06
• by hand means by formula, so use this formula.of course in exam they will not give you 1000 data,what you can do you may apply fast Fourier transform in case of sample length if power of 2 – dato datuashvili Oct 3 '14 at 10:23