Contents
Homework 6, ECE438, Fall 2010, Prof. Boutin
Due in class, Friday October 15, 2010.
The discussion page for this homework is here. Feel free to share your answers/thoughts/questions on that page.
Question 1
Consider the signal
$ x[n]=\cos \left( \omega_1 n \right)+ k \cos \left( \omega_2 n \right) $
where k is a real-valued constant.
a) Write a program that will
- Plot x[n].
- Compute the N point DFT X[k]. (Yes, you may use FFT routines.)
- Plot the magnitude of X[k].
Turn in a print out of your code.
b) Run your program and generate outputs for the cases shown below.
| Case | N | $ \omega_1 $ | k | $ \omega_2 $ |
|---|---|---|---|---|
| 1 | 20 | 0.62831853 | ||
| 2 | 200 | 0.62831853 | 0 | N/A |
| 3 | 20 | 0.64402649 | 0 | N/A |
| 4 | 200 | 0.64402649 | 0 | N/A |
| 5 | 200 | 0.64402649 | 0.2 | 1.27234502 |
| 6 | 200 | 0.64402649 | 0.2 | 0.79168135 |
Question 2
Draw a complete flow diagram for a decimation-in-time FFT algorithm for an 8 point FFT. How many complex operations does your algorithm take? How many operations would this DFT computation take if you were using the summation formula (i.e., the definition of the DFT) instead?
Question 3
a) Draw a complete flow diagram for a decimation-in-time FFT algorithm for an 6 point FFT beginning with two three-point DFTs. How many complex operations does your algorithm take? How many operations would this DFT computation take if you were using the summation formula (i.e., the definition of the DFT) instead?
b) Draw a complete flow diagram for a decimation-in-time FFT algorithm for an 6 point FFT beginning with three two-point DFTs. How many complex operations does your algorithm take? Compare with your answers in part a).
Question 4
You want to exactly compute an exact 5120-point DFT. You have a radix 2 FFT
subroutine that computes the DFT for $ N=2^M $ points for any integer value of M.
a) Show how to use this subroutine to efficiently compute a 5120-point DFT.
b) Draw a block diagram for your algorithm, showing the radix 2 FFT subroutine as a black box with no detail regarding what is inside it.
c) Calculate the approximate number of complex operations required to compute the 5120-point DFT using your efficient approach, and compare with the
number of complex operations required to compute the 5120-point DFT directly.
Question 5
Under which circumstances can one explicitly reconstruct the DTFT of a finite duration signal from its DFT? Explain.
