# Find Discrete Fourier transform given the inverse

I don't know if this question is already answered somewhere else but I'm stuck with that and I need help...

Given an inverse Discrete Fourier Transform (IDFT), with N=16 :

How can I find the F(k) that represent the Discrete Fourier Transform (DTF)? $$F(k) = \sum_{n=0}^{N-1} f(n) e^{-i2\pi \frac{kn}{N}}$$

And how the plot of F(k) will be?

EDIT: for now this is my result but I have no idea if it's correct:

EDIT 2: plus I don't know how to plot the equation since it contains the imaginary number (j in the figure)...

• @ThP I edit my question with my the thing that I've tried Sep 15 '18 at 21:29

METHOD-I

Plain simple,

The discrete-time sequence you have provided is :

$$f[n] = \begin{cases} 1 ~~~,~~~\text{ for } n = 0,1,2,14,15 \\ 0 ~~~,~~~ \text{ otherwise } \end{cases}$$

which is also described as a sum of discrete-time unit impulses located for each $n=0,1,2,14,15$ as

$$f[n] = \delta[n] + \delta[n-1] + \delta[n-2] + \delta[n-14] + \delta[n-15]$$

Using the fact that, the N-point DFT of the unit-impulse located at $n=d$ is: $$\boxed{ \delta[n-d] \longleftrightarrow X[k] = e^{-j \frac{2\pi}{N} k d} }$$

Then employ linearity property of DFT, to get the N-point DFT of $f[n]$ as:

$$F[k] = e^{-j \frac{2\pi}{N} k 0} + e^{-j \frac{2\pi}{N} k 1} + e^{-j \frac{2\pi}{N} k 2} + e^{-j \frac{2\pi}{N} k 14} + e^{-j \frac{2\pi}{N} k 15}$$

which becomes with $N = 16$: $$F[k] = 1 + e^{-j \frac{\pi}{8} k} + e^{-j \frac{\pi}{4} k} + e^{-j \frac{\pi}{8} 14 k} + e^{-j \frac{\pi}{8} 15 k}$$

Now, not always possible but in this case you can merge those complex exponentials, after replacing the frequency of the the latter two according to the following.

$$e^{-j \frac{\pi}{8} 14 k} = e^{-j \frac{\pi}{8} (16-2) k} = e^{-j 2\pi k} e^{j \frac{\pi}{4} k} = e^{j \frac{\pi}{4} k}$$

and similarly $$e^{-j \frac{\pi}{8} 15 k} = e^{-j \frac{\pi}{8} (16-1) k} = e^{-j 2\pi k} e^{j \frac{\pi}{8} k} = e^{j \frac{\pi}{8} k}$$

Then the DFT $F[k]$ becomes: $$F[k] = 1 + e^{-j \frac{\pi}{8} k} + e^{-j \frac{\pi}{4} k} +e^{j \frac{\pi}{8} k} + e^{j \frac{\pi}{4} k}$$

Now combine those exponentials, with conjugate angles, into cosine terms according to $2 \cos(\omega n) = e^{j \omega n} + e^{-j \omega n}$ to conlcude: $$\boxed { F[k] = 1 + 2 \cos( \frac{\pi}{4} k) + 2 \cos( \frac{\pi}{8} k) ~~~,~~~\text{ for } k = 0,1,2,...,15}$$

Which is a real and (circularly) even function of $k$, as the sequence $f[n]$ is (circularly) even-symmetric and real.

METHOD-II

if you prefer a fancier approach, then you can also use this. By inspection, one can see that $f[n]$ is given by a circular left shift of another sequence $g[n]$ (i.e., $f[n] = g[n+d]$) where and $g[n]$ is

$$g[n] = \begin{cases} 1 ~~~,~~~\text{ for } n = 0,1,2,3,4 \\ 0 ~~~,~~~ \text{ otherwise } \end{cases}$$

and $d=2$. Then the N-point DFT of $f[n]$ and N-point DFT of $g[n]$ are related by (with $N=16$):

$$F[k] = e^{j \frac{2\pi}{N} d k} G[k] ~~~,~~~\text{ for } k = 0,1,2,...,N-1 \\ F[k] = e^{j \frac{\pi}{4} k} G[k] ~~~,~~~\text{ for } k = 0,1,2,...,15 \\$$

Ffurthermore, the N-point DFT of $g[n]$ is found as: $$G[k] = \sum_{n=0}^{4} 1 \cdot e^{-j \frac{2\pi}{16}nk} = \frac{ 1 - e^{-j \frac{5 \pi}{8} k} }{ 1 - e^{-j \frac{\pi}{8} k} }$$

Finally the N-point DFT $F[k]$ of $f[n]$ becomes $$\boxed{ F[k] =e^{j \frac{\pi}{4} k} \left( \frac{ 1 - e^{-j \frac{5 \pi}{8} k} }{ 1 - e^{-j \frac{\pi}{8} k} }\right) ~~~,~~~\text{ for } k = 0,1,2,...,15 }$$

Which should yield the same result.

• Thank you very much for the explanation; I didn't know that I can merge these complex exponentials. :) Sep 15 '18 at 22:22
• yes you can with the Euler identiy. Also work on the method-II, as it's found to be useful in various places... Sep 15 '18 at 22:25