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. Explain why you don't get $F[r=1]=1$ in the case of the sine wave. Hint: Notice that there are two nonzero coefficients. Specifically, $|F[r=-1]|=0.5$. This coefficient shows up in your calculation as $F_{19}$, but you can subtract $N$ from the index ($F_{19}=F_{-1}$). It is sufficient to show this behvior conceptually or qualitatively with reference to the summation that leads to the inverse DFT. For a more rigorous approach,
• Either use the cosine function instead of the sine function. The cosine function is an even function, and its Fourier coefficients are real and even (and you would not have to deal with $j$ in the IDFT)
• Or examine closely the results of your DFT spreadsheet. Specifically, write down the complex Fourier coefficients, i.e., $F_1 = 0 -j/2$ and $F_{-1}$ its complex conjugate. With these coefficients, the imaginary units $j$ cancel out in the IDFT summation.
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 sake of completeness, here is the equation for the inverse discrete Fourier transform. This is useful for Question 3. $$f_k = \sum_{r=0}^{N-1} F_r \cdot e^{+2 \pi j r k / N}$$ 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.