Line 6: Line 6:
 
Diagram of "decimation by two" FFT computing 8-pt DFT.
 
Diagram of "decimation by two" FFT computing 8-pt DFT.
  
[[Image:HW5Q1fig.jpg]]
+
[[Image:HW5Q1fig1.jpg]]
  
 
where <math>W_N^k = e^{-j2\pi k/N},\ N=8</math>
 
where <math>W_N^k = e^{-j2\pi k/N},\ N=8</math>
 +
 +
  
 
----
 
----

Revision as of 16:02, 23 October 2011

Homework 5, ECE438, Fall 2011, Prof. Boutin


Question 1

Diagram of "decimation by two" FFT computing 8-pt DFT.

HW5Q1fig1.jpg

where $ W_N^k = e^{-j2\pi k/N},\ N=8 $



Question 2

Diagram of "radix-2" FFT computing 8-pt DFT.

HW5Q2fig1.jpg

Recall the definition of DFT:

$ X[k]=\sum_{n=0}^{N-1} x[n]e^{-j2\pi k/N} $

In this question N=8

If we use summation formula to compute DFT, for each k, we need N times complex multiplications and N-1 times complex additions.

In total, we need N*N=64 times of complex multiplications and N*(N-1)=56 times of complex additions.

In decimation-in-time FFT algorithm, we keep on decimating the number of points by 2 until we get 2 points DFT. At most, we can decimate $ v=log_2 N $ times. As a result, we get v levels of DFT. Except for the first level (2-pt FFT), which only needs N times complex additions, for the rest of levels, we need N/2 times of complex multiplications and N times of complex additions.

In total, we need $ \frac{N}{2}(log_2 N -1)=8 $ times of complex multiplications and $ Nlog_2 N=24 $ times of complex additions.

(Note: when $ N $ is large, $ log_2 N -1 \approx log_2 N $. So the number of multiplications becomes $ \frac{N}{2}log_2 N $.)


Question 3


Back to Homework 5

Back to ECE 438 Fall 2011

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood