Transcript PPT One Dimensional Fourier Analysis

ControlNumber
1
Nature of light and theories about it
 Fourier optics falls under wave optics
 Provides a description of propagation of light waves based
on two principles
– Harmonic (Fourier) analysis
– Linearity of systems
Quantum optics
Electromagnetic
optics
Wave optics
Ray optics
ControlNumber
2
Topics









Week 1: Review of one-dimensional Fourier analysis
Week 2: Two-dimensional Fourier analysis
Weeks 3-4: Scalar diffraction theory
Weeks 5-6: Fresnel and Fraunhofer diffraction
Week 7: Transfer functions and wave-optics analysis of
coherent optical systems
Weeks 8-9: Frequency analysis of optical imaging systems
Week 10: Wavefront modulation
Week 11: Analog optical information processing
Weeks 12-13: Holography
ControlNumber
3
Week 1: Review of One-Dimensional
Fourier Analysis
 Descriptions: time domain and frequency domain
 Principle of Fourier analysis
– Periodic: series
• Sin, cosine, exponential forms
– Non-periodic: Fourier integral
– Random
 Convolution
 Discrete Fourier transform and Fast Fourier Transform
 A deeper look: Fourier transforms and functional analysis
ControlNumber
4
Basic idea: what you learned in
undergraduate courses
 A periodic function f(t) can be expressed as a sum of sines
and cosines
– Sum may be finite or infinite, depending on f(t)
– Object is usually to determine
• Frequencies of sine, cosine functions
• Amplitudes of sine, cosine functions
• Error in approximating with finite number of
functions
– Function f(t) must satisfy Dirichlet conditions
 Result is that periodic function in time domain, e.g., square
wave, can be completely characterized by information in
frequency domain, i.e., by frequencies and amplitudes of
sine, cosine functions
ControlNumber
Historical reason for use of Fourier
series to approximate functions
 Breaks periodic function f(t) into component frequencies
 Response of linear systems to most periodic waves can be
analyzed by finding the response to each ‘harmonic’ and
superimposing the results)
5
ControlNumber
6
Basic idea: what you learned in
undergraduate courses (continued)
 Periodic means that f(t) = f(t+T) for all t
– T is the period
– Period related to frequency by T = 1/f0 = 2/0
– 0 is called the fundamental frequency
 So we have

f (t )  a0   an cos 2 nf 0  bn sin 2nf 0
n 1

 a0   an cos n 0  bn sin n0
n 1
 n0 = 2n/T is nth harmonic of fundamental frequency
ControlNumber
7
How to calculate Fourier coefficients
 Calculation of Fourier coefficients hinges on orthogonality of
sine, cosine functions



T
0
T
0
T
0
 Also,
sin m0 t cos n0 t dt  0, all m, n
sin m0 t sin n0 t dt  0, m  n
cos m0t cos n 0 t dt  0, m  n
T
0 sin m0t dt  2 , all m
T
T
2
0 cos m0t dt  2 , all m
T
2
ControlNumber
8
How to calculate Fourier coefficients
(continued)
 And we also need

T

T
0
0
sin m0t dt  0, all m
cos m0t dt  0, all m
ControlNumber
9
How to calculate Fourier coefficients
(continued)
 Step 1. integrate both sides:
T

0
T
T 
0
0
f ( t ) dt   a0 dt  
 a0T  0
 a0T
 Therefore
1
a0 
T

T
0
f ( t) dt
a
n
n 1
cos n0  bn sin n0 dt
ControlNumber
10
How to calculate Fourier coefficients
(continued)
 Step 2. For each n, multiply original equation by cos n0t and
integrate from 0 to T:
T

0
0
0
T
f ( t) cos n0t dt   a0 cos 0t cos n0t dt   a1 cos 20t cos n0t dt 
0
0
0
T
T
  a1 cos n0t cos n0t dt     a0 sin 0t cos n0t dt  
T
0
  an cos 2 n0t dt  anT / 2
T
0
2 T
Therefore a n   f (t ) cos n0 t dt
T 0
0
ControlNumber
11
How to calculate Fourier coefficients
(continued)
 Step 3. Calculate bn terms similarly, by multiplying original
equation by sin n0t and integrating from 0 to T
– Get similar result
2
bn 
T

T
0
f (t ) sin n0t dt
 Some rules simplify calculations
– For even functions f(t) = f(-t), such as cos t, bn terms = 0
– For odd functions f(t) = -f(-t), such as sin t, an terms = 0
ControlNumber
12
Calculation of Fourier coefficients:
examples
 Square wave (in class)
1, 0  t  1 / 2
f (t )  
  1, 1 / 2  t  1
1
T/2
-1
T
ControlNumber
13
Calculation of Fourier coefficients:
examples (continued)
 Result
Gibbs phenomenon:
ringing near discontinuity
Source: http://mathworld.wolfram.com/FourierSeries.html
4
sin 30t sin 50t sin 70t

f (t)   sin 0t 


 

3
5
7

ControlNumber
14
Calculation of Fourier coefficients:
examples (continued)
 Triangular wave (in class)
+V
T/2
T
-V
4V

t, 0  t  T / 4

T

 4V
f (t )  
t  2V , T / 4  t  3T / 4
 T
  V  4V t , 3T / 4  t  T

T

ControlNumber
Calculation of Fourier coefficients:
examples (continued)
 Triangle wave result
– Note that value of terms falls off as inverse square
8V 
sin 30t sin 50t sin 7 0t 
f (t)  2  sin 0t 



2
2
2
 
3
5
7

15
ControlNumber
16
Other simplifying assumptions: halfwave symmetry
 Function has half-wave symmetry if second half is negative
of first half:
f (t)   f (t  T / 2)
ControlNumber
17
Other simplifying assumptions: halfwave symmetry
 Can be shown
a0  0, an  bn  0, n even
4 T /2

an  
f ( t ) cos n0t dt 
T 0
n odd

T
/
2
4
bn   f (t ) sin n0t dt 
T 0

ControlNumber
18
Conditions for convergence
 Conditions for convergence of Fourier series to original
function f(t) discovered (and named for) Dirichelet
– Finite number of discontinuities
– Finite number of extrema
– Be absolutely convergent: T f(t) d
t
0
 Example of periodic function excluded

1
i
f
t
r
a
t
i
o
n
a
l
,
0
o
t
h
e
r
w
i
s
e
,0

t

1
/
2

f
(
t
)



1
i
f
t
r
a
t
i
o
n
a
l
,
0
o
t
h
e
r
w
i
s
e
,1
/
2

t

1

ControlNumber
19
Parseval's theorem
 If some function f(t) is represented by its Fourier expansion
on an interval [-l,l], then
2 

l
1
2 a
2
2
0


f
(
x
)


a

b

n
n


l
2
l
4n

1
n

1
 Useful in calculating power associated with waveform
ControlNumber
20
Effect of truncating infinite series
 Truncation error function en(t) given by
en  f (t )  sn (t )
– This is difference between original function and truncated
series sn(t), truncated after n terms
 Error criterion usually taken as mean square error of this
function over one period
1 T
2
En   e n ( t)  dt
T 0 of Fourier series states that no other
 Least squares property
series with same number n of terms will have smaller value
of En
ControlNumber
21
Effect of truncating infinite series
(continued)
 Problem is that there is no effective way to determine value
of n to satisfy any desired E
 Only practical approach is to keep adding terms until
En < E
 One helpful bit of information concerns fall-off rate of terms
– Let k = number of derivatives of f(t) required to produce a
discontinuity
– Then
M
M
wherea
M
depends
on
f(t)
but
not n

,
b

n
n
k

1
k

1
n
n
ControlNumber
Some DERIVE scripts
 To generate square wave of amplitude A, period T:
squarewave(A,T,x) := A*sign(sin(2*pi*x/T))
 For Fourier series of function f with n terms, limits c, d:
Fourier(f,x,c,d,n)
– Example: Fourier(squarewave(2,2,x),x,0,2,5) generates
first 5 terms (actually 3 because 2 are zero)
 To generate triangle wave of amplitude A, period T:
int(squarewave(A,T,x),x)
– Then Fourier transform can be done of this
22
ControlNumber
23
Exponential form of Fourier Series
 Previous form

f (t )  a0   an cos n0t  bn sin n0t 
n 1
 Recall that


1 jn0 t
cos n0 t  e
 e  jn 0 t
2
1 jn 0t
sin n0 t 
e
 e  jn0 t
2j


ControlNumber
24
Exponential form of Fourier Series
(continued)
 Substituting yields
 e jn 0t  e  jn 0t
e jn0t  e  jn 0t
f (t)  a0    a n
 bn
2
2j
n 1 

 Collecting like exponential terms and using fact that
1/j = -j:



 an  jbn jn 0t an  jbn  jn0t 
f (t)  a0   
e

e

2
2

n 1 

ControlNumber
25
Exponential form of Fourier Series
(continued)
 Introducing new coefficients
a n  jbn
an  jbn ~
~
~
cn 
, c n 
, c0  a0
2
2
 We can rewrite Fourier series as


f (t)  ~
c0   ~
cne jn 0t  c~ n e jn 0t
n 1
 Or more compactly by changing the index
f (t ) 

jn 0 t
~
c
e
n
n  

ControlNumber
26
Exponential form of Fourier Series
(continued)
 The coefficients can easily be evaluated
a n  jbn
~
cn 
2
1 T
j T
  f ( t ) cos n0t dt   f (t ) sin n0t dt
T 0
T 0
1 T
  f ( t ) cos n0t  j sin n0 t  dt
T 0
1 T
  f ( t ) e  jn 0t dt
T 0
ControlNumber
27
Exponential form of Fourier Series
(continued)
 Sometimes coefficients written in real and complex terms as
~
cn  ~
cn e j n , ~
cn  ~
cn*  c~n e jn
where
1 2
~
cn 
an  bn2
2
 bn 
 n  arctan   
 an 
ControlNumber
28
Exponential form of Fourier Series:
example
 Take sawtooth function, f(t) = (A/T)t per period
 Then
1


~
cn  T



T
0
V  jn0 t
te
dt , n  0
T
V / 2, n  0
 Hint: if using Derive, define  = 2/T, set domain of n as
integer
ControlNumber
29
Fourier analysis for nonperiodic
functions
 Basic idea: extend previous method by letting T become
infinite
 Example: recurring pulse
v0
t
-a/2
a/2
T
ControlNumber
30
Fourier analysis for nonperiodic
functions (continued)
 Start with previous formula:
1 T
~
cn   f (t ) e  jn 0 t dt
T 0
1 a/2
 jn 0t
 a / 2 V0 e
dt
T
 This can be readily evaluated as
jn0 a / 2
 jn 0 a / 2


V
e

e
0 a  sin( n0 a / 2) 
~
0

  V0


cn 
n 
2j
2   n0a / 2 

ControlNumber
31
Fourier analysis for nonperiodic
functions (continued)
 Using fact that T = 2/0, may be written
a  sin( n0a / 2) 
a  sin( na / T ) 
~
  V0 
cn  V0 

T  n0a / 2 
T  na / T 
 We are interested in what happens as period T gets larger,
with pulse width a fixed
– For graphs, a = 1, V0 = 1
ControlNumber
32
Effect of increasing period T
0.25
0.6
a/T
c o e ffic ie n t v a lu e , T =5
0.4
0.3
0.2
0.1
a/T
0.2
0.15
0.1
0.05
0
0
0
0
50
100
150
50
100
-0.05
-0.1
-0.1
-0.2
frequency
frequency
0.12
a/T
0.1
coefficient value, T=10
coefficient value, T=2
0.5
0.08
0.06
0.04
0.02
0
0
50
100
-0.02
-0.04
frequency
150
150
ControlNumber
33
Transition to Fourier integral
 We can define f(jn0) in the following manner
1
~
cn 
T
~
cT
n
 jn0 t
V
e
dt
a / 2 0
a/2

a/2
a / 2
V0 e  jn 0t dt
~
~
c
cn
~
n
F ( jn 0 )  c nT  2
 2
0
D
Since difference in frequency of terms D = 0 in the
expansion. Hence
F ( jn 0 ) D
~
cn 
2
ControlNumber
34
Transition to Fourier integral
(continued)
 Since
f (t ) 

jn 0 t
~
c
e
n
n  
 It follows that
F ( jn 0 )  jn 0t
f (t)  lim 
e
D
T   n  
2

 As we pass to the limit, D -> d, nD ->  so we have
1 
j t
f (t) 
F
(
j

)
e
d

2  
ControlNumber
35
Transition to Fourier integral
(continued)
 This is subject to convergence condition



f (t ) dt  
 Now observe that since
1
~
cn 
T

T
0
f (t) e  jn0t dt
 We have
a/2
~
cnT  F ( jn0 )   f (t) e  jn0t dt
a / 2
ControlNumber
36
Transition to Fourier integral
(continued)
 In the limit as T -> 
F ( j )  
a/2
a / 2



f (t )e  j  t dt
f (t )e  j t dt
 Since f(t) = 0 for t < -a/2 and t > a/2
 Thus we have the Fourier transform pair for nonperiodic
functions
F ( j )  Ff (t )
f (t )  F -1 F ( j )
ControlNumber
37
Example: pulse
 For pulse of area 1, height a, width 1/a, we have

2 a sin  
1/ 2 a
 2a 
F ( t )   ae  jt dt 
1 / 2 a

 Note that this will have zeros at  = 2an, n=0,+1, +2
 Considering only positive frequencies, and that “most” of the
energy is in the first lobe, out to 2a, we see that product of
bandwidth 2a and pulse width 1/a = 2
ControlNumber
38
Example of pulse
5
width=1
1
-1/2
-1/10
1/2
1/1
0
width=0.2
ControlNumber
39
Pulse: limiting cases
 Let a -> , then f(t) -> spike of infinite height and width 1/a
(delta function) -> 0
– Transform -> line F(j)=1
– Thus transform of delta function contains all frequencies
 Let a -> 0, then f(t) -> infinitely long pulse
– Transform -> spike of height 1, width 0
 Now let height remain at 1, width be 1/a
– Then transform is

 

2 sin  
sin  
sin  
2a  2
2a  1  2a 


F ( j ) 



2a   
a  
 
 
 2a 
 2a 
ControlNumber
40
Pulse: limiting cases (continued)
 Now, we are interested in limit as a -> 0 for  -> 0 and  > 0
– First, consider case of small :


sin  
sin  
1  2a  1
1
2a
lim
 lim   
 0 a
 
a  0   
a
 
 
 2a 
 2a 
– So when a -> 0, 1/a -> 
– As w moves slightly away from 0, it drops to zero quickly
because of w/2a term in denominator (numerator <1 at all
times)
 So we get delta function, d(0)
ControlNumber
Fourier transform of pulse width 0.1
41
ControlNumber
42
Properties of delta function
0 x  0
 Definition d( x)  
 x  0
 Area



for any g > 0
d( x) dx  1   d( x ) dx
 Sifting property
g
g






since
d( x ) f ( x ) dx  f ( 0)
d( x  x0 ) f ( x) dx  f ( x0 )
 0 x  x0
d( x  x0 )  
 x  x0
ControlNumber
43
Some common Fourier transform pairs
Source: http://mathworld.wolfram.com/FourierTransform.html
ControlNumber
44
Some Fourier transform pairs
(graphical illustration)
function
transform
function
transform
Source: Physical Optics Notebook: Tutorials in Fourier Optics, Reynolds,
et. al., SPIE/AIP
ControlNumber
Fourier transform: Gaussian pulses
45
ControlNumber
46
Properties of Fourier transforms

 Simplification: F ( j )  20 f (t ) cos t dt ,

F ( j )  2 f (t ) sin t dt ,
0
 Negative t:
 Scaling
– Time:
Ff (t )  F *( j)
1  j 
Ff ( at )  F  
a  a 
– Magnitude:
Faf (t)  aF ( j)
f (t ) even
f (t ) odd
ControlNumber
47
Properties of Fourier transforms
(continued)
 j a
F
f
(
t

a
)

F
(
j

)
e
 Shifting:
Ff ( t ) e j0t  F  j (   0 )
1
F  j(   0 )  F  j(   0 ) 
2
1
Ff ( t ) sin 0 t  F  j (   0 )   F  j (  0 ) 
2
Ff ( t ) cos 0 t 
 Time convolution:
F
1
F1 ( j)F2 ( j)  - f1 () f 2 (t  )d
 Frequency convolution:


1




F
f
(
t
)
f
(
t
)

F
(
j

)
F
j
(



)
d

1
2
1
2



2

ControlNumber
Convolution and transforms
 A principal application of any transform theory comes from
its application to linear systems
– If system is linear, then its response to a sum of inputs is
equal to the sum of its responses to the individual inputs
– This was original justification for Fourier's work
 Because a delta function contains all frequencies in its
spectrum, if you “hit” something with a delta function, and
measure its response, you know how it will respond to any
individual frequency
– The response of something (e.g., a circuit) to a delta
function is called its “impulse response”
• Called “point spread function” in optics
– Often denoted h(t)
48
ControlNumber
Convolution and transforms
(continued)
 The Fourier transform of the impulse response can be
calculated, usually designated H(j)
 Therefore if one knows the frequency content of an incoming
“signal” u(t), one can calculate the response of the system
– The response to each individual frequency component of
incoming signal can be calculated individually as product
of impulse response and that component
– Total response is obtained by summing all of individual
responses
 That is, response Y(j) = H(j)U(j)
– Where U(j) is sum of Fourier transforms of individual
components of u(t)
49
ControlNumber
50
Convolution and transforms
(continued)
 May be visualized as
U(j)
H(j)
Y(j)=H(j)U(j)
Input
System
Response
ControlNumber
51
Convolution and transforms
(continued)
 Example
– Signal is square wave, u(t)=sgn(sin(x))
sin( 2n  1) 0t
u (t )  
2n 1
n 1

– This has Fourier transform
i   
( 2n 1) 0  
(2 n  1)0  
U ( j )   d  
  d  

2 n 1  
2
2
 

– So response Y(j) is

i
 
( 2n  1)0  
( 2n 1) 0  
Y ( j )  H ( j)U ( j)  H ( j) d  
  d  

2
2
2
 

n 1  
ControlNumber
Convolution and transforms
(continued)
 If incoming signal described by Fourier integral instead,
same result holds
 To get time (or space) domain answer, we need to take
inverse Fourier transform of Y(j)
52
ControlNumber
53
Convolution and transforms
(continued)
 Can also be calculated in time (or space), i.e., nontransformed domain
 Derivation
Y ( j )  H ( j)U ( j)


 j t



  h (t ) e dt  u ( z )e  j z dz 
 
   





  
h (t )u ( z ) e  j ( t z) dtdz
 Now, we introduce new variables v and , related to t and z by
v  t  z,   z
ControlNumber
54
Convolution and transforms
(continued)
 Computing Jacobean to transform variables
z t z t
dt dz 

d dv  d dv
v   v
– Implies that differential areas same for both systems of
variables
 Thus since t = v-z = v- we have
v

Y ( j)    h (v  )u () d e  j v dv
 

0

 Where we have calculated the limits as follows
ControlNumber
Convolution and transforms
(continued)
 We may assume without loss of generality that u(z) = 0 for
z<0
– Otherwise we can shift variables to make it so
• Must assume that u(z) has some starting point
– Therefore the lower limit of integration in the inner
integral is 0
 We may also assume without loss of generality that h(t) = 0
for t<0
– Therefore h(v-) = 0 for  > v
55
ControlNumber
56
Convolution and transforms
(continued)
 Since the outer integral defines a Fourier transform, its
inverse is just y(t), so we have
y (t)  F
1
Y ( j)  0 h(v  )u()d
v
 This is usually written with t as the inner variable,
t
y
(
t)
(
t

)
u
(

)
d

h
0 convolution of h and u, usually written
 This is called the
y(t) = h*u
 Can readily be calculated on a computer
ControlNumber
Convolution: old way (graphically)

57
ControlNumber
58
Convolution: old way (continued)
Source: P. S. Rha, SFSU,
http://online.sfsu.edu/~psrha/
ENGR449_PDFs/EE449_L5_Conv.PDF
ControlNumber
Convolution and transforms (new way)
 Use computer algebra programs
 Some Derive scripts
– Step function: u(t):=if(t<0,0,1)
– Pulse of width d, amplitude a: f1(t):=if(t>=0 and t<=d,a,0)
– Triangle of width d, amplitude a:
triangle(t):=if(t>=0 and t<=d/2,2at/d,(if(t>d/2 and t<d,2a2at/d,0)0)
– Convolution: convolution(t):=int(f1(t-)*f2(),,0,t)
 Example
– f1 is pulse of width 1, amplitude 1
– f2 is pulse of width 2, amplitude 3
59
ControlNumber
Convolution functions
60
ControlNumber
61
Convolution: useful web sites




http://www.jhu.edu/~signals/
http://mathworld.wolfram.com/Convolution.html
http://www.annauniv.edu/shan/Lap1.1.9.html
http://rivit.cs.byu.edu/morse/550-F95/node12.html
ControlNumber
62
Fourier and Laplace transforms
 Fourier transform does not preserve initial condition
information
– Therefore most useful when “steady state” conditions
exist
• This is typically the case for optical systems
• But often not true for electrical networks
 Comparison of definitions
Laplace

Fourier
F ( s )   f ( t ) e dt
st
0
1 1 j
st
f (t) 
F
(
s
)
e
ds



j

2j 1

F ( j )   f (t ) e  jt dt
1 
j t
f (t) 
F
(
j

)
e
d


2
ControlNumber
63
Fourier and Laplace transforms
(continued)
 Differences
– In Fourier transform, j replaces s
– Limits of integration are different, one-sided vs. two-sided
– Contours of integration in inverse transform different
• Fourier along imaginary axis
• Laplace along imaginary axis displaced by 1
 Conversion between Fourier and Laplace transforms
– Laplace transform of f(t) = Fourier transform of f(t)e-t
– Symbolically,

Lf ( t)  F f (t )e  t

ControlNumber
Fourier transforms of random sources
(noise)
 Noise has frequency characteristics
– Generally continuous distribution of frequencies
– Since transform of individual frequencies gives spikes, this
allows us to separate signal from noise via Fourier methods
 Common types of noise
– White noise: equal power per Hz (power doubles per octave)
– Pink noise: equal power per octave
– Other “colors” of noise described at
http://www.hoohahrecords.com/resfreq/articles/noise.html
– Fourier transform distinguishes these
64
ControlNumber
Fourier transforms of random sources
(noise) (continued)
 Frequency domain thus allows us to obtain information
about signal purity that is difficult to obtain in time (or space)
domain
– Noise
– Distortion
65
ControlNumber
Fourier transforms of random sources
(noise) (continued)
Source:
http://hesperia.gsfc.nas
a.gov/~schmahl/fourie
r_tutorial/node6.html
66
ControlNumber
67
Discrete and Fast Fourier Transforms
 Most Fourier work today carried out by computer (numerical)
analysis
 Discrete Fourier transform (DFT) is first step in numerical
analysis
– Simply sample target function f(t) at appropriate times
– Replace integral by summation
F ( j)  


f ( t ) e j t dt
N 1
F ( j k )   f (t n )e  j kt n , k  0,1,2  N  1
n 0
Here tn = nT, where T=sampling interval, N = number of
samples, and frequency sampling interval W = 2/NT,
k = kW
ControlNumber
Discrete and Fast Fourier Transforms
(continued)
 Sampling frequency fs = 1/T
 Frequency resolution Df = 1/NT = fs/N
 For accurate results, sampling theorem tells us that
sample frequency fs > 2 x fmax, the highest frequency in the
signal
– Implies that highest frequency captured fmax < 1/2T = fs/2
• Otherwise aliasing will occur
 To improve resolution, note that you can't double sampling
frequency, as that also doubles N (for same piece of
waveform)
– The only way to increase N without affecting fs is to
increase acquisition time
68
ControlNumber
Discrete and Fast Fourier Transforms
(continued)
 Note that DFT calculation requires N separate summations,
one for each k
 Since each summation requires N terms, number of
calculations goes up as N 2
– Therefore doubling frequency resolution requires
quadrupling number of calculations
 Method also assumes function f(t) is periodic outside time
range (nT) considered
 Also note that raw DFT calculation gives array of complex
numbers which must be processed to give usual magnitude
and phase information
– When only power information required, squaring
eliminates complex terms
69
ControlNumber
70
Inverse discrete Fourier transform
 Calculated in straightforward manner as
1
f (tn ) 
N
N 1
j k t n
F
(
j

)
e
, n  0,1,2, N  1

k
k0
 This gives, of course, the original sampled values of the
function back
– Other values can be determined by appropriate filtering
ControlNumber
71
Uses of DFT
 DFT usage may be visualized as
Power Spectral Density
Power Spectrum
Magnitude
Phase
DFT Spectrum
ControlNumber
Power measurements and DFT
 Power spectrum
– Gives energy (power) content of signal at a particular
frequency
– No phase information
– Squared magnitude of DFT spectrum
72
ControlNumber
Power spectral density
 Derived from power spectrum
 Generally normalized in some fashion to show relative power
in different ranges
 Measures energy content in specific band
73
ControlNumber
Fast Fourier Transform (FFT)
 Developed by Cooley and Tukey in 1965 to speed up DFT
calculations
 Increases speed from O(N2) to O(N log N), but there are
requirements
 Useful reference: http://www.ni.com/swf/presentation/us/fft/
74
ControlNumber
Fast Fourier Transform (FFT)
(continued)
 Requirements for FFT
– Sampled data must contain integer number of cycles of
base (lowest frequency) waveform
• Otherwise discontinuities will exist, giving rise to
“spectral leakage”, which shows up as noise
– Signal must be band limited and sampling must be at high
enough rate
• Otherwise “aliasing” occurs, in which higher
frequencies than those capturable by sampling rate
appear as lower frequencies in FFT
– Signal must have stable (non-changing) frequency
content
– Number of sample points must be power of 2
75
ControlNumber
76
Spectral leakage
No discontinuities
Discontinuities present
Source: National Instruments
ControlNumber
Fast Fourier Transform (FFT)
(continued)
 We will not discuss exactly how the method works
 Lots of software packages are available
– See this site for many of them
http://ourworld.compuserve.com/homepages/steve_kifowi
t/fft.htm
– Contained in Mathcad package
– Also available in many textbooks
– Many modern instruments such as digital oscilloscopes
have FFT built-in
 Averaging is frequently used to improve result
– Averages over several FFT runs with different data sets
representing same waveform
• Sometimes with slightly staggered start times
77
ControlNumber
FFT (continued)
 Also inverse FFT exists for going in opposite direction
 Short Mathcad demo
 Note that output of FFT is two-dimensional array of length ½
number of sample points + 1
– The points in this array are the complex values F(jk)
– But the k values themselves do not appear
• Must be calculated by user
• They are k = k x frequency resolution = k x 2/NT,
k = 0...N/2
78
ControlNumber
79
FFT examples showing different
resolution
f(x)=sin (x/5), analysis done in
MATHCAD
10
10
9.371085
8
8
6
6
d
dd
jj , 2
0.010797
10
j,2
4
4
2
2
5.398305 10
0
0
0
0.1
0.2
0.3
0.4
dd
jj , 1
32 sample points, T=1 sec, fs=1
resolution 1/32 Hz
0.5
3
0
0
0
0.1
0.2
0.3
0.4
d
j,1
64 sample points, T=1 sec, fs=1
resolution 1/64 Hz
0.5
0.5
ControlNumber
80
Fourier analysis: a deeper view
 Fourier series only one possible way to analyze functions
 Best understood in terms of functional analysis
 Let X be a space composed of real-valued functions on some
interval [a,b]
– Technically, the set of Lebesgue-integral functions
– Infinite-dimensional space
 Define an inner product (“dot product” in Euclidean space)
as follows:
x, y   x( t) y (t ) dt
b
a
ControlNumber
81
Fourier analysis: a deeper view
(continued)
 This induces a norm on the space
x  x, y
1/ 2
1/ 2
  x (t ) dt 
a

b
2
 Can be shown that this space is complete
– Complete normed space with norm defined by inner
product is known as a Hilbert space
 An orthogonal sequence (uk) is a sequence of elements uk of X
such that
ui , u j  0, i  j
ControlNumber
82
Fourier analysis: a deeper view
(continued)
 This series can be converted into an orthonormal sequence
(ek) by dividing each element uk by its norm ||uk||
 Consider an arbitrary element x  X, and calculate
 k  x, ek
 Now formulate the sum

xn    k ek
k 0
1 as n, the sum converges to x
 Then clearly if ||x-xn||
ControlNumber
83
Fourier analysis: a deeper view
(continued)
 We have the following theorem: If (ek) is an orthonormal
sequence in Hilbert space X, then

(a) The series   k ekconverges (in the norm on X) if and
k 1
only if the following
series converges:


k
k 1
(b) If the series 
converges, then the coefficients k
 k ek
coefficients
are the Fourier
so that x can be written
k 1
x, ek

xn   x , ek ek
k 1
ControlNumber
84
Fourier analysis: a deeper view
(continued)
(c) For any x  X, the foregoing series converges
 Lemma: Any x in X can have at most countably many
(may be countably infinite) nonzero Fourier coefficients
x, ek
with respect to an orthonormal set (ek)
 Note that we are not quite where we want to be yet, as we
have not shown that every x  X has a sequence which
converges to it
– For this we require another notion, that of totality
ControlNumber
85
Fourier analysis: a deeper view
(continued)
 Note also that as of this point we have said nothing about
the nature of the functions ek
– Any set which meets the orthogonality condition
is OK, since it can be normalized
ui , u j  0, i  j
– Note that (sin nt), (cos nt) meet condition, can be
combined into new set containing all elements by suitable
renumbering
– Lots of other functions would work as well, such as
triangle waves, Bessel functions
ControlNumber
Fourier analysis: a deeper view
(continued)
 Most interesting orthonormal sets are those which consists
of “sufficiently many” elements so that every element in the
space can be approximated by Fourier coefficients
– Trivial in finite-dimensional spaces: just use orthonormal
basis
– More complicated in infinite dimensional spaces
 Define a total orthonormal set in X as a subset M  X whose
span is dense in X
– Functions analogously to orthonormal basis in finite
spaces
– But Fourier expansion doesn't have to equal every
element, just get arbitrarily close to it in sense of norm
86
ControlNumber
87
Fourier analysis: a deeper view
(continued)
 Can be shown that all total orthonormal sets in a given
Hilbert space have same cardinality
– Called Hilbert dimension or orthogonal dimension of the
space
– Trivial in finite dimensional spaces
 Necessary and sufficient condition for totality of an
orthonormal set M is that there does not exist a non-zero
x  X such that x is orthogonal to every element of M
xM x0
ControlNumber
88
Fourier analysis: a deeper view
(continued)
 Parseval relation can be expressed as

x, ek
2
 x
2
k
 Another theorem states that an orthonormal set M is total in
X if and only if the Parseval relation holds for all x
– True for {(sin nt)/, (cos nt)/ terms
– Therefore these terms form total orthonormal set
 Key results
– Fourier expansion works because {(sin nt)/, (cos
nt)/}terms from orthonormal basis for space of functions
– Any other orthonormal set of functions can also serve as
basis of Fourier analysis
ControlNumber
89
Fourier analysis: a deeper view
(continued)
 Effect of truncating Fourier expansion
– Finite set (e1...em) no longer total
– But it can be shown that the projection theorem applies
Function f(x) to be approximated
Approximation error
Approximation fm(x)
Space spanned by (e1...em)
ControlNumber
Fourier analysis: a deeper view
(continued)
 Projection theorem states that optimal representation of
f(x) in lower-order space obtained when error ||f – fm|| is
orthogonal to fm
 This is guaranteed by orthonormal elements ei and the
construction of the Fourier coefficients
 Therefore truncated Fourier representation is optimal
representation in terms of (e1...em)
 References:
– Erwin Kreyszig, Introductory Functional Analysis with
Applications
– Eberhard Zeidler, Nonlinear Functional Analysis and its
Applications, Vol. I, Fixed-Point Theorems
90