| (20 intermediate revisions by the same user not shown) | |||
| Line 9: | Line 9: | ||
DFT | DFT | ||
| − | <math> X [k] = \sum_{k=0}^{N-1} x[n] | + | <math> X [k] = \sum_{k=0}^{N-1} x[n]e^{-j2\pi kn/N}</math> |
IDFT | IDFT | ||
| − | <math> x [n] = (1/N) \sum_{k=0}^{N-1} X[k] | + | <math> x [n] = (1/N) \sum_{k=0}^{N-1} X[k]e^{j2\pi kn/N}</math> |
| Line 24: | Line 24: | ||
Idea : discretize (ie. sample) the F.T. | Idea : discretize (ie. sample) the F.T. | ||
| − | <math> X(w) = \sum_{n=-\infty}^{\infty} x[n] | + | <math> X(w) = \sum_{n=-\infty}^{\infty} x[n]e^{-jwn}----sampling---> X(k2\pi /N) = \sum x[n]e^{-j2\pi nk/N}</math> |
note : if X(w) band limited can reconstruct X(w) if N big enough. | note : if X(w) band limited can reconstruct X(w) if N big enough. | ||
| Line 30: | Line 30: | ||
Oberve : | Oberve : | ||
| − | <math> X( | + | <math> X(k2\pi /N) = \sum_{n=0}^{N-1} x_{p}[n]e^{-j2\pi kn/N}</math>, where <math> x_{p}[n] = \sum_{-\infty}^{\infty} x[n-lN]</math> |
is periodic with N. | is periodic with N. | ||
This is because | This is because | ||
| − | math> X( | + | <math> X(k2\pi /N) = \sum_{n =-\infty}^{\infty} x[n]e^{-j2\pi kn/N}</math> |
| − | + | <math> = . . . + \sum_{n = -N}^{-1} x[n]e^{-j2\pi kn/N} + \sum_{n = 0}^{N-1} x[n]e^{-j2/pi kn/N}. . .</math> | |
| − | + | <math> = \sum_{l=-\infty}^{\infty} \sum_{n=lN}^{lN+N-1} x[n]e^{-j2\pi kn/N}</math> | |
| + | |||
| + | Let m=n-lN | ||
| + | |||
| + | <math> X(k2\pi /N) = \sum_{l=-\infty}^{\infty} \sum_{m=0}^{N-1} x[m+lN]e^{-j2\pi k(m+lN)/N}</math> | ||
| + | <math> = \sum_{l=-\infty}^{\infty} \sum_{m=0}^{N-1} x[m+lN]e^{-j2\pi km/N}</math> | ||
| + | |||
| + | where <math>\sum_{m=0}^{N-1} x[m+lN]</math> is <math> Xp[n]</math> | ||
| + | |||
| + | Note : if X[n] is finite duration N | ||
| + | => Xp[n] is the periodic repetation of X[n] | ||
| + | |||
| + | Nice thing is | ||
| + | |||
| + | Xp[n] can be recovered from the sampling <math> X(k2\pi /N)</math> | ||
| + | |||
| + | because | ||
| + | |||
| + | <math> X(k2\pi /N) = \sum_{n=0}^{N-1}Xp[n]e^{-j2\pi km/N}</math> | ||
| + | |||
| + | <math> \sum_{k=0}^{N-1}e^{j2\pi km/N}X(k2\pi /M)=\sum_{k=0}^{jw\pi km/N}\sum_{n=0}^{N-1}Xp[n]e^{-j2\pi km/N}</math> | ||
| + | |||
| + | <math>=\sum_{n=0}^{N-1}\sum_{k=0}^{N-1}Xp[n]e^{-j2\pi k(n-m)/N}</math> | ||
| + | |||
| + | <math>=\sum_{n=0}^{N-1}Xp[n]\sum_{k=0}^{N-1}(e^{-j2\pi (n-m)/N})^{k}</math> | ||
| + | |||
| + | <math>=\sum_{n=0}^{N-1}Xp[n]</math> | ||
| + | |||
| + | | N, if n=m | ||
| + | |||
| + | | <math>\frac{1-e^{-j2\pi(n-m)N/N}}{1-e{-jw\pi (n-m)/N}} = 0, else</math> | ||
| + | |||
| + | so, <math> Xp[n]= \frac{1}{N}\sum_{k=0}^{N-1}X(K2\pi /N)e^{j2\pi km/N}</math> | ||
| + | |||
| + | We write | ||
| + | |||
| + | <math> X[n] = X(k2\pi/N)</math> | ||
| + | |||
| + | <math>Xp[n]----DFT---->X[k]</math> | ||
| + | |||
| + | <math>Xp[n]<----IDFT----X[k]</math> | ||
| + | |||
| + | DFT properties | ||
| + | |||
| + | <math>X[n]=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{j2\pi km/N}</math> | ||
| + | |||
| + | <math>X(k)=\sum_{k=0}^{N-1}X[n]e^{-j2\pi km/N}</math> | ||
| + | |||
| + | X(k)=Nak | ||
| + | |||
| + | DFT | ||
| + | |||
| + | same formula as for discrete fourier series. | ||
| + | |||
| + | ==> same properties as DFT series. | ||
Latest revision as of 22:03, 22 September 2009
Discrete Fourier Transform
definition
Let X[n] be a DT signal with period N
DFT
$ X [k] = \sum_{k=0}^{N-1} x[n]e^{-j2\pi kn/N} $
IDFT
$ x [n] = (1/N) \sum_{k=0}^{N-1} X[k]e^{j2\pi kn/N} $
Derivation
Digital signals are 1) finite duration 2)discrete
want F.T. discrete and finite duration
Idea : discretize (ie. sample) the F.T.
$ X(w) = \sum_{n=-\infty}^{\infty} x[n]e^{-jwn}----sampling---> X(k2\pi /N) = \sum x[n]e^{-j2\pi nk/N} $
note : if X(w) band limited can reconstruct X(w) if N big enough.
Oberve :
$ X(k2\pi /N) = \sum_{n=0}^{N-1} x_{p}[n]e^{-j2\pi kn/N} $, where $ x_{p}[n] = \sum_{-\infty}^{\infty} x[n-lN] $ is periodic with N.
This is because
$ X(k2\pi /N) = \sum_{n =-\infty}^{\infty} x[n]e^{-j2\pi kn/N} $
$ = . . . + \sum_{n = -N}^{-1} x[n]e^{-j2\pi kn/N} + \sum_{n = 0}^{N-1} x[n]e^{-j2/pi kn/N}. . . $
$ = \sum_{l=-\infty}^{\infty} \sum_{n=lN}^{lN+N-1} x[n]e^{-j2\pi kn/N} $
Let m=n-lN
$ X(k2\pi /N) = \sum_{l=-\infty}^{\infty} \sum_{m=0}^{N-1} x[m+lN]e^{-j2\pi k(m+lN)/N} $ $ = \sum_{l=-\infty}^{\infty} \sum_{m=0}^{N-1} x[m+lN]e^{-j2\pi km/N} $
where $ \sum_{m=0}^{N-1} x[m+lN] $ is $ Xp[n] $
Note : if X[n] is finite duration N => Xp[n] is the periodic repetation of X[n]
Nice thing is
Xp[n] can be recovered from the sampling $ X(k2\pi /N) $
because
$ X(k2\pi /N) = \sum_{n=0}^{N-1}Xp[n]e^{-j2\pi km/N} $
$ \sum_{k=0}^{N-1}e^{j2\pi km/N}X(k2\pi /M)=\sum_{k=0}^{jw\pi km/N}\sum_{n=0}^{N-1}Xp[n]e^{-j2\pi km/N} $
$ =\sum_{n=0}^{N-1}\sum_{k=0}^{N-1}Xp[n]e^{-j2\pi k(n-m)/N} $
$ =\sum_{n=0}^{N-1}Xp[n]\sum_{k=0}^{N-1}(e^{-j2\pi (n-m)/N})^{k} $
$ =\sum_{n=0}^{N-1}Xp[n] $
| N, if n=m
| $ \frac{1-e^{-j2\pi(n-m)N/N}}{1-e{-jw\pi (n-m)/N}} = 0, else $
so, $ Xp[n]= \frac{1}{N}\sum_{k=0}^{N-1}X(K2\pi /N)e^{j2\pi km/N} $
We write
$ X[n] = X(k2\pi/N) $
$ Xp[n]----DFT---->X[k] $
$ Xp[n]<----IDFT----X[k] $
DFT properties
$ X[n]=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{j2\pi km/N} $
$ X(k)=\sum_{k=0}^{N-1}X[n]e^{-j2\pi km/N} $
X(k)=Nak
DFT
same formula as for discrete fourier series.
==> same properties as DFT series.
