Homework 7, ECE438, Fall 2015, Prof. Boutin

Hard copy due in class, Wednesday October 14, 2015.


Questions 1

Draw the complete flow diagram for 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?

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

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

Back to ECE438, Fall 2015, Prof. Boutin

Alumni Liaison

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

Dr. Paul Garrett