Contents
Homework 5, ECE438, Fall 2011, Prof. Boutin
Due Wednesday October 17, 2011 (in class)
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 complete flow diagram for of the "radix-2" FFT algorithm to compute an 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
