| 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 12:07, 19 October 2010
Homework 6 Solution
Q1.
Matlab code:
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:
case 2:
case 3:
case 4:
case 5:
case 6:
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.
