Difference between revisions of "9-21 lecture note" - Rhea

Revision as of 21:53, 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 $