Here are the solutions to assignment 2: pdf
Please report any typos or errors to me by email.
Here are the solutions to assignment 2: pdf
Please report any typos or errors to me by email.
Here are the numerical grades you need to achieve to be guaranteed given letter grade.
F < 50
Here are some hints for assignment 2: pdf
Please report any errors or typos.
(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 as input and outputs the signal defined by . Select File>New>Function to pull up an editor window in which we can write our function. Enter the following:
Here, rev (for reverse) is the name of our function. The x 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 y 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: .
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 , we want to calculate the signal defined by . Here, we always understand modulo , meaning that if , then means . 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 , then . Verify this formula for various x and m. For example:
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 x 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:
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:
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.
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.
P20) Find all the solutions of the following equations: (a) , (b) , (c) .
P21) Suppose is the discrete Fourier transform of a real signal . Find , , and .
P22) Suppose be a real signal with Fourier transform . Find and , where and . (Hint: Relate and to using shifts and time-reversals.)
P23) Without explicitly calculating any Fourier transforms, find , where .
P24) Let and let . Let and let . Compute the imaginary part of . Bonus: Under what condition is this imaginary part equal to zero?
P25) Let be even and suppose . Find , , and .
P26) Find the complex and real Fourier series where is the function of period satisfying , .
P27) Suppose . Find the complex and real Fourier series of the function where is the function of period satisfying if and if . (Start by drawing a picture of .)
P15) Finite, sampled signals and their discrete Fourier transforms both live in — a vector space. Show that the DFT respects basic vector space operations — addition and scalar multiplication. More precisely, show that (a) if and are signals in and , then , and (b) if , is a scalar, and , then .
P16) Let and . Calculate and .
P17) Let and let be the matrix whose -th entry is , . Show that (a) is a symmetric matrix; (b) , where is the matrix obtained by conjugating each entry of ; (c) if we view as a column vector, then .
P18) Write down the matrix of the previous problem in the case . (Each entry should be expressed in standard for .) Use it to compute and , where and .
P19) Make some stem plots of the modulus of , where where the string of ones has length and the string of zeroes has length . (We computed in class, but you should check it with MATLAB.)
This activity is meant to be instructive. I won’t ask you to submit your code or plots.
Let be an -element vector. Its DFT is the vector defined by
where . (In class yesterday, we had a factor of in front of the above sum. I’m dropping this because MATLAB uses different conventions.) Suppose for some function defined on . Then
The sum in this expression is a “left endpoint” Riemann sum approximation to using a subdivision of into equal subintervals of width . Thus, . This means that we can approximate the Fourier coefficients of a function by computing the DFT of the vector with .
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 . 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 = s + y(k)/N*exp(i*(k-1)*t);
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 is . We’ve been ignoring the terms with . No wonder our pictures are wrong! Even though for doesn’t make sense, we recall that if is real-valued, then . Let’s take this into account:
s = s + y(k)/N*exp(i*(k-1)*t) + conj(y(k))/N*exp(i*(1-k)*t);
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?