Fourier theory made easy (?)
Download
Report
Transcript Fourier theory made easy (?)
Sampling theory
Fourier theory made easy
Sampling, FFT
and Nyquist
Frequency
A sine wave
8
5*sin (24t)
6
Amplitude = 5
4
Frequency = 4 Hz
2
0
-2
-4
-6
-8
0
0.1
0.2
0.3
0.4
0.5
seconds
0.6
0.7
0.8
0.9
1
We take an
ideal sine wave
to discuss
effects of
sampling
A sine wave signal and correct sampling
8
5*sin(24t)
6
Amplitude = 5
4
Frequency = 4 Hz
2
Sampling rate = 256
samples/second
0
-2
Sampling duration =
1 second
-4
-6
-8
0
0.1
0.2
0.3
0.4
0.5
seconds
0.6
0.7
0.8
0.9
1
We do sampling of 4Hz
with 256 Hz so sampling
is much higher rate than
the base frequency, good
Thus after sampling we can
reconstruct the original signal
An undersampled signal
Here sampling rate is
8.5 Hz and the
frequency is 8 Hz
Sampling rate
Red dots
represent
the sampled
data
sin(28t), SR = 8.5 Hz
2
1.5
1
0.5
0
-0.5
-1
-1.5
-2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
Undersampling
can be confusing
Here it suggests
a different
frequency of
sampled signal
Undersampled signal can confuse you about its frequency when reconstructed.
Because we used to small frequency of sampling. Nyquist teaches us what should
be a good frequency
The Nyquist Frequency
1. The Nyquist frequency is equal to one-half
of the sampling frequency.
2. The Nyquist frequency is the highest
frequency that can be measured in a
signal.
Nyquist invented
method to have a
good sampling
frequency
We will give more
motivation to Nyquist and
next we will prove it
Fourier series is for periodic
signals
• As you remember, periodic functions and
signals may be expanded into a series of
sine and cosine functions
http://www.falstad.com/fourier/j2/
The Fourier Transform
• A transform takes one function (or signal)
and turns it into another function (or signal)
The Fourier Transform
• A transform takes one function (or signal)
and turns it into another function (or signal)
• Continuous Fourier Transform:
close your eyes if you
don’t like integrals
The Fourier Transform
• A transform takes one function (or signal)
and turns it into another function (or signal)
• Continuous Fourier Transform:
H f h t e
h t H f e
2ift
dt
2ift
df
The Fourier Transform
• A transform takes one function (or signal)
and turns it into another function (or signal)
• The Discrete Fourier Transform:
N 1
H n hk e
2ikn N
k 0
N 1
1
2ikn N
hk H n e
N n 0
Fast Fourier Transform
1.
The Fast Fourier Transform (FFT) is a very efficient
algorithm for performing a discrete Fourier transform
2.
FFT principle first used by Gauss in 18??
3.
FFT algorithm published by Cooley & Tukey in 1965
4.
In 1969, the 2048 point analysis of a seismic trace took 13 ½
hours.
5.
•
Using the FFT, the same task on the same machine took 2.4 seconds!
•
We will present how to calculate FFT in one of next lectures.
Now you can appreciate applications that would be very
difficult without FFT.
Examples of
FFT
Famous Fourier Transforms
2
1
Sine wave
0
-1
-2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
In time
300
250
200
Delta function
150
100
50
0
0
20
40
60
80
100
120
In frequency
Calculated in real time by software that you can
download from Internet or Matlab
Famous Fourier Transforms
0.5
0.4
0.3
Gaussian
0.2
0.1
0
0
5
10
15
20
25
30
35
40
45
50
In time
6
5
4
Gaussian
3
2
1
0
0
50
100
150
200
250
In frequency
Famous Fourier Transforms
1.5
1
Sinc function
0.5
0
-0.5
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
In time
6
5
4
Square wave
3
2
1
0
-100
-50
0
50
100
In frequency
Famous Fourier Transforms
1.5
1
Sinc function
0.5
0
-0.5
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
In time
6
5
4
Square wave
3
2
1
0
-100
-50
0
50
100
In frequency
Famous Fourier Transforms
1
0.8
0.6
Exponential
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
In time
30
25
20
Lorentzian
15
10
5
0
0
50
100
150
200
250
In frequency
FFT of FID
1. If you can see your NMR spectra on a computer it’s because they are in a
digital format.
2. From a computer's point of view, a spectrum is a sequence of numbers.
3. Initially, before you start manipulating them, the points correspond to the
nuclear magnetization of your sample collected at regular intervals of time.
4. This sequence of points is known, in NMR jargon, as the FID (free
induction decay).
5. Most of the tools that enrich iNMR are meant to work in the frequency
domain; they are disabled when the spectrum is in the time domain.
6. Indeed, the main processing task is to transform the time-domain FID into a
frequency-domain spectrum.
t
F t sin 2ft exp
T 2
FFT of FID
2
T2=0.5s
1
SR=sampling
rate
0
f = 8 Hz
SR = 256 Hz
T2 = 0.5 s
-1
-2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
In time
70
60
50
40
30
20
10
0
0
20
40
60
80
100
120
In frequency
FFT of FID
t
F t sin 2ft exp
T 2
2
f = 8 Hz
SR = 256 Hz
T2 = 0.1 s
1
T2=0.1s
Effect of
change of T2
from previous
slide
0
-1
-2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
14
In time
12
10
8
6
4
2
0
0
20
40
60
80
100
120
In frequency
FFT of FID
T2 = 2s
t
F t sin 2ft exp
T 2
Effect of
change of T2
from previous
slide
2
1
0
-1
-2
f = 8 Hz
SR = 256 Hz
T2 = 2 s
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
In time
200
150
100
50
0
0
20
40
60
80
100
120
In frequency
Effect of changing sample rate
Change of
sampling rate, we
see pulses
2
1
0
In time
-1
-2
f = 8 Hz
T2 = 0.5 s
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
70
35
60
30
50
25
40
20
30
15
20
10
10
5
0
0
10
20
30
40
50
60
0
In frequency
• Lowering the sample
rate:
Effect of changing sample rate
SR = 256 kHz
– Reduces the Nyquist
frequency, which
SR = 128 kHz
• Reduces the
maximum
measurable
frequency
• Does not affect the
frequency resolution
2
SR = 256 Hz
SR = 128 Hz
1
0
-1
-2
Circles appear more
often
0
0.2
0.4
0.6
0.8
1
1.2
f = 8 Hz
T2 = 0.5 s
1.4
1.6
1.8
2
70
35
60
30
Peak for circles and crosses in
the same frequency
50
40
25
20
30
15
20
10
10
5
0
0
10
20
30
40
In time
50
60
0
In frequency
Effect of changing sample rate
• Lowering the sample rate:
– Reduces the Nyquist frequency, which
• Reduces the maximum measurable frequency
• Does not affect the frequency resolution
To remember
Effect of changing sampling duration
2
1
0
-1
-2
f = 8 Hz
T2 = .5 s
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0
2
4
6
8
10
12
14
16
18
20
In time
70
60
50
40
30
20
10
0
In frequency
Effect of reducing the sampling duration
from ST = 2s to ST = 1s
ST = Sampling
Time duration
2
1
ST = 2.0 s
ST = 1.0 s
0
-1
-2
f = 8 Hz
T2 = .5 s
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0
2
4
6
8
10
12
14
16
18
20
In time
70
60
50
40
30
20
10
0
In frequency
•
Reducing the sampling duration:
–
–
Lowers the frequency resolution
Does not affect the range of frequencies you can measure
Effect of changing sampling duration
• Reducing the sampling duration:
– Lowers the frequency resolution
– Does not affect the range of frequencies you
can measure
To remember
Effect of changing sampling duration
T2 = 20 s
2
1
0
-1
-2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
In time
200
150
100
50
0
f = 8 Hz
T2 = 2.0 s
0
2
4
6
8
10
12
14
16
18
20
In frequency
Effect of changing sampling duration
T2 = 0.1s
2
ST = 2.0 s
ST = 1.0 s
1
0
f = 8 Hz
T2 = 0.1 s
-1
-2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0
2
4
6
8
10
12
14
16
18
20
In time
14
12
10
8
6
4
2
0
In frequency
Measuring multiple frequencies
3
2
f1 = 80 Hz, T21 = 1 s
f = 90 Hz, T2 = .5 s
1
f3 = 100 Hz, T23 = 0.25 s
2
2
0
-1
-2
-3
SR = 256 Hz
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
In time
120
100
80
60
40
20
0
0
20
40
60
80
100
120
In frequency
conclusion: you can read the main frequencies
which give you the value of your NMR signal, for
instance logic values 0 and 1 in NMR –based
quantum computing
Good sampling
is important for
accuracy
Measuring multiple frequencies
3
2
f1 = 80 Hz, T21 = 1 s
f = 90 Hz, T2 = .5 s
1
f3 = 200 Hz, T23 = 0.25 s
2
2
0
-1
-2
-3
SR = 256 Hz
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
In time
120
100
80
60
40
20
0
0
20
40
60
80
100
120
In frequency
Sampling
Theorem of
Nyquist
Nyquist Sampling Theorem
f x
Continuous signal:
x
Shah function (Impulse train):
sx
s x
x nx
n
0
projected
x
x0
Sampled function:
Sampled and
discretized
f s x f x sx f x x nx0
n
Multiplication in image domain
Sampling Theorem: multiplication in image domain is
convolution in spectral
Sampled function:
image
Sampling
frequency
Shah function
(Impulse
train):
f s x f x sx f x x nx0
1
x0
n
1
n
FS u F u S u F u u
x0 n
x0
FS u
F u
A
A
umax
x0
umax
u
1
Only if u max
1
2 x0
u
x0
We do not want
trapezoids to overlap
Nyquist Theorem
If u max
FS u
1
2 x0
A
x0
Aliasing
u
umax
1
x0
When can we recover F u from FS u ?
Only if u max
We can use
Then
1
(Nyquist Frequency)
2 x0
x0
C u
0
u 1
2 x0
otherwise
F u FS u C u and
f x IFTF u
Sampling frequency must be greater than
2umax
Nyquist Theorem;
We can recover F(u)
from Fs(u) when the
sampling frequency is
greater than 2 u max
Aliasing in 2D image
High
frequencies
Low
frequencies
Some useful links
•
•
•
•
•
•
http://www.falstad.com/fourier/
– Fourier series java applet
http://www.jhu.edu/~signals/
– Collection of demonstrations about digital signal processing
http://www.ni.com/events/tutorials/campus.htm
– FFT tutorial from National Instruments
http://www.cf.ac.uk/psych/CullingJ/dictionary.html
– Dictionary of DSP terms
http://jchemed.chem.wisc.edu/JCEWWW/Features/McadInChem/mcad008/FT
4FreeIndDecay.pdf
– Mathcad tutorial for exploring Fourier transforms of free-induction decay
http://lcni.uoregon.edu/fft/fft.ppt
– This presentation
Conclusions
1. Signal (image) must be sampled with high
enough frequency
2. Use Nyquist theorem to decide
3. Using two small sampling frequency leads
to distortions and inability to reconstruct a
correct signal.
4. Spectrum itself has high importance, for
instance in reading NMR signal or speech
signal.