Line 44: Line 44:
 
Q2.
 
Q2.
  
 +
Recall the definition of DFT: <math>X[k]=\sum_{n=0}^{N-1} x[n]e^{-j2\pi k/N}</math>
 +
 +
In this question N=8
 +
 +
If we use summation formula to compute DFT, for each k, we need N times complex multiplications and N 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 <math>v=log2N</math> times. As a result, we get v levels of DFT. For each level, we need N/2 times of complex multiplications and N times of complex additions.
 +
 +
In total, we need <math>\frac{N}{2}log2N=12</math>N times of complex multiplications and <math>Nlog2N=24</math> times of complex additions.
  
 
------------------------------------
 
------------------------------------

Revision as of 13:07, 19 October 2010

Homework 6 Solution

Q1.

Matlab code:

MCode HW6 Q1.jpg

Assign the value of parameters and then call the function signalDFT

For example, in case 6 type following command in the command window of Matlab:

N=20;

w1=0.62831853;

k=0.2;

w2=0.79168135;

[x,X]=signal(w1,w2,k,N);

Plot result:

case 1: HW6 Q1 Case1.jpg

case 2: HW6 Q1 Case2.jpg

case 3: HW6 Q1 Case3.jpg

case 4: HW6 Q1 Case4.jpg

case 5: HW6 Q1 Case5.jpg

case 6: HW6 Q1 Case6.jpg


Q2.

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 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=log2N $ times. As a result, we get v levels of DFT. For each level, we need N/2 times of complex multiplications and N times of complex additions.

In total, we need $ \frac{N}{2}log2N=12 $N times of complex multiplications and $ Nlog2N=24 $ times of complex additions.


Q3.



Q4.



Q5.



Q6.



Q7.



Back to Course Homepage

Back to Homework 6 Questions

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood