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
• $f_k=const$
• the full-period sine wave $f_k=\sin(sk)$ where $s$ is $2\pi/N$
• a sum of full-period sine with half-amplitude quadruple-frequency sine, i.e. $f_k=\sin(sk)+0.5 \cdot \sin(4sk)$ where $s$ is $2\pi/N$
• a square-wave with $f_k=0$ for $k$ from 0 to 9 and $f_k=+1$ for $k$ from 10 to 19.
• a DFT of $f_k$ where $f[k]=rand()$, i.e. random numbers or white noise.
2. Discuss the results:
• What does $F[r=0]$ represent? (proof!)
• Explain the apparent symmetry $\left| F[r] \right| = \left| F[N-r] \right|$ for $r>0$.
• What would the DFT coefficients $F[r]$ look like for $r \ge N$?
• What do you notice in the DFT of noise? Specifically: How fast (compared to, e.g., triangle, sine, or square wave) do the coefficients diminish with increasing frequency?
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:

• For the inverse discrete Fourier transform, note that you can once again write $e^{2 \pi j r k / N}$ as $\cos(2 \pi r k / N) + j \sin(2 \pi r k / N)$. Also, the exponent has a positive sign in the inverse transform, and there is no normalization term $1/N$ present.
• Keep in mind that the cosine is an even function, which means that $\cos(-x) = \cos(x)$, and that the sine is an odd function for which holds $\sin(-x) = -\sin(x)$.
• Finally, the periodicity of the sine and cosine functions can be expressed as $\sin(x + 2 \pi m) = \sin(x)$ (same for the cosine), where $m$ is any integer. This means that you can add and subtract multiples of $2 \pi$ to/from the argument without changing the function value.