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 onedimensional 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}^{N1} f_k \cdot e^{2 \pi j r k / N} \\
& = \frac{1}{N} \sum_{k=0}^{N1} f_k \cdot \cos \left(2 \pi \frac{r k}{N} \right) \\
& \quad + \frac{j}{N} \sum_{k=0}^{N1} 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]$.
 Use your spreadsheet program to graph and present the DFT of
 $f_k=const$
 the fullperiod sine wave $f_k=\sin(sk)$ where $s$ is $2\pi/N$
 a sum of fullperiod sine with halfamplitude
quadruplefrequency sine, i.e. $f_k=\sin(sk)+0.5 \cdot \sin(4sk)$ where $s$
is $2\pi/N$
 a squarewave 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.
 Discuss the results:
 What does $F[r=0]$ represent? (proof!)
 Explain the apparent symmetry $\left F[r] \right = \left F[Nr] \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?
 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.
 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
fullphase 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}^{N1} 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.
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 09212017 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.