AMAT 415 — Assignment 2 solutions

Here are the solutions to assignment 2: pdf

Please report any typos or errors to me by email.

AMAT 415 — Midterm 1 solutions

Here are the solutions for midterm 1: pdf

AMAT 415 — Letter grade conversion

Here are the numerical grades you need to achieve to be guaranteed given letter grade.

A+ 95-100
A 90-94.99
A- 85-89

B+ 80-84.99
B 75-79.99
B- 70-74.99

C+ 65-69.99
C 60-64.99
C- 55-59.99

D 50-54.99

F < 50

AMAT 415 — Hints for assignment 2

Here are some hints for assignment 2: pdf

Please report any errors or typos.

AMAT 415 — Aliasing and leakage

Here are the pictures I showed in class to illustrate aliasing and leakage.

AMAT 415 — Matlab activity 4: Reversing, shifting and convolution

(Added 2013.02.06: Here are a few hints: pdf)

In this activity we study the some basic operations on signals and their interaction with the discrete Fourier transform.

First, we will write a function that will reverse a signal.  That is, we want a function that takes a signal $x=(x_0,\ldots,x_{N-1})$ as input and outputs the signal $y$ defined by $y_n=x_{N-n}$ .  Select File>New>Function to pull up an editor window in which we can write our function.  Enter the following:

function y=rev(x)
N=length(x);
y=[x(1) x(N:-1:2)];
end

Here, rev (for reverse) is the name of our function.  The in the brackets represents the vector that we’re trying to reverse.  The y is the output of the function; this should be the reverse of x.  The two lines in the middle describe how to compute from x. (At this point, you should figure out why this accomplishes the task.) The end indicates the end of our function.  File>Save this file as rev.m. Now we can use rev in the command window just like any other MATLAB function.  Try it out on a few vectors x to make sure that it works.  Verify the identity we proved in class: $\mathcal{F}y=\overline{\mathcal{F}\bar{x}}$.

Now it’s your turn.  Select File>New>Function again. Please write a function — call it shift — that cyclically shifts the entries of a vector m places to the right.  That is, given a signal $x=(x_0,\ldots,x_{N-1})$, we want to calculate the signal $y$ defined by $y_n=x_{n-m}$.  Here, we always understand $n-m$ modulo $N$, meaning that if $n-m<0$, then $n-m$ means $n-m+N$.  The function shift that you are to write takes two inputs — x and m, so the first line of your function should be y=shift(x,m).  Its should be end.  As for how to actually get y from x, I want you to figure it out using the rev function as a guide.

The function you just wrote shifts components of a signal m places to the right.  We’d also like the flexibility to shift components m units to the left.  We could do one of two things.  We could write another function called leftshift or something that does this, but that would be wasteful.  Shifting each component of an N element signal m positions to the left (cycically!) is the same as shifting each component of our signal ??? units to the right.  (What is ???).  So you can use your existing shifting function to do left shifts, too.

We proved in class that if $y_n=x_{n-m}$, then $(\mathcal{F}y)_n=(\mathcal{F}x)_n e^{-2\pi i nm/N}$.  Verify this formula for various x and m. For example:

x=1:6;
y1=fft(shift(x,N-2));
y2=fft(x).*exp(2*pi*i*(0:5)*2/6);

Now let’s write a convolution function. Again, select File>New>Function to open a new editor window.  We will write a function conv that takes as input two signals x and y and outputs the convolution z of and y.  I would suggest starting out by initializing your eventual answer z and filling in the first entry:

z=zeros(1,size(x)); (double check that)
z(1) = sum(x.*rev(y));

You could then proceed with a for loop:

for n=2:N
z(n)=sum(x.*shift(rev(y),???));
end for

You are not obligated to code it as I suggest.  Just don’t do it in such a way that if defeats the purpose of the next part.

To check that our conv works, we can use the relationship between convolution, pointwise multiplication under the Fourier transform: conv(x,y) and ifft(fft(x).*fft(y)) should be equal.  Check this for a few vectors x and y.

Now that we have a nice functional convolution function, we can use it to investigate some signals.  First, let’s see what the effect of convolution in the frequency domain on a signal in the time domain.  Let t=0:0.02:0.98; and let x=cos(2*pi*4*t)+3*cos(2*pi*10*t);. Have a look at x and fft(x) using a stem plot and explain why it looks how it looks.  Let’s kill one of the peaks as follows.  Set w=((1:50)<8)+((1:50)>42); and let xx=conv(x,ifft(w)).  (This should give you the same vector as xx=ifft(fft(x).*w);.) Make a stem plot of xx.  What function does the plot resemble? More precisely, what simple function, when sampled 50 times per second, gives xx? Check your guess (using MATLAB, of course). Explain what’s going on in a few sentences.

Please submit the following along as part of Assignment 2:

• your code for the shift and conv functions
• a few examples verifying that your code works
• your stem plots of x and xx and your few sentences of explanation.

Optional/time permitting: We just looked at an example of pointwise multiplication in the frequency domain and the corresponding convolution in the time domain.  Let’s consider, on the other hand, pointwise mutliplication in the frequency domain.  Set y=sin(2*pi*4*t); and v=(1:50)<26;. Have a look at stem(t,y) and stem(t,y.*v) as well as at stem(fft(y)) and stem(abs(fft(y.*v))).  Since the Fourier transform maps pointwise multiplication to convolution, fft(y.*v)=conv(fft(y),fft(v)). The signal y.*v is a “zero padded” sine wave.  Zero padding in the time domain corresponds to convolution with fft(v) in the frequency domain.  Functions like fft(v) are important and we’ll be seeing them more later.

AMAT 415 — Assignment 2

For Assignment 2, please submit MATLAB activity 4 (worth 4 points) and the following problems: P12, P14, P15, P22, P24 (worth 2 points each).

Handwritten is fine, but it should be neat and legible. Staples are preferable to paperclips.

Hand in your work at the beginning of your tutorial on Tuesday, February 12. If you can’t make it to the tutorial, be sure to get the assignment to me before noon on Tuesday.

AMAT 415 — Week 5 problems

P20) Find all the solutions of the following equations: (a) $z^2=-9i$, (b) $z^3=i$, (c) $z^4=-2$.

P21) Suppose $y=(7.00000, y_1, 0.61803, y_3, -1.61803)$ is the discrete Fourier transform of a real signal $x$. Find $y_1$, $y_3$, and $x$.

P22) Suppose $x=(x_0,x_1,x_2,x_3)\in \mathbf{C}^4$ be a real signal with Fourier transform $\mathcal{F}x=(2,-4,6,-4)$. Find $\mathcal{F}y$ and $\mathcal{F}z$, where $y=(x_2,x_3,x_0,x_1)$ and $z=(x_2,x_1,x_0,x_3)$. (Hint: Relate $y$ and $z$ to $x$ using shifts and time-reversals.)

P23) Without explicitly calculating any Fourier transforms, find $\mathcal{F}(\mathcal{F}x)$, where $x=(2,3,5,7,11,13,17,19)$.

P24) Let $\delta=(1,0,\ldots,0)$ and let $0. Let $y_n=\delta_{n-k}$ and let $z_n=\delta_{n-\ell}$. Compute the imaginary part of $\hat{y}_n + \hat{z}_n$. Bonus: Under what condition is this imaginary part equal to zero?

P25) Let $N$ be even and suppose $0. Find $\mathcal{F}\{\cos(2\pi mn/N)\}$, $\mathcal{F}\{\sin(2\pi mn/N)\}$, and $\mathcal{F} \{\cos(2\pi mn/N+\varphi)\}$.

P26) Find the complex and real Fourier series $f(t)$ where $f(t)$ is the function of period $2\pi$ satisfying $f(t)=\cos(t/2)$, $-\pi.

P27) Suppose $0<\alpha<\pi$. Find the complex and real Fourier series of the function $f(t)$ where $f(t)$ is the function of period $2\pi$ satisfying $f(t)=1$ if $|t|\leq\alpha$ and $f(t)=0$ if $\alpha<|t|\leq \pi$.  (Start by drawing a picture of $f(t)$.)

AMAT 415 — Week 4 problems

P15) Finite, sampled signals $x$ and their discrete Fourier transforms $\hat{x}$ both live in $\mathbf{C}^n$ — a vector space. Show that the DFT respects basic vector space operations — addition and scalar multiplication.  More precisely, show that (a) if $x$ and $y$ are signals in $\mathbf{C}^n$ and $z=x+y$, then $\hat{z}=\hat{x}+\hat{y}$, and (b) if $x \in\mathbf{C}^n$, $a\in\mathbf{C}$ is a scalar, and $y=ax$, then $\hat{y}=a\hat{x}$.

P16) Let $x=(-1,2,5)$ and $y=(2,3,5,7)$.  Calculate $\hat{x}$ and $\hat{y}$.

P17) Let $\omega= e^{2\pi i/N}$ and let $A$ be the $N\times N$ matrix whose $(i,j)$-th entry is $\omega^{-(i-1)(j-1)}$, $i,j=1,\ldots,N$. Show that (a) $A$ is a symmetric matrix; (b) $A^{-1}=N^{-1}\bar{A}$, where $\bar{A}$ is the matrix obtained by conjugating each entry of $A$; (c) if we view $x\in \mathbf{C}^N$ as a column vector, then $\hat{x}=Ax$.

P18) Write down the matrix $A$ of the previous problem in the case $N=4$. (Each entry should be expressed in standard for $x+iy$.) Use it to compute $\hat{y}$ and $\hat{z}$, where $y=(2,3,5,7)$ and $z=(2,4,6,8)$.

P19) Make some stem plots of the modulus of $\hat{x}$, where $x=(1,\ldots,1,0,\ldots,0)$ where the string of ones has length $m$ and the string of zeroes has length $N-m$. (We computed $\hat{x}$ in class, but you should check it with MATLAB.)

AMAT 415 — Matlab activity 3: Fourier series via FFT

This activity is meant to be instructive.  I won’t ask you to submit your code or plots.

Let $x=(x_0,\ldots,x_{N-1})$ be an $n$-element vector. Its DFT is the vector $y=(y_0,\ldots,y_{N-1})$ defined by

$\displaystyle{y_n=\sum_{k=0}^{N-1}x_ke(-nk/N)}$,

where $e(x)=e^{2\pi i x}$. (In class yesterday, we had a factor of $1/N$ in front of the above sum. I’m dropping this because MATLAB uses different conventions.) Suppose $x_k=f(2\pi k/N)$ for some function $f$ defined on $[0,2\pi]$. Then

$\displaystyle{y_n=\frac{N}{2\pi}\sum_{k=0}^{N-1}f(2\pi k/N)e^{-in(2\pi k/N)}\frac{2\pi}{N}}$.

The sum in this expression is a “left endpoint” Riemann sum approximation to $\displaystyle{\int_0^{2\pi}f(t)e^{-int}dt}$ using a subdivision of $[0,2\pi]$ into $N$ equal subintervals of width $2\pi/N$. Thus, $y_n\approx N\hat{f}(n)$. This means that we can approximate the Fourier coefficients of a function $f(t)$ by computing the DFT of the vector $x$ with $x_k=f(2\pi k/N)$.

The Fast Fourier Transform is an algorithm for computing the DFT very efficiently. In MATLAB, invoking fft(x) gives you the DFT of the vector x. (Note that MATLAB indexes vectors starting from 1 rather than from 0. From the perspective of the mathematics of the DFT, it’s better to start indexing from 0 as above. Keep this shift in mind.) Let’s repeat some of the calculations of last week’s lab using the fft command. The FFT algorithm works best on vector of length $2^n$. So let N=2^7, say, and set t=0:2*pi/N:(2*pi-2*pi/N);. We’ll start with the step function x=t<pi;. Let y be its DFT, i.e., set y=fft(x);. Now let’s try to reconstruct x from y. Initialize the vector and, for various small values of m, perform:

s=zeros(1,length(x));
for k=1:m
s = s + y(k)/N*exp(i*(k-1)*t);
end
plot(t,real(s))

Do the graphs look right? Plot x and s on the same graph: plot(t,x,t,s). Something’s off. What’s going on?

Let’s try a different function. Let x=[t(1:N/2) t(N/2)-t(1:N/2)];. (Plot it and figure out why the command you just pasted in gives you the graph you see.) Now run through the above process with this x. Still doesn’t look right…

Wait a second. The Fourier series of a function $f$ is $\displaystyle{\sum_{n=-\infty}^\infty \hat{f}(n)e^{int}}$. We’ve been ignoring the terms with $n<0$. No wonder our pictures are wrong! Even though $y_{n}$ for $n<0$ doesn’t make sense, we recall that if $f(t)$ is real-valued, then $\hat{f}(-n)=\overline{\hat{f}(n)}$.  Let’s take this into account:

s=zeros(1,length(x))+y(1)/N;
for k=2:m
s = s + y(k)/N*exp(i*(k-1)*t) + conj(y(k))/N*exp(i*(1-k)*t);
end
plot(t,real(s),t,x)

That’s more like it! Try a few more functions x like the ones you worked with last week.

Finally, I’d like to acquaint you with a nice command. Check out stem(y), stem(abs(y)) and compare them with plot(real(y)) and plot(abs(y)). Since DFTs are just N element vectors, a “plot” of them should just be N points not connected by lines. This is what stem gives you. It’s really nice for visualizing discrete signals in the frequency domain, especially when N isn’t too big so the circles it plots don’t start overlapping.  What interesting symmetries do you observe in these stem plots?