welcome back so i'm really excited today to tell
you about the shannon nyquist sampling theorem which is one of the most important
results in all of information theory you're going to see it everywhere now
that i'm going to tell you about it and it's really important especially when we
think about signal processing control systems especially compress sensing and sparsity and kind
of the recent trends in applied mathematics so i'm going to jump in and i'm going to tell you
all about this shannon nyquist sampling theorem which basically tells you if you have some signal
you're measuring some let's say it's some signal that's oscillating and doing something how fast
you have to measure it to perfectly represent and reconstruct that signal okay and there's
really interesting connections to code breaking and other kinds of information theory so um
i i find this a really fascinating topic and i hope i hope you do too so there are two seminal
papers uh by by claude shannon and harry ninequist nyquist was a little bit earlier in 1928
shannon in 1949 both of them worked at bell labs so shannon was an american mathematician
nyquist is a swedish american mathematician and both of them developed a lot of their best
work working at bell labs okay which is kind of this famous think tank where a lot of great ideas
came out of um shannon in particular did a lot of wartime research during world war ii in encryption
and code breaking and just kind of you can kind of think of him as america's counterpart of alan
turing and in fact they were contemporaries and claude shannon loved turing's work because
it complemented his his so well so i think that's that's really interesting uh as well okay
good so they wrote these two classic papers uh communication in the presence of noise and
certain topics in telegraph transmission theory and there was this idea of kind of how much
can you compress information if you want to send it over a long distance and then be able to
decompress it and get the full high resolution uh signal kind of out at the end okay so a really
important problem of their time based on uh on on communication and signal processing over long
distances how much can you compress information and expect to get a faithful decompression
uh kind of downstream on the other end and of course we already had lots of knowledge
about this there was already morse code and some kind of redundancy built into communications
in telegraphing but this really put this on a firm mathematical footing uh claude shannon in
particular uh is many times oftentimes called the father or the the father of kind of information
theory and a lot a lot a lot of what we have in information theory came from claude shannon so
he also took ideas from thermodynamics entropy and introduced that into information theory
so he introduced you know information entropy when you're sending signals over the ocean okay
across the atlantic nyquist was really pivotal in control theory so a lot of our classical control
theory comes from nyquist and a lot of things are named after nyquist so these are two titans that
kind of came together in this idea of of sampling uh for the the sampling theorem okay good um
and i'll just also point out that that shannon you know also was very deeply interested in kind
of this theory of secrecy and the way he said it is that uh kind of communication and cryptography
are inseparable you can't study one without inherently analyzing the other you can't talk
about communication theory without the theory of uh of kind of encoding and coding and cryptography
okay so that's a really interesting perspective uh as well and so i want to kind of just walk
you through what they say the the shannon nyquist sampling theorem is and then how we can
interpret it uh today kind of practically so in in words the sampling theorem says that a function
containing no frequency higher than omega measured in hertz is completely determined by sampling
that function at two omega again measured in hertz so if you have a function and i'm actually
going to say this another way i want to flip it also if you have a function and you want to
perfectly represent that function you want to perfectly resolve all of its frequency content
perfectly then you have to sample that function at twice its highest frequency okay so i'll say
this a couple ways and when we're used to thinking about functions uh like an audio signal you can
take its fourier transform and it's got a power spectrum that tells you where in that signal kind
of what frequencies are active in that signal and if you want to perfectly reconstruct that signal
in fourier remember we can compress that signal and send that information and decompress it if
you want to perfectly represent that information and you have a highest frequency you care about
you have to sample at twice that highest frequency okay and so that establishes what's known now as
the nyquist rate which is two omega measured in hertz or alternatively it says if you care about
a frequency omega if that's the highest frequency you care about you have to sample at least as fast
as a delta t of one over two omega in seconds okay and actually this is really interesting this
is why if you've ever noticed that your audio sampling like your mp3 is encoded at 44 kilohertz
that's because humans can hear up to about 20 kilohertz so you take that highest frequency
humans would ever care about which is about 22 kilohertz and you have to double that uh to get
perfect uh fidelity reconstruction when you uh when you decompress okay so that's that's
why audio signals are at 44 kilohertz. Good, so i'm going to walk you through
pictorially how this sampling works and then we'll talk a little bit more about
applications and where you see this every day. So the idea is that you might have
some signal, and this is a little hard to draw so I'm gonna do my best. Let's say you have
some signal that has a high frequency in it. And by common sense, if you wanted to resolve this
frequency, you might say that you need to pick at least two measurements per period to get the
high and the low. Maybe I'll just draw, to get the highs and the lows of this signal, maybe let
me make sure that this ah that's much better. So you have this signal, and to get the
highs and the lows of the signal you would need to measure at least two points
per period. That's kind of common sense. But I'm going to do the thought experiment:
what if you down-sampled, so you didn't measure fast enough? If you didn't
measure fast enough, so let's say I measure less frequently than I need
to, so I measure maybe now and then now and now. I'm not doing a great job here, but
you would essentially get a signal that could equally well be described by a lower frequency
sine wave. So if you don't sample at this Shannon Nyquist sampling rate, this two times the
highest frequency that you care about, then you're potentially going to miss information, and it
could get even worse than that. Imagine I measure at exactly the frequency of the highest frequency
so instead of at measuring two omega I measure at omega, so I measure just the peak and the peak
and the peak. Then I have no information in this signal, and as far as I'm concerned the signal
might as well be that straight line. And so you can see that there's all this information that's
lost if I don't measure at at least the Nyquist sampling frequency of two omega so that two omega
is critical because otherwise you'll get this phenomenon that is called aliasing. And i'm
going to write that up here. So you'll get this aliasing phenomenon, which basically says
that as far as your sampling is concerned these curves are aliases of one another.
They might as well be the same thing as far as this blue sampling is concerned. So if you
sample below the Nyquist rate you're going to get aliasing and you're going to lose the high
frequency components that you might care about. Now there's a really cool plot that you can
make that kind of shows this idea of aliasing and sometimes this is called frequency folding.
If you look at the power spectral density versus frequency and remember that omega is the
frequency I care about, that's where all of my frequency content... actually I'm going to say
this a little differently. Let's say here omega is what I'm actually sampling at, so I sample
at omega. This is all that I'm able to sample, but let's say that my signal has
frequency content up here at 1.5 omega. If my signal has frequency content
at 1.5 omega, but I sample at omega, what I measure, my measurement at this
frequency is going to look like this. So it's going to look like an aliased version
that's folded over in the frequency domain. I'm going to say this again because this is
a little tricky and a little subtle okay so if i'm measuring at omega at a frequency omega
now based on the sam the the shannon nyquist sampling theorem that says i could only resolve
frequencies that are at half of that sampling rate because i need to sample twice the highest
frequency in my signal so if i sample at omega i can only resolve signals that are half of that
rate but if my actual true data so this is my true data over here had a frequency that was higher
than omega based on this aliasing what's going to happen is it's going to look like i measured
a system that was half of that frequency or 0.5 omega this is going to be kind of the aliased
measurement so from my measurements at frequency omega i couldn't tell the difference between
these two signals and when i fourier transform i'm going to get this erroneous low frequency
behavior so that's exactly what i drew here this high frequency signal was kind of this signal
here but because i didn't measure it fast enough at the nyquist rate because i measured it too
slowly i'm getting this blue erroneous frequency that looks like it's at a lower frequency than it
actually is okay so that's this idea of aliasing you'll see it everywhere in signal processing um
actually if i wore a shirt with like a checker pattern you might get like a really fine like
a dress shirt with a really fine mesh pattern then this camera might actually cause
there to be aliasing so as i walk around from pixel to pixel you'd almost see it
like sparkling that's a weird camera effect that you get sometimes and it's because of
this idea of aliasing so you also see this this is a picture of a curtain i believe this
is at um heathrow airport i think and you can see these kind of these kind of moire patterns
that you see sometimes in optics so this is kind of an artistic and artistic rendition of these
aliasing patterns that you get we also saw this when we looked at the discrete fourier transform
matrix so this is literally a visualization of the 1024 by 1024 dft matrix but when i down sampled
it when i when i just shrunk that image on my computer screen because because i used less
than 1024x1024 pixels you actually see some really interesting aliasing features here i
don't know if you can see it i hope you can it looks like there are almost four periodic roles
in x and three periodic roles in y that's not in the high resolution dft this is purely because of
aliasing because i'm taking this information and i'm not measuring it uh finally enough so that's
another application uh kind of of aliasing okay um so that's really what i wanted to tell you about
is kind of this really interesting uh idea of um of aliasing and and the shannon nyquist sampling
rate it tells you how fast you have to measure a signal to get faithful reconstruction
of the frequency content of that signal uh and so i'm just gonna i should probably write
it out to be completely clear so if you want omega you need to sample at two omega it's
really simple really easy to to remember now what's interesting about this and
i'm gonna kind of close the lecture on where we're at now now fast forward you know
70 80 90 years past shannon and nyquist to today advances in applied math and optimization and
statistics are starting to change how we think about the shannon nyquist sampling theorem so
technically speaking all of the results from shannon and nyquist are for broadband signals
so that means signals that are full jam-packed with frequency content from low frequencies all
the way up to that highest frequency that you care about broadband dense signals that you've
already kind of compressed down so think about signals you've zipped up that is definitely then
the shannon nyquist sampling theorem absolutely applies to those dense broadband signals you can't
beat uh the nyquist sampling theorem and have full perfect signal reconstruction but if your signal
is not broadband or dense if it is only a couple of frequencies that are high frequencies you
technically can in fact sometimes under some conditions beat the the nyquist sampling frequency
on average and i'm going to talk about this more in the context of compressed sensing
and reconstructing audio signals but for now i'm just going to walk you through
at a very high level what we expect to see so here we have a signal f which is the sum
of two sine waves at 73 hertz and 531 hertz and so what the shannon nyquist sampling theorem
would say is that to fully resolve this f i would have to sample twice the highest frequency or
twice 531 which is uh 1062 samples per second that's how fast i'd have to sample to perfectly
reconstruct this signal okay and here's the power spectrum here's the signal now that is technically
only true for broadband signals but this is not a broadband signal this signal is very sparse uh in
the frequency domain there's only two frequency peaks only two tones making up this function and
so you can get away i'm going to zoom in here if i measured uniformly below the
shannon nyquist sampling theorem or shannon nyquist limit if i if i uniformly
sampled below the nyquist sampling rate i would get a terrible signal reconstruction and i
would get this aliasing but if i measure randomly but on average at 128 samples per second
so well below the shannon nyquist sampling rate but if i do it randomly not regularly or
uniformly then results in compressed sensing say that you can actually faithfully reconstruct
the sparse vector in the fourier domain the sparse power spectrum and then you can inverse fourier
transform and reconstruct your full signal essentially with no aliasing so this is a really
cool result in the field of compressed sensing i don't know why this is comped this is
spelled wrong it should be compressed sensing or compressive sampling and the basic
idea is that if i sample randomly in time i can get away with a much lower average sampling rate
than predicted by shannon nyquist if my signal is sparse so i'm going to tell you a lot more about
this you're going to learn about this in kind of this lecture series on compressed sensing so
there's you know there's going to be more about this for you to dig into but the basic idea just
to recap is that if you have a signal f and you care about frequencies up to frequency omega then
you have to sample at two omega or else you're going to get aliasing and you're going to get this
frequency folding phenomenon all right thank you
