| Line 1: | Line 1: | ||
| − | + | == Discrete Fourier Transform == | |
| − | + | ||
| Line 18: | Line 17: | ||
== Derivation == | == Derivation == | ||
| + | |||
| + | Digital signals are 1) finite duration 2)discrete | ||
| + | |||
| + | want F.T. discrete and finite duration | ||
| + | |||
| + | Idea : discretize (ie. sample) the F.T. | ||
| + | |||
| + | <math> X(w) = \sum_{n=-\infty}^{\infty} x[n].e^{-Jwn} >^{sampling}> X(k.2pi/N) = \sum x[n].e^{-J2pi.n.k/N} </math> | ||
| + | |||
| + | note : if X(w) band limited can reconstruct X(w) if N big enough. | ||
| + | |||
| + | Oberve : | ||
| + | |||
| + | <math> X(k.2pi/N) = \sum_{n=0}^{N-1} x_{p}[n].e^{-J.2pi.kn/N}</math>, where <math> x_{p}[n] = \sum_{-\infty}^{\infty} x[n-lN]</math> | ||
| + | is periodic with N. | ||
| + | |||
| + | This is because | ||
| + | |||
| + | math> X(k.2p/N) = \sum_{n =-\infty}^{\infty} x[n].e^{-J.2pi.kn/N}</math> | ||
| + | |||
| + | <math> = . . . + \sum_{n = -N}^{-1} x[n].e^{-J2pi.k.n/N} + \sum_{n = 0}^{N-1} x[n].e^{-J.2pi.kn/N}</math> | ||
| + | |||
| + | <math> = \sum_{l=-\infty}^{\infty} \sum_{n=lN}^{lN+N-1} x[n].e^{-J.2pi.kn/N}</math> | ||
Revision as of 22:11, 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^{-J.2pi.kn/N} $
IDFT
$ x [n] = (1/N) \sum_{k=0}^{N-1} X[k].e^{J.2pi.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(k.2pi/N) = \sum x[n].e^{-J2pi.n.k/N} $
note : if X(w) band limited can reconstruct X(w) if N big enough.
Oberve :
$ X(k.2pi/N) = \sum_{n=0}^{N-1} x_{p}[n].e^{-J.2pi.kn/N} $, where $ x_{p}[n] = \sum_{-\infty}^{\infty} x[n-lN] $ is periodic with N.
This is because
math> X(k.2p/N) = \sum_{n =-\infty}^{\infty} x[n].e^{-J.2pi.kn/N}</math>
$ = . . . + \sum_{n = -N}^{-1} x[n].e^{-J2pi.k.n/N} + \sum_{n = 0}^{N-1} x[n].e^{-J.2pi.kn/N} $
$ = \sum_{l=-\infty}^{\infty} \sum_{n=lN}^{lN+N-1} x[n].e^{-J.2pi.kn/N} $
