(New page: == 1.6.3 Spectral analysis via DFT == <p>use DFT to approximate <math>X(a)</math> for a DT signal x(n) <h3>Relationships of signals</h3> <p>infinate duration signal: <math>x(n) \Rightar...) |
|||
| Line 26: | Line 26: | ||
*frequency sampling <math>\Rightarrow</math> "picket fence effect" | *frequency sampling <math>\Rightarrow</math> "picket fence effect" | ||
| + | |||
| + | </p> | ||
| + | == 1.6.4 FFT "Fast Fourier transform" == | ||
| + | <p>An algorithm (family of algo) to compute the DFT <u>fast</u></p> | ||
| + | <p>Recall DFT of x(n) periodic w\ period N<br/> | ||
| + | <math> X(k) = \sum_{n=0}^{N-1} x(n)e^{-j\frac{2\pi}{N}kn}</math><br/> | ||
| + | <math>e^{-j\frac{2\pi}{N}^r}</math> is an Nth root of unity for every r=0,1,2,...,N-1<br/> | ||
| + | |||
| + | N=2<br/>two square roots of unity<br/> | ||
| + | <math>e^{-j\frac{2\pi}{N}*0} = 1</math><br/> | ||
| + | <math>e^{-j\frac{2\pi}{N}*1r} = e^{-j\pi} = -1</math><br/> | ||
| + | Let <math>W_N^r = e^{-j\frac{2\pi}{N}r}</math>for every r, <math>W_N^r</math> is an Nth root of unity | ||
</p> | </p> | ||
--[[User:Drestes|Drestes]] 15:05, 23 February 2009 (UTC) | --[[User:Drestes|Drestes]] 15:05, 23 February 2009 (UTC) | ||
Revision as of 10:21, 23 February 2009
Contents
1.6.3 Spectral analysis via DFT
use DFT to approximate $ X(a) $ for a DT signal x(n)
Relationships of signals
<p>infinate duration signal: $ x(n) \Rightarrow DTFT \Rightarrow X(w) $
also infinate druation signal: $ x(n) \Rightarrow *truncation\Rightarrow \bar{x}(n) = x[n] $ finite duration
The periodic sample of $ x_p(n) = \sum_{l=-\infty}^{\infty} \bar{x}(n+lN) $
The DTFT of periodic sample is $ X(k) $
The DTFT of $ \bar{x}(n) \Rightarrow \bar{X}(w) \Rightarrow sampling\Rightarrow \bar{X}(k\frac{2\pi}{N}) = X(k) $
Example
$ x(n) = cos(w_0n) $
$ X(w) = rep_{2\pi}(\pi \delta(w-w_0) + \pi \delta(w+w_0)) $
consider $ \bar{x}(n) = x(n)w(n) $
- $ w(n) = 1 | 0 \le n \le N, 0 | else $
$ \bar{X}(w) = F(\bar{x}(n)) $
$ = \frac{1}{2\pi}X(w)*W(w) $
$ = \frac{1}{2}(W(w+w_0) + W(w-w_0)) $
Two sources of inaccuracies
- signal truncation $ \Rightarrow $ "leakage"
- frequency sampling $ \Rightarrow $ "picket fence effect"
1.6.4 FFT "Fast Fourier transform"
An algorithm (family of algo) to compute the DFT fast
Recall DFT of x(n) periodic w\ period N
$ X(k) = \sum_{n=0}^{N-1} x(n)e^{-j\frac{2\pi}{N}kn} $
$ e^{-j\frac{2\pi}{N}^r} $ is an Nth root of unity for every r=0,1,2,...,N-1
N=2
two square roots of unity
$ e^{-j\frac{2\pi}{N}*0} = 1 $
$ e^{-j\frac{2\pi}{N}*1r} = e^{-j\pi} = -1 $
Let $ W_N^r = e^{-j\frac{2\pi}{N}r} $for every r, $ W_N^r $ is an Nth root of unity
--Drestes 15:05, 23 February 2009 (UTC)
