ENGR4620/6620: HOMEWORK 2

The Fourier Transform

The learning goal of this homework is to understand the representation of some selected signals in frequency space and to learn the significance of the Fourier coefficients. Also, the spreadsheet realization is a good visual way to appreciate how the discrete Fourier transform is computed.

Please use a spreadsheet program (e.g. LibreOffice/OpenOffice Spread or MS Excel) to compute a one-dimensional discrete Fourier transform (DFT) with N=20 sample points (numbered k=0...19). One possible way to set up a DFT is to have k and f(k) in two leftmost columns. To the right, each summation for components r=0...19 is performed in a separate column. As a consequence, the DFT components reside in a row below the summation elements. This summation needs to be performed twice, once for the real component and once for the imaginary component. We are interested in the magnitude of the complex number. Here is the equation for the DFT:

$$ \begin{split} F_r &= \frac{1}{N} \sum_{k=0}^{N-1} f_k \cdot e^{-2 \pi j r k / N} \\ & = \frac{1}{N} \sum_{k=0}^{N-1} f_k \cdot \cos \left(-2 \pi \frac{r k}{N} \right) \\ & \quad + \frac{j}{N} \sum_{k=0}^{N-1} f_k \cdot \sin \left( -2 \pi \frac{r k}{N} \right) \end{split} $$

(note: you need to have Javascript enabled for the equation to display correctly)

Create independent "computation engines" for the real and imaginary components, respectively. Note that both parts look very similar, except that the real part uses the cosine where the imaginary part uses the sine. Finally, combine both to obtain $|F_r| = \sqrt{\Re (F_r)^2+ \Im (F_r)^2}$. Plot both $f_k$ over $k$ and $|F_r|$ over $r$. You may alternatively plot $\Re(F_r)$ and $\Im(F_r)$ over $r$ if you wish to examine the odd and even parts separately.

Calibrate and possibly correct the computations using test signals: a constant signal of intensity one ($f_k = 1 \forall k$) should yield $F[r=0]=1$ and $F[r>0]=0$. A sine wave that extends over all 20 points should result in a peak at $F[r=1]$, but there should also be a peak at $F[r=19]$.

  1. Use your spreadsheet program to graph and present the DFT of
  2. Discuss the results:
  3. Show in a simple example that the inverse Fourier transform exactly restores the input signal. For this purpose, choose either the sine function above, $f_k = \sin(2 \pi k/N)$ or the corresponding cosine, $f_k = \cos (2 \pi k/N)$. Write down the complex Fourier coefficients that are not zero. Now apply the inverse DFT, $$ f_k = \sum_{r=0}^{N-1} F_r \cdot e^{+2 \pi j r k / N} $$ and show that the resulting $f_k$ matches the function you started with.
  4. Assuming that the data points were sampled at intervals of 10 ms, what is the highest frequency in your diagram (hint: at r=10 due to the symmetry)? What is the frequency of the full-phase sine wave? What are the frequencies at r=0, 1, ...?

Hints:

Grading

This homework will give you a maximum of 20 points towards your total score, 8 points from item 1 and 4 points each from items 2 - 4.

Due date and turnin

Homework is due on 09-21-2017 on eLC. Please note that eLC accepts only one comprehensive file (data and summary of observations).

Late turnin penalty: For each late day, you lose 1 point from your total score.

Early turnin bonus: If your homework is done before the due date, you may present your work for a brief evaluation. If I find significant errors, I will point those out and return the homework to you for revision. You may turn in a revised version by the due date.