Latest revision as of 12:17, 2 December 2011

Notes on Discrete Fourier Transform

From ECE301:"Signals and Systems" lecture by Prof. Boutin, Fall 2009.

Click here to visit the ECE301 Fall 2009 course wiki.

4) Discrete Fourier Transform

Definition: let x[n] be a DT signal with Period N.

$ X [k] = \sum_{k=0}^{N-1} x[n].e^{-J.2pi.kn/N} $

$ x [n] = (1/N) \sum_{k=0}^{N-1} X[k].e^{J.2pi.kn/N} $

Derivation:

Digital signal are :

• Finite Duration
• Discrete

So the idea is, we need to discretize (ie sample) the Fourier Transform

$ 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) is band-limited and if N is big enough, we can reconstruct X(w)

Observe that : $ 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

The reason behind this is as follow: $ X(k.2p/N) = \sum_{n =-\infty}^{\infty} x[n].e^{-J.2pi.kn/N} $

        $  = . . . . . + \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} $

let $ m = n - lN : $

$ X(k.2pi/N) = \sum_{l=-\infty}^{\infty} \sum_{m=0}^{N-1} x[m+lN].e^{-J.2pi.k.(m+lN)/N} $

        $  = \sum_{l=-\infty}^{\infty} \sum_{m=0}^{N-1} x[m+lN].e^{-J.2pi.km/N} $ since $  e^{-J.2pi.k.l} $ is always = 1 because k.l is always integer

and $  e^{J*2pi} = \cos (2*pi) + j \sin (2*pi) = 1 $ 

        $  = \sum_{m = 0}^{N-1}(\sum_{l=-\infty}^{\infty} x[m+lN]).e^{-J.2pi.km/N} $

As a result: $ x_{p}[n] = \sum_{l=-\infty}^{\infty} x(m + lN) $

Also Note that $ x_{p}[n] $ is the periodic repetition of $ x[n] $ if $ x[n] $ has a finite duration of N.

Note that $ x_{p}[n] $ can be recovered from Sampling $ X(k.2pi/N) $

Because :

$ X(k.2pi/N) = \sum_{n=0}^{N-1} x_{p}[n].e^{-J.2pi.kn/N} $. Mutiply both sides by $ \sum_{k=0}^{N-1} e^{J.2pi.km/N} $ $ \sum_{k=0}^{N-1} e^{J.2pi.km/N} X(k.2pi/N) = \sum_{k=0}^{N-1} e^{J.2pi.km/N} \sum_{n=0}^{N-1} x_{p}[n].e^{-J.2pi.kn/N} $

$ \sum_{n=0}^{N-1} \sum_{k=0}^{N-1} x_{p}[n].e^{-J.2pi.k.(n-m)/N} $

$ \sum_{n=0}^{N-1} x_{p}[n] \sum_{k=0}^{N-1}(e^{-J.2pi.(n-m)/N})^{k} $

$ \sum_{k=0}^{N-1}(e^{-J.2pi.(n-m)/N})^{k} = $

• $ N $ if m = n
• $ (1-e^{-J.2pi.(n-m)N/N}) / (1-e^{-J.2pi.(n-m)N}) $ else

since $ e^{-J.2pi.(n-m)N/N} $ is always = 1, $ (1-e^{-J.2pi.(n-m)N/N}) / (1-e^{-J.2pi.(n-m)N}) = 0 $

As a result:

$ \sum_{n=0}^{N-1} x_{p}[n] \sum_{k=0}^{N-1}(e^{-J.2pi.(n-m)/N})^{k} = N.\sum_{n=0}^{N-1} x_{p}[n] = N.x_{p}[m] $

$ x_{p}[n] = (1/N). \sum_{k=0}^{N-1} X(k.2pi/N).e^{J.2pi.kn/N} $

So,

$ X(k) = X(k.2pi/N) $

$ x_{p}[n] > DFT > X(k) $

Back to ECE301 Fall 2009