Contents
Homework 5, ECE438, Fall 2011, Prof. Boutin
Due Wednesday October 19, 2011 (in class)
- Note the slight change in Question 3. --Mboutin 14:24, 14 October 2011 (UTC)
Questions 1
Draw the complete flow diagram for the "decimation by two" FFT algorithm to compute an 8 point DFT. 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?
Questions 2
Draw a complete flow diagram for of the "radix-2" FFT algorithm to compute an 8 point DFT. How many complex operations does your algorithm take?
Question 3
Draw a flow diagram for of the "decimation by two" FFT algorithm to compute a 122 point DFT. 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 4
Use the definition of the DFT (the summation formula) to obtain two different FFT algorithms to compute a 6 point DFT. Draw a flow diagram for each of your algorithms, and compute the total number of complex operations they would require. Compare these two numbers with the number of complex operations this computation would take if you were using the definition of the DFT instead.
Question 5
You want to compute a 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 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.
Discussion
Write your questions/comments here
- Is this due Monday the 17th or Wednesday the 19th just for clarification. Thanks.
- Is this due Wednesday the 19th. Sorry got the date wrong. -pm
