Super Freq

Assign: Wednesday, December 1

Due: Thursday, December 9

Assignment Policies

All assignments are partner assignments. Please make sure to review the policies and guidelines about discussing assignments with those other than your partner. Assignments are usually, but not always, a combination of paper and coded exercises. Please make two submissions (one for paper exercises and one for coded exercises) to Gradescope. Paper exercises are marked with HW to indicate a handwritten question and C to indicate a coded question. Paper submissions can receive an extra 2% bonus if they are typed. Please visit the tools section of the website for more information.

Handwritten Exercises

State whether the following signals are orthogonal:
1. $\sin(440\pi t)$ and $\sin(220\pi t)$
2. $\sin(200\pi t)$ and $\sin(200\pi t + \pi)$
3. $0.5\sin(480\pi)$ and $\sin(100\pi + \frac{3\pi}{2})$
4. $\sin(200\pi t)$ and $\cos(200\pi t)$
5. $0.5\cos(400\pi)$ and $0.75\cos(400\pi - \frac{\pi}{4})$
6. $\sin(50\pi t)$ and $0.2\sin(25\pi t - \pi) + 0.25\cos(50\pi t - \pi/2)$
Suppose some frequency bin $X_k$ has the complex value $0.25 - 0.25i$ based on 20 samples of some input signal.
Determine the phase and amplitude of that bin.
Suppose that a periodic, continuous waveform has a period of 0.01 seconds. What are the possible frequencies that could constitute that sound according to the Fourier Series?
Would the inner product of $f$ and $g$ be zero or non-zero if $f(t) = \sin(2\pi(10)t + \pi/4)$ and $g(t) = e^{2\pi(4)ti}$?

Sample Number	Amplitude
0	-0.1768
1	1.198
2	0.36503
3	-0.4743
4	-0.9119
5	-0.1768
6	1.198
7	0.36503
8	-0.4743
9	-0.9119

Consider the following samples below. These samples are taken from a periodic signal. The total samples are $N = 10$ and are taken at a sample rate $f_s = 10$Hz. The following questions ask you to perform the Discrete Fourier Transform on the samples below. Note that the periodic signal is periodic on the interval of 1 second and contains no frequencies at or above the Nyquist frequency.

Which bin $k$ corresponds to the Nyquist frequency? Explain.
What are the frequencies tested by bins $X_0$, $X_1$, $X_2$, $X_3$, and $X_4$?
For the following bins, determine the complex number at each bin. If non-zero, determine the amplitude and phase of the bin. If either the value of the real or imaginary component is of the order of $10^{-5}$ or smaller, assume that value is zero. Note that $\tan$ is undefined at $\pm \frac{\pi}{2}$. Be careful with the quadrant when determining phase.
1. $X_0$
2. $X_1$
3. $X_2$
4. $X_3$
5. $X_4$
Based on your answers to part(c), determine a mathematical equation to represent the original signal. It should be of the form $A_1\cos(2\pi f_1t + \phi_1) + A_2\cos(2\pi f_2t + \phi_2) + … + A_n\cos(2\pi f_nt + \phi_n)$.

Optional Challenge (Up to 25 BONUS Points)

Note that this challenge exercises is really a challenge! My answer took nearly three pages! It may be best to spend your time working on your final project. But for the interested it can provide an understanding for two of the equations I gave you in class. Note that you can of course receive partial credit for any progress you make. You may only ask Andy for help on this question and he will only provide vague responses. This is to be almost entirely your work alone.

Background

I asserted that the amplitude and phase of any frequency bin could be reconstructed as a cosine wave using $A = \frac{2}{N}\sqrt{a^2 + b^2}$ and $\phi = \tan^{-1}(\frac{b}{a})$ for complex bin $a + ib$. In this challenge, you will derive these two equations.

We discussed in class that continuous sinusoids that are periodic along some distance of time $L$ are not orthogonal when the frequencies are the same (assuming they are not out of phase by $\pi/2$) and orthogonal otherwise. The same is true for sampled sinusoids with some caveats. If we look at the Discrete Fourier Transform, the frequency of the complex exponential is wrapped up in the term $\frac{kn}{N}$. Remember the DFT is as follows:

$X_k = \frac{1}{N}\sum_{n = 0}^{N - 1}x[n]e^{-2\pi nki/N}$

How is the frequency wrapped up in the term $\frac{kn}{N}$? Remember that with the DFT the only valid frequencies of some periodic signal are harmonics. We expressed this as $f = k/L$ where $L$ is some span of time that a sinusoid is periodic on and $k$ is the number of complete oscillations along that time period $L$, making the sinusoid a harmonic. Because we are sampling this sinusoid with $N$ samples, we can say that $L = \frac{N}{f_s}$ where $f_s$ is the sample rate. Therefore, $f = \frac{kf_s}{N}$. Additionally, time $t$ can also be thought of in terms of samples as well. We can say $t = \frac{n}{f_s}$ and now time has been quantized in terms of the $n$th sample. In a continuous sinusoid like $\cos(2\pi ft)$, frequency and time are separated. If we replaced $f$ and $t$ with the above equations, we can say that a sampled sinusoid is actually $\cos(2\pi\frac{kn}{N})$. As you can see then in the DFT, $\frac{kn}{N}$ encodes the information for both time and frequency.

Assuming we are dealing with only periodic signals (no possibility of spectral leakage), then a frequency bin will only have a non-zero magnitude when one of the harmonics of the signal matches the frequency of the frequency bin, just as in the continuous case. Therefore, let’s perform the DFT on the signal $A\cos(2\pi \frac{kn}{N})$ for the bin $X_k$. We should have the following:

$A\sum_{n = 0}^{N - 1}\cos(2\pi \frac{kn}{N} + \phi)e^{-2\pi nki/N}.$

Question

Determine the complex number generated by this equation in the form $a + bi$. Reduce the complex number to its simplest form.
From $a + bi$ show that $A = \frac{2}{N}\sqrt{a^2 + b^2}$ and $\phi = \tan^{-1}(\frac{b}{a})$. Under what conditions?

Useful Identities

Note that it will be helpful to use the following two identities that you can use to help solve this question:

$\sum_{n=0}^{N - 1}\cos(2\pi fn) = \frac{\cos(\pi f(N - 1))\sin(\pi fN)}{\sin(\pi f)}$

$\sum_{n=0}^{N - 1}\sin(2\pi fn) = \frac{\sin(\pi f(N - 1))\sin(\pi fN)}{\sin(\pi f)}$

Submission

Feedback

When you are finished with the problem set, please fill out the form linked here to provide feedback on how long the problem set took you and how difficult you found it. Note that you must fill out this form to receive credit for the problem set.

Submission Guidelines

All assignments in this course are submitted through Gradescope. There are two kinds of assignments in this course: paper assignments and code assignments. Both are submitted to Gradescope. Most assignments are a mix of code and paper assignments. Each question or question part will be marked either “code” or “paper” to indicate which kind of question it is. For paper assignments, note that typed answers will receive a small additional bonus of 2%.