DSP Lecture 13: The Sampling Theorem

so today I want to talk about one of the most fundamental concepts in signal processing which is sampling okay so what I'm mainly going to talk about des is the kind of classical sampling theorem just as a reminder for how that all works and the set up is that you know we're kind of used to thinking about the difference between continuous-time signals and discrete-time signals right so a continuous-time signal which we might also think of as an analog signal is a function of T and the assumption here is that I can choose any real number T I want here and get back any signal value that I want right however in the kind of digital signal processing world we have to deal with an approximation to this underlying continuous-time signal and the way we do that is with a discrete-time or digital signal where I get only certain values of the signal and presumably at regular you know units right so for example MATLAB assumes that these units are spaced out by one unit on the axis right so if you don't tell me anything else it makes you go to get X's 1 X of 2 X of 3 and so on okay so the process of going from a continuous-time signal to discrete-time signal is called sample okay and that's the main topic of today there's a separate issue so sampling is definitely like kind of an x-axis issue or time-domain axis issue there's also an issue on the y-axis called quantization right so we'll talk about that very briefly today when they talk about it later on in future classes but the idea also is that I made a necessarily get kind of infinite resolution in the heights that these signal values can be could be I'm also limited by you know some sort of a chopped-up version of the y-axis not to round myself to the nearest thing that's called quantization right so both of those things are kind of ways of thinking about digitizing either the domain or the range of a signal okay and so most of the time we think about what we call periodic sampling okay so the periodic sampling is simply saying that I obtain a discrete-time signal by sampling a continuous-time signal every capital T units so n is an integer and this capital T is called the sampling period and 2pi over T which I sometimes call Omega S is called the sampling frequency and just as a side note you know this sampling frequency is measured in what's called radians right that is kind of you know worried about the PI's involved right if you want to talk about Hertz you could just look at one over T so the sampling frequency in Hertz is just the reciprocal and pretty much all the time with this class we're going to talk about radians because that's where the mathematics is more natural okay and so sometimes this process of obtaining the discrete-time signal from the potato sign signal is called d to a conversion and going backwards is called A to D conversion right so for example I might take a TS time signal I might feed it into a analog to digital converter or similar to C called the continuous to discrete converter one of the inputs that is the sampling period and what comes out is this this free time okay and so before I start talking about the sampling theorem holies mentioned that in the real world there are often some non-ideal effects that we can still model with the machinery to be important so far right so for example it's not necessarily always true that my sampler you know takes a continuous-time signal and ideally just picks off one value right so this is my continuous-time signal ideally what I want is getting like exactly this value right what I may actually get instead is basically say the average signal over a very very short time cream right so may not be physically possible for the for the sampler to pick off one value it may be picks off you know the average of you know a fraction of a millisecond of values for example okay and so in that case kind of what we're getting is you know so non-ideal effects so one is we may not ideally sample this continuous-time signal we may instead sample some signal that is involved with some kind of tiny impulse response this kind of like the impulse response of the sampler right so instead we may get samples of this slightly kind of blurred out sick right but again knowing that you know knowing that we know how to handle involve signals that's not really a big issue for this I'm going to just going to assume going forward that we do get the ideal samples but you could analyze these slightly blurry samples in this way okay the other non-ideal effect is that we may have noise which means that instead of getting exactly this value I may get you know this value instead right so just due to noise in the system I might not get exactly what I asked for right and so kinda what this means is that my discrete i/o signal may be some sort of a you know so if I let this thing equal Y of T right this whole thing here what I may be getting is you know a sampled version of a blurry signal plus some sort of a you know noise term that I can't control okay so you know life is not always so ideal but in this case we're going to assume everything's good okay okay so it's kind of straightforward about how do we do the sampling right I decide my thing that picks off the values the thing that's of interest to us at this class right now is how would I go back from the digital values to the continuous-time signal right because you know the whole hypothesis here is that we can use DSP and stuff that we do in MATLAB and chips as a substitute for the ideal continuous time processing of more continuous-time signals right and so to do that we have to kind of have some confidence that the digital signals adequately represent the continuous-time signal okay and so kind of a central topic is reconstruction so so basically how to you know how to recreate or maybe their way to say with the estimate the continuous-time signal given the discrete-time samples and so clearly that's kind of a many to one or one to many kind of problem right so i mean if i give you some samples there are lots of ways that i could hypothesize a continuous-time signal that went through those samples right this is kind of like an interpolation problem so i mean i could do something really simple like this connect these guys with lines crummy picture this or i could you know kind of like try and make these into bars like a bar graph or i could even make some sort of like you know crazy signal that could do basically anything in between the samples right and so just for the samples alone there's no way to disambiguate which of these cases i might be in right and that's the fundamental kind of challenge in the sampling theorem is you know what is the signal that we want to reconstruct for a given set of samples okay so let me just say a couple words so certainly there's this sense that if I had sampled the signal fast enough then connecting the dots or making this bar graph maybe use good enough right and so you know some simple estimates have names right so you know one is basically so I'm going to kind of draw the same signal in three different ways here okay so one kind of natural thing is the nearest neighbor right so nearest neighbor basically says you know if I want to fill in the time you know gaps that I have well I should just take the closest sample that I saw of the discrete world right so that mean that I'd have kind of like a bar graph that says okay you know all these samples are closest to this guy then I have a jump and all these samples are closest to this guy and so on right this is called nearest neighbor interpolation this is you know maybe not entirely palatable because for example for some of these signals right so for these singles over here I have should actually have to look into the future to find out where the nearest sample is right so I have this kind of half sample offset that's not causal and so the natural modification of that is just to say okay you know to reconstruct the signal I just use the most recent value that I saw right so I basically just hold on to this and when I see a new signal I hop up to the new value right so this is like basically the nearest neighbor but offset by half a sample and this is called zero order hold and you know then you can start to think about okay well I could do better by instead of just kind of like having these stairs W functions by connecting the dots right so connecting the dots gives me perhaps a slightly better approximation and this is called first order hold and is also called linear interpolation right and so for those of you that have done like your graphics and stuff like that you know that there are even higher order things I could do right so for example you heard of a cubic spline that's what people in graphics use to connect up the discrete points that you have that define the surface of the 3d mesh into a smoother looking continuous surface right and so in that case it's really like a cubic polynomial that goes through you know points and so in order to make that cubic spline I'm not just using my nearest neighbors I'm using multiple neighbors that are further away from me right so you can kind of make smoother and smoother interpolations if you're willing to consider more and more of your neighbors as what comes down to okay so I pause and ask any questions on these guys so far all right so one thing that's kind of interesting to think about and that plays into the way that we talk about the sampling theorem is that each of these reconstructions you can think of as taking the original samples and convolving them with some special kind of baseline like a kernel okay and so what I mean by that is you know let's think about let's go about this guy for a second zero order hold right so what I can do and here what I'm going to do is I'm going to draw this guy instead of dots as Delta functions okay and this is kind of the this is kind of the critical thing that lets us convert between digital and continuous right so it is that you know in MATLAB I have this continuous-time set of you know stick figures these stem plots right to think about analyzing that in a more principled way we think about the relationship between those samples and Delta functions in continuous-time that just happen to fire at those sample locations and have the putz okay and so if I was to take this thing and I was to convolve it right spending about this as a function of T and if I think about convolving that with this function here so here I'm going to kind of label these guys right this is like actually actually I should be more proper if I think about these as being every capital T interval so here I should be really explicit about the sampling frequency right so forget about these guys right this is like saying if I take a little pulse that is you know capital T units wide and I can valve it with this I'm going to produce exactly this picture right and so in some sense this zero order hold is a reconstruction that I obtained by taking my original samples and involving them with this special kind of baseline simple signal and I can think about each of these guys in a similar way right so here you know this thing in a similar way is what I would have gotten if I taken these same Delta functions and here instead involved it with again we're thinking about one way I think about this is kind of like a impulse response of a filter that does the reconstruction right and so here like I saw you earlier we like the zero order hold because it's causal right that means that the simple response shouldn't have any values that are on the negative side of the T axis right whereas here I know this is that pulse that means I'm looking at half unit back into the past and so here the corresponding guy here is this pulse shifted by you know T over 2 right this one is a little harder to visualize so what this guy has to do is take into account both of my bonus taken into account you know here this guy has to look this direction and this direction of both of these samples right and so it turns out that the corresponding signal for the kind of a pulsing sponson sampler looks like this and you can kind of convince yourself why that's true so the is for example let's suppose that I you know place that triangle yeah but I place a triangle right on top of one of these Delta functions I get exactly that guy because there's no overlapping the triangle in any other function when I move the triangle a little bit over that's like saying okay I get you know I guess I kind of made this tiger a little hard to understand let me kind of zoom in here right so suppose I have this guy and this guy when I move the triangle over kind of halfway that's like saying that the triangle is normally this slide if I move it over kind of half a unit that's like saying that I'm taking you know half of this sample plus half of that sample and if I move it over even further that's like saying I take you know like a quarter of the sample plus three quarters of that sample until finally the triangle is on top of the next in Holmes right if you kind of see that the triangle is always going to weight the two adjacent samples in terms that add up to one right so I'm always taking alpha plus one sample plus one by yourself at times the others down and so you can imagine that more and more fancy interpolation methods involve kind of more and more complicated you know reconstruction impulse responses right and so the preview right is that the actual true correct interpolation in those response is going to be a sinc function in the time domain right which would correspond to a pulse in the frequency so we're going to show why that works in just a second but the idea is basically that all we're doing is we're choosing kind of like the correct thing to convolve the time to main impulses with to get the reconstructed signal okay so now I want to talk about you know reconstruction right perfect reconstruction is our goal we would love to be able to take original samples and get back exactly the original time domain signal right and so it kind of seems like okay well let's suppose that I have even just like a sinusoid so let's goes I have like a sinusoid and I sample it like super finely okay blah blah blah okay so you know this looks pretty good right I mean in fact it seems like a pretty credible argument that if these samples were close enough together then connecting the dots should get me pretty close to the original signal right if they were like super close together then you know maybe sure I wouldn't get exactly the same signal but I'll get so it was pretty close right and so that's true and what I'm going to call this it's kind of like the good case right so life is good here that you know if the samples were close enough together there wouldn't be any real ambiguity about what the underlying signal was right okay but the problem is that there's also kind of a bad case okay and here's the kind of text my drawing powers that I'm going to show you a MATLAB example of second okay so what's the first that I have a really high frequency sinusoid and I sample it like every you know once in a while that is like the best picture that I ever drew when I try and draw the back case a little bit a little bit worse all right so again we have a high frequency side to side let's sample like really far apart this is more like okay so I get this sample at the sample the sample okay and now if I was have to naively connect the dots this is where the crappy quality of my drawing will suffer so you know my connecting the dots might give me some sort of a weird signal that appears to have lower frequency than the underlying sinusoidal right I wouldn't be able to capture all the wiggliness that's going on between the dots I'm going to show you an actual example this in MATLAB that is actually a lot better than this actually quite instead of just promising I'm going to do it when others do it okay so for example here is a tiny size right and so here what I've done is I'm showing you different possibilities for what the reconstruction looks like so the blue is the original signal the green is the reconstructed signal under different circumstances right and so here the green is simply the zero order hold meaning that I hold the sample that I was on you can see they had kind of a crummy reconstruction here is something you know that I would get if I try to connect the dots and what I'm going to do is I'm going to be a little bit more aggressive about this right so here's an example where should I get one where I can show you the buttons here here right seers case where I'm sampling too slow right and the green samples are hitting the blue sinusoid you know at the correct places but when I kind of connect the dots what I get is this appearing Li low-frequency sinusoid right and that's exactly the problem right is that without knowing anything about an underlying signal there's no way for me to tell a priori am I in the good case where it appears examples are really close together or the bad case when the samples are really far apart right the problem is I don't know anything about what's happening between the samples right and so if I were to go back to my kind of sketch you might say oh okay well you know let's suppose I got my samples and they look like this the problem is that you know if I were to zoom and enhance this picture right it could be that you know then in between like this region then it might look like my samples are comparatively far apart and who knows what the signal could be doing you know could be oscillating wildly in between the samples that I have right so the problem is that I don't know without putting more restrictions on the problem am I in the good case or am I in the bad guys and so the only way out of this problem is to put some restrictions on the input signal say I am NOT going to tolerate any crazy wiggling between my samples right that means I have to kind of say that my input signal is restricted in some way okay and that's what the band-limited redundancy so I play pause for a second just on the big picture does this make sense okay so okay so here's the assumption that makes everything kind of come together and that is a problem so we're going to say a signal is band limited if there's some frequency Omega B such that the continuous-time fourier transform is zero for omega you know outside this interval right that means that my continuous-time fourier transform looks something like this okay so between minus Omega D and Omega B I have some content outside of that range I have nothing okay and so again in all the stuff I'm going to draw right now the reason I'm kind of drawing these these signals is approximately symmetric is because I assume that I have an approximately real signal and what I'm kind of drawing here is something like you know the magnitude of the continuous-time fourier transform we know that there are these symmetries and the Fourier transform that mean these are actually complex numbers so here I'm just kind of getting across the sketch of the picture okay okay and so let's talk about what happens when I sample a signal that looks like this okay and this is the famous sampling theorem okay so so famously gets its own sheet okay so this was basically you know attributed widely to Shannon Claude Shannon father Grayson theory and also Nyquist who talked about this idea even earlier than that okay and so here's the theorem a band limited signal with maximum frequency Omega B can be perfectly reconstructed from samples I would say for people in state samples if the sampling frequency Omega s satisfies Omega s greater than 2 Omega V ok and 2 Omega B is called the Nyquist rate right so another way of saying this is that a signal given certificate samples if I sample above the Nyquist rate okay and the Nyquist rate is related to the highest frequency present in the underlying signal okay and so let's prove why this is true now we're going to prove why it's true and number two we're going to show explicitly how that reconstruction could be obtained okay and let me just make a note that you have to sample faster than the Nyquist rate like you can't sample at the Nyquist rate that is sometimes good enough but sometimes will not do it for you okay I'll show you example of why sometimes sampling at the Nyquist rate could be bad okay so the key idea is suite after sample period in my screen this is a common kind of what's the word you know tricky true/false kind of chest question where I ask you you know could I sample this would it work kind of thing okay and so now we have to kind of think back for a second to some of the stuff we talked about when we did the Fourier transform long ago so now the key idea is that what I need to do is I have a continuous-time signal right so here's my underlying continuous-time signal and here's my discrete-time signal which is basically sampling the sky every two units and so kind of my proxy for this discrete-time signal is going to be a signal where i multiplied the continuous-time signal by a set of Delta functions right so if I were to multiply this thing and here I mean multiplying volution in the time domain if I just multiply this by this set of impulse functions that are separated out by capital T and they have height one the effect of multiplying this by this is simply to pick off the values that I want right so kind of what I'm doing is I'm making kind of a proxy continuous-time signal that clearly is basically the same as my discrete-time signal just with Delta function arrows replacing my stem pot dots okay so kind of what I'm going to talk about is okay so how could I get from this signal back to the signal okay again in this form this kind of brings it back to the sketch I drew earlier of I'm altima to convolve this time domain signal with some special you know reconstruction filter that's going to get me back to here okay all right so in order to do this what I have is that my you know let me call this kind of D of T so what I have is that my sampled signal is like my continuous signal times this impulse train right and so in order to think about these things in the frequency domain I need to know what is the Fourier transform of this right because here what I'm doing is multiplying in the time domain that means I'm involving the original signal in the frequency domain with whatever the Fourier transform this is right and so as a reminder if you look back in your notes or videos if I have this in my time domain and this is that good I'm lecturing well hungry should head out another donut okay so this is the time domain what is the frequency domain version of us remember again everything here is in continuous time right so this is a instantly long extending impulse training time and this Omega axis goes off infinitely far too so we showed earlier that the Fourier transform of this is actually another impulse train in the frequency domain and it corresponds to impulses look like this so the height of the impulses is two PI over T which is actually the same as the sampling frequency and the separation between the impulses is every two PI over T units or you can think about these as basically multiples of the sampling frequency okay so again I'm not going to prove this because if you look back in your notes I think we proved this earlier actually just as a as a reference the way you get to here is by thinking about this so this is like a periodic continuous-time signal and it's easy to show that you know if you think about this in terms of what is the Fourier series of this thing it's a constant right because I know that Delta functions correspond to constants and we showed that basically when I have a periodic signal I take the regular Fourier transform of it what I get is basically you know multiples what I basically get is that this is like the a zero coefficient this is like the a one coefficient select the a two coefficient right these are the Fourier series coefficients multiplied by something which it turns out to be the two PI over T and they occur at multiples of the sampling frequency right so if you go back and look at your notes on the Fourier transform of a periodic continuous function this is not too hard okay so let's take a step back now so this is our assumption that this is true okay now what I have is that my sample continuous time signal is my underlying continuous time signal multiplied by this impulse train so in the frequency domain I know that this corresponds to a convolution and this is the corresponding property you may not remember there's a 2pi there because right and so let's think about what that looks like okay well what I kind of just showed was that if I'm being all mathematical about this right what I just showed was that this Delta function thing here was I'm going to write this like two PI over T times the sum from k equals minus invader and finiti of Delta functions that are spaced out every multiple of the sampling producing okay and so I can see some cancellations right so this two pi cancels of this two pi and what happens when I convolve a signal with a delta function well it just shifts the signal right just like saying that I'm going to get a bunch of copies of the original signal at all the places where the Delta function fires right this is like basically saying I'm going to get a whole bunch of periodic copies of the original thing so let's kind of sketch out as a picture what that means oops talked to my finger go back okay so let's interpret this right this is like saying okay let's suppose that I have my original signal and as we're trying to prove the Coase theorem I'm going to assume that this signal is band limited between minus Omega D MD and actually to me to give myself more room maybe I should make that a little bit smaller on the page so I'm going to say like between here here okay so here's my original spectrum of the continuous-time signal so what is this result tell me this tells me I'm going to get a whole bunch of copies of that guy they're going to be one over T as high as they used to be and they're going to occur at multiples of the sampling frequency so if this guy originally had height one my sampled spectrum is going to look like let's suppose I sampled like here and here's my other multiple like this and here's my first copy the first copy is centered at zero because that's definitely an example of a multiple of sampling regency my second copy is over here my third copy is over here and so I think all these guys are going to have height one over T and so the band so this goes out to WB this goes out to Omega s minus Omega B this is Omega S Plus Omega T and so on okay and so this picture is really all I need to help me prove the sampling theorem right because if this is the spectrum of my sample signal it's pretty obvious that all I need to do is to notch out this middle guy so all you need is a filter that kind of crops out the middle guy multiplies that by T in the frequency domain then I get back exactly this guy right so all you do is low-pass filter the sampled signal to get back the original signal right and you can see in this picture why the Nyquist rate is what it is right because what I need is to make sure that this copy here doesn't overlap with this copy here right so the good case is when you know the good case is when this number is strictly greater than this number right that means that things don't overlap and that's exactly the statement of the sampling theorem right that means that this edge and this edge stay away from each other right it's maybe not super clear from the picture why it would be a problem if they were right on top of each other and there show you example that in just a second but this is definitely the good case and Mike and conversely the bad case is when I have copies that are overlapping so you know the bad case is that I sample too slowly too slow and so that's like saying that okay here is my sampling frequency here is my band limit and here this number here you know when I look at this combination of signals unfortunately these signals have overlapped in a way that I can't undo so this is going to be minus Omega s yeah plus Omega P right and so this bad juju over here is aliasing right so that means that if I sample too slowly I kind of garble up high frequencies the original signal and they get mixed up with lower frequencies of the lower copy in the frequency domain and once I've added this stuff together there's really nothing I can do to recover it okay so that's not good so that's kind of the idea is that you know high frequency components appear as low frequency or maybe they compare they combine with low frequency components from a different copy so we don't want to be in that case right that means that we have to be careful to sample fast enough okay so assuming that we do sample fast now that we're in the good case right this case then all we need to do to reconstruct things is to take this signal and multiply it by some nice reconstruction filter so I would call my reconstruction filter something like this where I'd say okay I'm going to knock this guy out I'm going to multiply you know the gain in the frequency domain instance capital T I'm going to call this my reconstruction filter and I can choose this reconstruction filter to kind of be as wide as I want as long as I don't hit any of the you know edges a safe choice if I've done it right should be basically you know half the sampling frequency in general you know this would be like some cutoff but you know here I'm going to choose this particular case right that means I'm going to just notch out this so when I multiply in a frequency domain you know this thing times this thing what I should get is exactly my original so I'm going to call this like X reconstructed Omega again I'm going to get back the right height in the frequency domain and you know this is exactly equal to the original time domain or the original signal right and so life is good and this is why we can see right so basically what I'm doing is I'm multiplying by a pulse in the frequency domain right low-pass filtering basically what is going on in the time domain well I know that a pulse in the time pulse in one domain corresponds to a sink in the other domain and so if I were to go back and think about what's being involved with the original signal right so that's like saying if I have my original signal you know what a Mike involving it with to get back my continuous-time signal well this question mark is going to be some sort of a sink and it turns out that sink looks like this so the sink is got a special structure where it hits zero at every one of these places it's one at zero and so if I kind of carefully draw this what it looks like is something like this right this is basically in the time domain this looks like safe of Pi T over capital T right because at units at multiples of capital T I have in the numerator a sign of some multiple of Pi which is o and 0 and only at T equals 0 might I have a problem but we know the sinc function at 0 is equal to 1 right and so really in the time domain putting it all together what I could say is if I didn't want to go into the frequency domain I could represent the reconstruction process as a convolution so I could say for example that you know X of T should be equal to this kind of sampled version of T involved with the reconstruction filter which is different way of saying something like I'm going to get a sum from N equals minus infinity these are my samples and I'm going to have a convolution sum which means that I'm going to assign like this sinc of I T over like this so this is kind of like you know again this may be a little confusing to look at I don't really change anything this is just like saying that all I'm doing is I am taking my sinc function and to create my output what I'm doing is I am going to kind of draw this again a little bit spaced out the output is actually the sum of a bunch of sinc functions that happen to pass right on tops of these guys here so it's going to cool I think so what's happening is basically to reconstruct the output what I'm doing is I'm centering this special sinc function over every sample and I'm adding those things up and I can see that at each sample the only sinc function that's nonzero is the one that's sitting on top of the sample right so I'm adding a bunch of zeros plus the original sample in between to get like this value here I'm adding a whole bunch of sinc functions that magically add up to the right value right so that's kind of neat I mean the downside is that you can see that in theory to get any of these intermediate values I have to include potentially an infinite number of sinc functions right and so you could argue that okay what I could do is after I've added up you know 56 runs of your side the sinc functions you only pretty small so in practice maybe I can kind of cut off those guys at some point okay that's the idea okay so we pause and ask any questions about any part of this process so hopefully that is not totally unfamiliar to you right you should have seen it in signals but you know now hopefully we're thinking about things more in terms of you know now we know that the samples that we obtain all the samples that were going to use forward for digital signal processing can be related back the original continuous-time samples under the assumption that we've sampled fast we're going to have to look in the next week of lectures to make sure that we never run into problems where we're sampling too slowly okay so let's just do a quick kind of twenty example so let's suppose that we have a cosine okay super simple and I did not bring them have a colored pen against blue or rags like that okay check from the audience all right thank you all right so here I wanna do is just look at a cosine cosine Omega 0 T okay and the reason I want colored pen is we know that I have a pulse you know impulse here and I have another one over here so hopefully you can tell the difference from these colors let's go okay and so the sampling theorem tells me that I need to reconstruct if I want to be through the signal I have to sample faster than twice this frequency right there's only really one frequency president signal and so you know that that's pretty easy so my sampled signal right so the spectrum and I guess I should just pause the size the spectrum I guess I've said the word a few times spectrum is the same kind of thing as looking at the Fourier transform it's the spectrum of a signal it's Fourier transform so the spectrum of the sample signal looks like and here I'm going to kind of zoom out so I'm going to assume that I'm sampling fast enough and I have my middle copy or my answer my right hand copy here this is like Omega S Plus Omega zero this is omega zero this is the minus Omega S Plus Omega zero my other copies look like this all right so this is Omega s minus Omega zero minus Omega zero minus Omega s minus Omega zero right and so I can see that you know life is good so suppose that my Omega 0 was equal to alright so now let's think about the bad news ok so let's suppose that I had a bad situation so this is fast enough so let's suppose I look at the spectrum of the sampled signal you know too slow so for example let's say that my Omega 0 is just 1 and let's suppose I chose my sampling frequency to be 3 over 2 right and so I know by Nyquist that I should be sampling on least 2 to avoid any problems right so this is this is to slow my Michaelis rate is to what does my picture look like well now I can actually put some numbers on here so these are my unit axes so here are my goodness so my original guys are going to look like this right so here's my original these are the original plus or minus Omega zero now if this is my sampling frequency Omega s that means I'm going to get a copy of the signal where I've got a copy over here and a copy over here right so this is basically at plus or minus at 1 or 3 over 2 plus or minus 1 and the same way I'm going to have a copy that comes from here where I'm going to get this guy and this guy right and so here I've seen exactly the aliasing problem right because this number here what used to be a high frequency you know the business of the copy on the high end gets alias down to over here so it used to be something that should be a cosign at high frequency now looks like cosine of 1/2 T so that's bad because what I would do if I didn't know better right is I would say my reconstruction filter my research filter cut off if I chose Omega s over 2 would be 3 over 4 right that would mean that my filter would cut off like this right and if I were to just follow my nose and reconstruct my reconstructed signal would be you know cosine of 1/2 T right not cosine of T so this is an example of aliasing because the problem is that you know my you know D to a converter is just kind of assuming that everything is going according to plan right it doesn't know what signals are coming into it right and so if it's just using its standard Mississippi bike direct reconstruction filter if I feed something in that was sampled too slow it will give me back something that is not my original signal and there's nothing that I can do about it there's no way I can disambiguate this signal coming in versus this signal coming in right so let's just do a quick thought experiment to think about okay well what could go wrong if I sample at the micro screen great right I mean so why can't I have the sampling frequency exactly equal to the Nyquist rate so can we sample right at the Nyquist rate right that's like saying that my Omega s is exactly equal to twice the highest frequency well let's think about a cosine again so let's suppose I have cosine of T right that means that my Omega down limit is 1 that means I sampling frequency is 2 for example so okay so let me draw my cosine so this means that my sampling period is 2 PI over Omega s which is just 1 right that means is justify sorry so here's my cosign and this is 2 pi this is PI this is minus PI this is minus 2 pi so that means that my samples are going to come here here here and so on so this is what's so bad right this looks ok so you know what's the problem right so let's suppose instead that I look at sine T right sine T has the same band limit just like shifting this over so if I have sine T that means that instead I have this guy again I'm going to sample every this is two pi zero minus PI and so on so here again if I sample this signal at exactly the Nyquist rate I'll get samples every PI units right and so my I sampled signal would be identically zero right that's like saying that every time I fire the all the function just happens to hit the zero sine function right and so if I were to reconstruct that there's no way to Rican there's no way to disambiguate the weakest artistical from just being a constant zero right I get the same thing and so this admittedly is kind of like the worst case scenario but the problem is when you look at an input so we don't really know you know what combination of sines and cosines it is right I mean admittedly you could get lucky in this case but you could also get unlucky in this case right so you know worst case scenario you can't sample at the Nyquist rate and an interesting thing that's kind of you know you can think about is in fact you know here's a here's an extreme case of the signal seeming to vanish when I sample another kind of interesting property is phase reversal and so basically we can show if my sampling frequency is less than twice the bandwidth for example if I have X of T being some cosine at this frequency you can prove that the reconstructed signal is a cosine that number one is alias right so I'm going to explain this in just a second right so what happened here so first of all we already knew kind of from this picture that you know what happens when things go wrong right when things go wrong this number here is basically Omega s minus Omega P right this tells me that when I sample too slow the highest frequency appears to be Omega s minus that okay and so that's exactly the same thing as that sorry this is like saying you know lower frequency ascending my sample too slow and the fact that this is a plus P and this is a minus P means that I'm kind of going backwards and kind of what I mean by that is let's suppose here's an example in a real world example so well semi reload so let suppose I've got a camera and I'm filming a wheel and the wheel has a you know a stripe on okay and so this thing is basically rotating let's say plotlines right yes we have discussion about where's clockwise or clockwise okay okay so what happens if I so the Nyquist rate tells me that I had to sample you know quickly relate to this week whatever is if I sample a little bit slowly so suppose my Omega zero suppose that my sampling frequency is kind of you know between the frequency the wheel and twice that rigorously wheel what kind of that what that means is that I'm sampling the wheel a little bit less than once every rotation right so it is that when the real rotates this way I sample it again before it gets to the starting point right so I'm settling it like less than once per rotation so like this would be like my starting image then as it rotates around I would sample this again here and as it goes around here I would sample again here and so on and so according to the camera it would look like the wheel was going down right because you know the line would appear to be going in the reverse direction and this is exactly the phenomenon that when you look at old movies it looks like the wagon wheels are going the wrong way if you look at a car commercial it's like the wheels are going the wrong way or even your eyes can sometimes fool you like that because your eyes have an innate sampling frequency right and this is exactly what's happening is that if your shutter does that sample fast enough and the wheel is going too fast you can easily get these kinds of funky phase reversal things so true story that's why that's one that works okay so let me just show you a couple examples of kind of real-world signals right so here's a little GUI that I wrote again back when I was in grad school so let's take a look at our old friend the dial tone and so what I'm doing here is taking the signal right and so on the top on the top axis you basically see the time domain signal which is since this is a long signal it's you know density sampled it looks like a mess and then the bottom what I'm doing is I'm looking at both the original spectrum and the reconstructed spectrum and so here I have a little drop-down menu that tells me you know what my you know routine searching about the names and so here I can choose whether I want to do zero order hold first order hold or sync interpolation okay so I know that you know Sigma Tribulation is the ideal thing that I should be doing things like zero or hold and first order hold are kind of approximations and so if I try and use them I'm not going to get exactly the right thing back and so here what I'm doing is I'm comparing the original signal so let me turn the volume up a little um recording trying to go didn't seem to make much change actually really alright fantastic so right here this is all the way up awesome alright so this may not be so successful on the on the computer thing but aren't so you guys in care at least okay so what happens if I were to regather to zero order hold and play the resulting signal I get kind of like not quite the right thing and the reason for that is that the zero order hold is not the ideal reconstruction but here let's think about this for a second so my dial tone has component frequencies and so let me just do a little back of the envelope calculation for second so dial tone turns out to have two pure tones at 350 Hertz and 440 Hertz right this tells me that my Nyquist rate by twice so 440 is the highest frequency in a signal that means that twice my micro straight is 880 years okay so let's take a look at my little GUI in my original GUI I'm sampling at 10,000 Hertz right so my my blue signal is way way over sampled right I know I know I need a sample at at least you know 880 and I'm sampling at 10,000 right now here what I have in this other little box is a factor of subsampling this is like saying suppose I take every tenth sample right if I do that I'm still sampling at 10,000 over 10 is 1,000 Hertz right and my Nyquist rate is 880 so that should be perfectly fine and if I change my reconstructed method to sync interpolation then indeed when I Rican start the signal I get exactly the original signal right because I'm sampling about the Nyquist rate everything is good so let's think about this for a second so if I take my ten thousand Hertz and I divide by ten I get a thousand that's still good enough if I take my ten thousand and I sub sampled by a factor of 11 that turns out to be 909 which is still above the Nyquist rate and if I September by twelve then I get 833 right so if I sub settle by 11 should be good by some settle by 12 I should start to have problems and I can kind of predict that what is the problem I'm going to have the problem going to have is that the 440 Hertz sinusoid is going to alias into something it sounds like a lower tone and I can predict that if this is my sampling rate and this is my bandwidth that this thing will turn into something that is 393 Hertz right so I expect this higher tone thing is then get shifted down to 393 and so let's let's verify that actually happens so again some title by a factor of 11 life is still good sub sound by a factor of 12 now you can see that the blue and the green signals are no longer the same when I play them I get think it sounds more like the phone ringing actually and I can see why that's true by zooming in right so this is like saying that the you know if I look at these piece I can see that my lower frequency sinusoid which was originally at 350 that didn't get damaged by anything because I was sampling fast enough for that sinusoid so nothing happened there but the sample the sinusoid that was at 440 got alias down to this green key that wasn't in the original signal and that green peak is exactly where I said it would be like roughly 400 which is actually 393 Hertz right so the system works and kind of I can do this in similar tones right so let's talk about the the phone signal for the phone ringing for a second so here the phone ring if I go back to my back of the envelope so my phone ring has frequencies at 440 and 480 right that means my Nyquist rate is 960 so again that means that subsampling by a factor of you know 10 should be fine subsampling even by a factor of 11 should get me in trouble because that's 909 and if i sub sample by a factor of 12 that's 833 so again if I only had this tone my high frequency would be 880 so sampling by understanding by 12 should probably Elias both of the side your science right so again let's see what happens there so subsampling by 10 life is good subsampling by 11 I should get one sinusoid screwed up funky all right so again I can zoom in on that and I can see that what's happened is one of the sinusoids looks okay the blue higher one got alias down to the green lower one and if I sub sample by 12 then I should see that you know both of the original things get dropped down to lower frequencies and I get you know this is this is the original this is the reconstructed so it's kind of like I'm taking the whole thing and moving it down by you know some number right okay and a more real-world example is if I take here's original signal right so this is a CD quality sample and so CDs are sampled at about forty-four thousand Hertz right and the reason for that is that the well they're a couple of they're a couple of reasons one is certainly true when one of those kind of may be apocryphal so the certainly true reason is that the human auditory system right it varies from person to person but as a young person to whom CDs are marketed your CDs huh so your your ears are probably good to about you know twenty thousand they're a little more Hertz right and so to make sure that you don't miss any of the high frequencies we double that number which comes out to about forty four thousand right the other apocryphal story is that the to it so if you think about me the wire CDs or why were CDs the size that they were the story that went around was that the chairman of Sony who was involved with the CD standard was a big classical music fan and he wanted to make sure he could fit the entire whatever it was Beethoven's fifth or some famous symphony on one CD so that was like that dictated the number of minutes needed and the sampling rate needed and the other constraint was something about how they want to be the diameter of the CD to be approximately the same as the you know quarter to quarter size of a cassette tape which was the other stand at the time right so you can kind of compare them and see they're about the same size right so I don't know if that's true or not but that's and so what happens if i sub samples so so clearly here the original signal has frequencies that are you know the again looking at the blue part you know the frequencies go pretty high if they go certainly again this is this is going up in terms of Hertz they go well above I guess I kind of get back to my but you kind of get back to money here so for example they go well above ten thousand Hertz right so I would need to sample really fast to not introduce any ileus but again the higher frequencies don't have that much energy to them and so if I were to you know let them wrap around low frequencies for a while I wouldn't expect to hear too much distortion right so for example here if I sub sample by like a factor of two right here again this is a good illustration it's kinda hard to see you can see that the video is that the green signal necessarily is band limited by the sampling rate that I've shown right so like I can't ever get a reco certain signal that has higher frequencies than of course by the sampling rate right so here the readings are critical it doesn't really sound that much different than the original and the reason is that the aliased part is taking pretty low energy stuff and bringing it back into here but the more that I create this thing the more these signals are going to start to make the original signal sound distorted so here's this is subsampling at a factor of four so there are a couple things that you expect to hear one is that you expect to hear kind of like a low-pass version of the signal right so you kind of remember from when we did the other demo with music that low-pass filtering an audio signal path takes out the you know symbols and the high frequency sounds and so on so even here you know you might not really notice an audible difference between the original signal and a low pass filtered version original signal but as I cranked it up more you definitely start to hear distortion and that manifested by looking at the time to man seeing the degree in the blue signal start to visibly diverge for each other and so here this is 8 times and so here not only do you get some low pass you kind of thing but you also start to get this kind of weird like crud that seems like it's not part of a low-pass filtered signal right okay serious weird shrieking kind of distortion and as I get further likes let's say I use 15 right so now not only am i kind of buddying up the signal but clearly there's other stuff that's coming in to the signal that's that's all that high-frequency stuff that's getting wrapped around and so in this case this is situation where even though in my drawings I made it look like the only thing that could happen was that the next adjacent copy overlapped into the middle copy if I really sample way too slowly it could be that I get frequency contributions coming from copies that are much further away right so in this case I'm probably wrapping around like four or five times into the part that I'm reconstructing and so after I'm constructing after after I take this to some extreme you know it doesn't sound like a it sounds like you know we're distortion of noise right and so so there's kind of a we're going to talk about this in you know we're gonna talk about this in a couple of lectures but one thing that you can do to kind of mitigate against this is to pre-filter the signal to definitely conforms the Nyquist rate before you do the sampling right so if you want to make sure that you didn't introduce this Distortion what I could do before I do the sampling is low-pass filter the signal to prevent any of those high frequencies for getting involved in the sampling that would be kind of like saying okay let me go back to my MATLAB pictured so what I could do is I could say okay I know that you know I I don't want this to happen right and so what I could do a priori is say I kind of know worst cases where this could be I'm going to take my original signal I'm going to pre filter it by what I know the ideal reconstructed filter has to be and I'm going Li I'm only going to pass this thing within you know the sampler and that means that when I reconstruct I get copies that you know worst case lineup ideally like this by no getting a lease right so I can kind of prevent aliasing by pre-filtering with the right bandwidth and the last thing I want to say is just that now we can really fully draw the connections between continuous assignment is free time which is kind of where I wanted to go from the very beginning right so let's let's revisit big picture right so big picture is that I want to know how to represent a continuous-time signals and if you look at my little MATLAB demo that's exactly what I'm doing right now kind of saying that I have this underlying continuous-time signal how can I be drawing these axes that show me what's happening in continuous-time Hertz right well let's just be really clear about the conversion so that's like saying I have some original signal this is like my original continuous-time fourier transform right maybe that continuous-time signal is band limited now if I sample at some sampling frequency what I get is copies of that signal centered at the sampling frequency now this basically is saying that I assume that my input signal samples are spaced apart by capital T right the sampling period if I think about that signal as a discrete-time signal like that lab in MATLAB those signals going to be spaced apart by units of one right and so basically this is like my dtft right so if I have MATLAB the corresponding Fourier transform MATLAB well I know that DTF T's are two pi periodic right that means that I'm still going to get these periodic looking signals but the copy is always occur at multiples of 2/pi because I know that the signal is two pi periodic and so kind of what I'm doing here is I'm taking the original signal and I'm modifying the frequency axis right so what used to be Omega s comes to PI well used to be Omega B becomes Omega B times Q PI over Omega s right or a different way of saying this is TE times Omega D and then when I take the dtft is if I was using MATLAB the DTF enter the DFT the DFT samples would be like sampling the sky every two pi over n units so this year like DFT samples every two pi over capital n units right and so if I want to draw an approximation to the original Fourier transform of the original signal and I took the dtft and the DFT if I want to know for example you know what does sample n here correspond to in actual Hertz what would I do well I would say that this sample here you know so sample n corresponds to well I would say okay sample n corresponds to the dtft sample at 2pi little n over capital m and then to convert back to this world I have to multiply by the inverse of this right Omega s over 2pi so these two PI's cancel out and I get n Omega s over capital n right and so this tells me that my corresponding you know element of this axis is related to capital n which is like the length of my DFT as related to Omega S which is my sampling frequency original signal and this conversion is exactly what I used to be able to draw this bottom graph in true units of Hertz right that tells me how do I draw the the time axis or the onset frequency axis of that lower graph right so now we have all the pieces in place right so now I feel really good about being able to talk about DFDS right and immediately through this chain go back to what is that what is actually correspond to in terms of Hertz or radians assuming that I sampled fast enough right I think that kind of ties a bow around the whole continuous time discrete time relationship okay so any questions or comments all right great so in that case I will see you guys on

Channel: Rich Radke

Views: 76,828

Rating: 4.9126363 out of 5

Keywords: digital signal processing, rich radke, radke, dsp, rpi, Sampling, Nyquist–Shannon Sampling Theorem

Id: _Z7ErH7UTMs

Length: 76min 24sec (4584 seconds)

Published: Thu Oct 16 2014