(New page: =Homework 5, ECE438, Fall 2011, Prof. Boutin= ---- ==Question 1== ---- Back to Homework 5 Back to [[2011_Fall_ECE_438_Boutin|ECE 438 Fall 2011]...) |
|||
| Line 1: | Line 1: | ||
=Homework 5, [[ECE438]], Fall 2011, [[user:mboutin|Prof. Boutin]]= | =Homework 5, [[ECE438]], Fall 2011, [[user:mboutin|Prof. Boutin]]= | ||
| − | |||
| − | |||
---- | ---- | ||
==Question 1== | ==Question 1== | ||
| + | |||
| + | 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-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 <math>v=log_2 N</math> 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 <math>\frac{N}{2}(log_2 N -1)=8</math> times of complex multiplications and <math>Nlog_2 N=24</math> times of complex additions. | ||
| + | |||
| + | (Note: when <math>N</math> is large, <math>log_2 N -1 \approx log_2 N</math>. So the number of multiplications become <math>\frac{N}{2}log_2 N</math>. | ||
---- | ---- | ||
Revision as of 14:38, 23 October 2011
Homework 5, ECE438, Fall 2011, Prof. Boutin
Question 1
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 become $ \frac{N}{2}log_2 N $.
Back to Homework 5
Back to ECE 438 Fall 2011
