Contents
Homework 7, ECE438, Fall 2013, Prof. Boutin
Harcopy of your solution due in class, Friday October 18, 2013
Presentation Guidelines
- Write only on one side of the paper.
- Use a "clean" sheet of paper (e.g., not torn out of a spiral book).
- Staple the pages together.
- Include a cover page.
- Do not let your dog play with your homework.
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
Please discuss the homework below.
- Comment/question here
- answer here
