1
$\begingroup$

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 : enter image description here

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: enter image description here

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

$\endgroup$
  • $\begingroup$ @ThP I edit my question with my the thing that I've tried $\endgroup$ – toom501 Sep 15 '18 at 21:29
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.