Contents
Homework 7, ECE438, Fall 2016, Prof. Boutin
Hard copy due in class, Wednesday October 19, 2016.
Question 1
Draw a flow diagram for a 2-point DFT and count the number of complex operations involved.
Question 2
Draw a flow diagram for a 3-point DFT and count the number of complex operations involved.
Question 3
Draw a flow diagram for a 5-point DFT and count the number of complex operations involved.
Question 4
Draw the complete flow diagram for the "decimation by two" FFT algorithm to compute an N=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?
Question 5
Same as Question 4, but with N=20. NOTE: THERE WAS A TYPO IN THAT QUESTION PREVIOUSLY: QUESTION 1-> QUESTION 4.
Questions 6
Draw a complete flow diagram for the "radix-2" FFT algorithm to compute an 8 point DFT. How many complex operations does your algorithm take?
Question 7
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.
Hand in a hard copy of your solutions. Pay attention to rigor!
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.
Discussion
- Write question/comment here.
- answer will go here
