intdian institution of technology channai.ppt

this a presentation of FT in details

1. ECE 8443 – Pattern RecognitionEE 3512 – Signals: Continuous and Discrete
•Objectives:
Derivation of the DFT
Relationship to DTFT
DFT of Truncated Signals
Time Domain Windowing
•Resources:
Wiki: Discrete Fourier Transform
Wolfram: Discrete Fourier Transform
DSPG: The Discrete Fourier Transform
Wiki: Time Domain Windows
ISIP: Java Applet
LECTURE 17: DISCRETE FOURIER TRANSFORM
URL:

2. EE 3512: Lecture 17, Slide 2
•The Discrete-Time Fourier Transform:
•Not practical for (real-time) computation on a digital computer.
•Solution: limit the extent of the summation to N points and evaluate the
continuous function of frequency at N equispaced points:
•MATLAB code for the DFT:
•The exponentials can be precomputed
so that the DFT can be computed
as a vector-matrix multiplication.
•Later we will exploit the symmetry
properties of the exponential to
speed up the computation (e.g., fft()).
The Discrete-Time Fourier Transform

 (analysis)][
)(synthesis
2
1
][
2







n
njj
njj
enxeX
deeXnx





 





1
0
/2
2 ][)(
N
n
Nknj
k
k
N
j
enxXkXeX





3. EE 3512: Lecture 17, Slide 3
Computation of the DFT
•Given the signal:
























 












31
20
11
06
)
2
3
sin()sin(2)
2
sin(2
)
2
3
cos()cos(2)
2
cos(21
3,2,1,0,1221
]3[]2[]1[]0[
3,2,1,0,][
]1,2,2,1[otherwise0][,1]3[,2]2[,2]1[,1]0[
2/32/
4/)3(24/)2(24/)1(24/)0(2
3
0
4/2
kj
k
kj
k
X
k
k
k
j
k
k
k
keee
exexexex
kenxX
nxxxxx
k
kjkjkj
kjkjkjkj
n
knj
k









x

4. EE 3512: Lecture 17, Slide 4
Symmetry
•The magnitude and phase functions are even and odd respectively.
•The DFT also has “circular” symmetry:
•When N is even, |X
k
| is symmetric about N/2.
•The phase,  X
k
, has odd symmetry about N/2.
)ofconjugatecomplex(][
Therefore,
...,2,1,01
But,
][][
:Let
][
1
0
/2
2
1
0
2/2
1
0
/)(2
1
0
/2
kk
N
n
Nknj
kN
nj
N
n
njNknj
N
n
NnkNj
kN
N
n
Nknj
k
XXenxX
nfore
eenxenxX
kNk
enxX



























5. EE 3512: Lecture 17, Slide 5
Inverse DFT
•The inverse transform follows from the DT Fourier Series:
1...,,1,0,
1
][
1
0
/2



NneX
N
nx
N
k
Nknj
k


6. EE 3512: Lecture 17, Slide 6
Computation of the Inverse DFT
 
  
  
 
  
 
  
  14/4116
4
1
))(1()0())(1(6
4
1
4
1
]3[
24/8116
4
1
)1)(1()0()1)(1(6
4
1
4
1
]2[
24/8116
4
1
))(1()1)(0()1(6
4
1
4
1
]1[
1
4
4
116
4
1
4
1
]0[
4
1
][
31
20
11
06
4/18
3
3
2
2/3
10
3
3
2
210
2/3
32
2/
10
3210
4/)3(2
3
4/)2(2
2
4/)1(2
10




















jj
jjjjeXeXeXXx
jj
jjeXeXeXXx
jj
jjjjeXeXeXXx
jjXXXXx
eXeXeXXnx
kj
k
kj
k
X
jjj
jjj
jjj
njnjnj
k





7. EE 3512: Lecture 17, Slide 7
Relationship to the DTFT
•The DFT and the DFT are related by:
•If we define a pulse as:
•The DFT is simply a sampling of the
DTFT at equispaced points along the
frequency axis.
•As N increases, the sampling becomes
finer. Note that this is true even when
q is constant  increasing N is a way of
interpolating the spectrum.
 





1
0
/2
2 ][)(
N
n
Nknj
k
k
N
j
enxXkXeX






 

otherwise
qn
nx
,0
2...,,2,1,0,1
][


)2/sin(
))2/1(sin(
)2/sin(
))2/1(sin(











q
eX
e
q
eX
j
jqj
•q=5, N = 22
•q = 5, N = 88
•q = 5

8. EE 3512: Lecture 17, Slide 8
DFT of Truncated Signals
•What if the signal is not time-limited?
We can think of limiting the sum to
N points as a truncation of the signal:
•What are the implications of this in
the frequency domain?
(Hint: convolution)
•Popular Windows:
Rectangular:
Generalized Hanning:
Triangular:


 


otherwise
Nn
nw
nxnwnx
w
,0
...,,2,1,0,1
][
][][][


 

otherwise
Nn
nw
,0
...,,2,1,0,1
][
)
1
2
cos()1(][


N
n
nw


)
2
1
2
(
2
][


N
n
N
N
nw
•Rectangular
•Generalized Hanning
•Triangular

9. EE 3512: Lecture 17, Slide 9
Impact on Spectral Estimation
•The spectrum of a windowed
sinewave is the convolution of two
impulse functions with the frequency
response of the window.
•For two closely spaced sinewaves,
there is “leakage” between each
sinewave’s spectrum.
•The impact of this leakage can be
mitigated by using a window
function with a narrower main lobe.
•For example, consider the spectrum
of three sinewaves computed using
a rectangular and a Hamming
window.
•We see that for the same number of
points, the spectrum produced by te
Hamming window separates the
sinewaves.
•What is the computational cost?

10. EE 3512: Lecture 17, Slide 10
Summary
•Introduced the Discrete Fourier Transform as a truncated version of the
Discrete-Time Fourier Transform.
•Demonstrated both the forward and inverse transforms.
•Explored the relationship to the DTFT.
•Compared the spectrum of a pulse.
•Discussed the effects of truncation on the spectrum.
•Introduced the concept of time domain windowing and discussed the impact
of windows in the frequency domain.