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


Back to ECE438, Fall 2013, Prof. Boutin

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett