Instructor (Brad Osgood):We’re on the air. Pay attention. You should – I think the exams will be back sometime today. I’ll send out a note when everything is all sorted out. I don’t really know how things are gonna turn out yet. I graded my part over the weekend. I graded the first part problem and people did actually quite well on that. I think Rajib is working on it now, and at some point – anyway, I’ll send you a note out when everything’s all set for you guys to pick up. All right? I am going to do a little demo on aliasing today that I didn’t want you to miss. Unfortunately, I loaned my strobe light to somebody, and I can’t find it. I can’t remember who I lent it to, so I can’t give you a demonstration of the spinning fan, which is the classic demonstration of aliasing. If I can get my strobe light back, then maybe we’ll have a chance to do that a little bit later. So I’m gonna give you a demonstration, a slight demonstration, a brief demonstration on what happens when you under sample music, that is when you turn analog music into digital music that we’re all so used to these days, and when you do it the wrong way, or you do not do it accurately enough. So how would you – how rapidly do you have to sample a piece of music in order to be able to interpolate it, in order to be able to reconstruct it digitally? Well, for that we need – sampling. We need to know something about human hearing. That is how high a note you can hear, and that’s roughly about 20 – the bandwidth of – or rather – gonna start that again. You can hear roughly up to 20,000 hertz. That is on the high end. You can hear – dogs go up much higher of course. You can hear up to roughly a note with a pitch 20,000 hertz. That’s way beyond anything you’d really hear musically of course, way beyond where music goes, but that’s roughly the range of the human hearing from about 20 hertz to about 20,000 hertz.
So according to the way we do things then, the bandwidth or the spectrum of – a slice of spectrum of music would go roughly up to say 20,000 hertz and then down to minus 20,000, so the frequency would be – and beyond that it’s essentially zero. At least as far as you’re concerned it’s zero. You can’t hear anything. So if that’s a picture of the spectrum of a slice of music, then it’s between minus 20,000 and 20,000, so the way we write things, that would be P over 2. The bandwidth is 20,000, so P is about 40,000, which means that if you wanna sample and reconstruct music, you should do it roughly at a rate of 40,000 hertz. That is to say you should sample every 40,000th of a second. So this should be the sampling rate for music, roughly 40,000 times per second, or sampled at a rate of one over 40,000 per second in order to be able to have confidence that you are sampling rapidly enough so that your reconstruction based on the sync function is gonna interpolate the actual music. Now in fact, as people probably know, they sample at a rate – for CDs, for example, they sample at a rate higher than that. Do you know what it is off the top of your head? 44.1 or something like that? Is that right? Somewhere around there? In fact, the sampling rate for CDs is whatever it is. I think it’s 44.1 kilohertz. And also, as far as I know, and some of you may know the history of this better than I do, this is – it’s gotta be something bigger than 40,000, all right? But as far as I know, the precise number comes from just the equipment that they were using when they were making the transition from analog to digital. I think the way the tapes – I’m sorry, do you know?
Student:[Inaudible].
Instructor (Brad Osgood):Is that right? Oh, really? The story that I had heard – I tracked this down [inaudible], but I haven’t looked at it really carefully was that everything was set up for analog recording, of course. And the way the machines were set up, it was just most natural to sample at that rate somehow. They got the best – they got the most accurate – most reliable sampling if they did it roughly at that rate, but it was not – that number comes out of practical considerations, not out of any sort of theoretical inspiration. Anyway, that’s how fast you should sample, okay? So here is a well-known piece – and if you sample at less than that rate, then you’re not gonna get an accurate reproduction of the music. So here is Gershwin’s Rhapsody in Blue sampled at a high enough rate, sampled at 44.1 kilohertz. It has a famous clarinet gliss at the beginning. Everybody remember? Everybody heard this? Okay. All right, now – so then – isn’t that nice? Nice way to start the day. So then what we did was sample this at a low rate, I think around 16 hertz – 16 kilohertz. All right? Not 16 hertz, 16,000. Roughly a little less than half of that. Now remember what that means in terms of the picture. For me, as I said many times, the sampling theorem is identical with the proof of the sampling theorem, so I always try to imagine what things look like in the frequency domain, in the spectrum. So that means if the real spectrum goes to that range, you are cutting of like here. So that means you’re cutting off a bunch of high frequencies, so to speak. And what does the proof of the sampling theorem say? The proof of the sampling theorem says to periodize this thing by a Shaw function that has spacing that is too narrow and then cut off.
So if you just take the first shift, if you shift thing over by the corresponding Shaw function, then you’re doing this. You’re getting like that. And then shifting it over the other way, you’re doing that, so when the two signals add, when this adds with its shifted version, you’re getting something that looks like that. And then you cut off – [inaudible] I’m not doing this right. And you cut off like that, so you’re getting some signal – the frequency of the signal that you’re reconstructing, instead of the original spectrum, looks something like that. And they talk about low frequencies being aliased as high frequencies, and high frequencies being aliased as low frequencies. What they mean by that is the lower part of the spectrum here is getting shifted over, and is getting added in as if it were part of the high frequency. So that means the lower frequencies are being aliased as high frequencies because you’re shifting things inadequately to shift this spectrum off itself. So you’re reproducing a signal based on this picture of the frequency instead of this picture of the frequency, and here is what you get. [Inaudible] lower parts are not as affected by [inaudible] distortion is more [inaudible]. You get the idea. The distortion really is more on the high end of things because it’s the high end of things where the overlap’s occurring. You’re cutting it off by not enough. You’re shifting things over. You’re adding up. And there’s more mistake that’s made in the higher part of the spectrum than the lower part of the spectrum. This part of the spectrum is pretty much unchanged. It’s the higher part of the spectrum that’s getting messed up by an inadequate shifting or too low a sampling rate.
And there are all sorts of experiments and tricks you can do with this. Aliasing should not always be thought of as the enemy, by the way. There are times when you wanna alias on purpose. As a matter of fact, there’s a problem I believe on the problem set on the basis for the so-called sampling oscilloscope where you try to sample – if you have a very fast signal to sample, that’s faster than – the frequencies are higher than an ordinary oscilloscope can actually handle, then there are ways of aliasing effectively to get a picture of the signal at a lower – by sampling at a lower rate. So it’s not that aliasing is always the enemy necessarily, but it’s something that certainly has to be understood. Then again, as far as I’m concerned, understanding aliasing is understanding the proof of the sampling theorem, which is what we’ve been talking about. Okay. The other famous example with aliasing is one you had a problem on also, and if I can find my strobe light, we’ll do it sometime because it is sort of fun to do where you freeze a fan going – or you freeze a rotating object that’s rotating periodically. It’s described by a periodic signal. If you sample it inappropriately, say at too low a rate once again, you can freeze it. You’ve probably seen demos like that. It’s very impressive. Okay. And then what I’d really like to do – I have done this before – is do some other examples of sampling and actually spectrum analyzing with a real, honest to god spectrum analyzer, bring my trombone in, bring some other musical instruments in, so you see how they look in the frequency domain. You can also do a bunch of interesting demos on that. We’ll see if we have the time for that. Any questions about that? Anything on anybody’s mind? Okay. So today, it is welcome to the modern world. Today, we’re gonna make the transition from the continuous to the discrete, from the analog to the digital, the modern world. I want to introduce – you’ve actually been using it in – any time you’ve used MATLAB with a Fourier transform you’ve been using it, but now we’re gonna really talk about why it works, and how it works, and where it comes from. I wanna introduce the DFT, the discrete Fourier transform. The DFT – that is to say we’re not saying farewell to the continuous and the analog world, but we are now having a meeting between the two, the old world and the new world. So we wanna move from the continuous and the analog to the discrete and the digital. So we’re moving from the continuous and analog to the digital and discrete, to the discrete and digital.
Now like so much else in this course, there are choices to make. Some people would say this is not a transition at all. You should never have been in a continuous world in the first place, you Neanderthal you. The modern is digital, the modern world is discrete, and you should always understand things in terms of exactly those sorts of operation. That’s a defensible choice, and there are courses actually on digital signal processing where you don’t really talk so much about the continuous case, but everything is discrete and digital right from the beginning, and all the formulas go that way, all the demonstrations go that way, all the theorems go that way, and so on. So that’s defensible. I don’t like it, and I don’t think it’s ultimately that – I think you miss a number of things by doing it that way, and I don’t think it always simplifies things, but nevertheless, that’s a defensible choice. For us however, we wanna make a transition from the continuous to the discrete, or from the analog to the digital. And in doing so, I wanna leverage I hope on all the hard won skill and intuition that we built up on the continuous Fourier transform. We spent a lot of time and before this class, I’m sure you spent a certain amount of time also on just developing those ideas, understanding analog signals. And what I wanna convince you of is that a lot of that skill that you’ve build up, and a lot of the intuition that you built up carries over. So much so that even there’s a similarity in the formulas. Even the formal aspects of the subject are similar enough in the discrete case that you can carry over what you learned then to what you’re gonna learn now. That’s the other reason for doing it this way is so we can use all that we have learned so far in the continuous and analog case to understand, and help us analyze, and help us work with the discrete and the digital case. So that’s the choice that we made, but it is a choice. It’s not necessarily the only way of doing things, by no means. So here’s how we’re gonna proceed. Here’s the plan. It comes really in three parts. One – so I have – you’re starting off with continuous signals, so FFT is a continuous signal as usual. There’s a continuous signal. When I say that, I’m not meaning it in a formal mathematical sense. I’m thinking of it as a function of a continuous variable T, and that’s what’s gonna get replaced by a discrete. F is gonna get replaced by a discrete function. All right? Think of this as the analog case.
So the first step is I wanna find a reasonable discrete approximation to FFT. Secondly, I wanna find a reasonable discrete approximation to its Fourier transform. All right? I know how to take the Fourier transform and make a continuous signal. The question is can I discretize that in a reasonable way that’s providing a reasonable approximation. And the third, which really combines the first two steps immediately when you see how the development goes, is to find a reasonable way from passing from one to the other, from the discrete approximation of F to the discrete approximation of the Fourier transform that is the most natural thing to do in this case. That is it approximates the passing from the continuous case, the continuous function of the continuous Fourier transform. So find a reasonable way of passing from the discrete form of F to the discrete form of the Fourier transform that mimics – I won’t write the rest of the sentence down – that mimics the way you pass from the form of F to the signal to its Fourier transform, the continuous version of that. Okay? And again, I wanna make this look as much like the continuous case as possible. There are different ways of making this argument also. There are different choices for how you can execute this. We’re actually gonna base this on the sampling theorem, misapplied a little bit or – yeah, misapplied is probably the right word. So we’re gonna base this – that is to say, I’m gonna base the reasonableness, the test of reasonableness, on sampling. So base this on misuse of the sampling theorem.
Well, the sampling theorem let me say – rather than saying based on a misuse of the sampling theorem, I’m not gonna write down the sync interpolation. I’ll say I’m gonna base it on the misuse of sampling. Here’s what I have in mind. Okay? I’m gonna make some assumptions that I know are wrong right from the outset. I’m gonna assume – but play along – assume first of all that F of T is limited – it’s a time limit signal to zero less than or equal to T, less than or equal to L. Okay. And I’m gonna also assume that the Fourier transform of F is limited to zero less than or equal to S, less than or equal to 2B, so B is the bandwidth, and I’m writing B for bandwidth instead of P. Now both of those assumptions cannot hold together. So you can’t have both together, but play along. This can’t happen. This cannot be because the signal cannot be both time limited and band limited. That’s one thing. The other thing here is that I’m writing the Fourier transform as if it’s only on the interval from zero to 2B. Sorry, you can’t see it very well here. So F of S is limited by zero less than or equal to S, less than or equal to 2B. All right? Now we know the Fourier – that’s what I just wrote there. The Fourier transform is symmetric. You talk about frequencies going from minus B to plus B. The only reason I’m saying from zero to – as between zero and 2B is because of the indexing of the discrete variable that’s gonna go along with this. You’ll see what I mean. All right? So we’re saying this – it’s purely a formal statement just to make the notation a little bit easier in a minute – saying this to make indexing of the discrete variable easier. All right. You’ll see. So just play along.
All right, now – so I have a sample that’s limited in time and limited in frequency. We know that can’t happen, but let’s play along. And what would the sampling theorem tell us? If I wanted to reconstruct F, how many samples would I need? Or rather what should the sampling rate be? Well, the sampling rate to consider myself getting a reasonable approximation of F from its samples is dictated by the properties of F in the frequency domain, that is to say the bandwidth of it. So to get a reasonable discrete approximation of F by sampling, I take samples spaced one over 2B apart. That is the sampling rate should be 2B, and so the samples should be one over 2B apart in the time domain. Okay? So in the time domain, here’s zero, 2B, and the sample should be spaced one over 2B apart. So let’s say there are N of them. Let’s say take N samples. All right? Oh sorry. This is the time domain, so the length of the interval is L. In the time domain, the function is limited from zero to L. I take the sample space, one over 2B apart, so I should have N over 2B is equal to L. That is if I take N samples, and the relationship between N and the number of samples that I take, the spacing, and the length of the interval that they’re supposed to fill up is that, and it’s equal to 2B times L if I take N samples. Okay? And let’s call the samples say T [inaudible] the sample points, T not zero, T1 is equal to one over 2B. T2 is equal to two over 2B. And then I go all the way up to [inaudible] N minus one over 2B. Okay? Those are my sample points. There are N of them indexed from zero to N minus one. So what is the sampled form of F? For us, the sample formed of F [inaudible] function is always multiplying a function by given – by delta function with that spacing. Take F of T times the sum from say K equals zero to N minus one of delta, T minus TK. That’s what we always mean by sampling. All right? So again, the TKs are zero, one over 2B, two over 2B, all the way to N minus one over 2B, so the sum goes from zero to N minus one. So this is sum F of TK delta T minus TK, zero up to N minus one. That’s a sample. We’ll just call that F sample.
That’s still a function of a continuous variable, but it’s recording what we think of as a reasonable approximation to F. It’s a reasonable approximation to F in the sense that the sampling theorem would tell us that if I base my interpolation on those values, I should be able to reconstruct it exactly. That’s why it’s reasonable. And as those points weren’t just chosen arbitrarily, those points were chosen with that spacing because that’s what the sampling theorem would tell us to do. Okay, now the sampled version of F is still a function of a continuous variable. I can take its Fourier transform. All right? That’s not so hard. The Fourier transform of F sample is also a function of the continuous frequency variable S, and that’s just the sum from K equals zero to N minus one of F of TK times the Fourier transform of the delta function which E to the minus – shift the delta function – E to the minus 2p I S T K. Okay? All right, so where are we here? I’ve got what I think is a reasonable approximation to the continuous function in the time domain. I’ve taken this Fourier transform, but the Fourier transform is not yet discretized itself. That’s a function of the continuous variable. So I want to sample or discretize the Fourier transform of F, the Fourier transform of the sample function. Okay? How do I do that? Well, think of the sampling theorem. What would the sampling theorem say again viewed somehow going from the frequency domain back to the time domain? That is think of this as a function that I wanna sample. How rapidly should I sample – never mind that it’s the Fourier transform of something. How rapidly should I sample this thing so the sampling theorem will tell me I’m getting a reasonable discrete approximation of it? That is I’m getting enough sample points so that if I wanted to interpolate it, I’d be getting the function back again.
How to sample this in the frequency domain so you get a reasonable approximation, let’s say – so you get a reasonable let’s say discrete version if I start using that sort of terminology. All right. So in the frequency domain the signal is limited to zero to 2B. All right? How rapidly to sample in that domain is dictated to us by what happens in the other domain where the signal is limited to zero L. How far apart should the sample points be spaced in the frequency domain in order that I get a reasonable approximation if I take samples of those points? It was either an answer or a cell phone ringing. One over L, all right? In the time domain, remember the signal is limited to one over L. All right. In the frequency domain, it’s limited to one over 2B. How fast the sample in one domain is dictated by the properties of the function in the other domain. All right? So the answers will go back and forth here between the function and its Fourier transform, but you should be able to say one or the other in either – I mean talk about one in terms of the other in either direction. So once again, let me say it. To think about how fast a sample a signal in this domain should have to do with what its properties are in the other domain. So I’m not speaking so much in terms of time and frequency here. I’m speaking in terms of the one domain and the other domain. The other domain, the function is limited to zero to L, so in this domain the sample should be taken one over L apart. All right? That’s what the sampling theorem would tell us to do if we were applying the sampling theorem in this direction.
If you take samples spaced one over L apart, spaced one over L, okay – and that’s supposed to cover an interval of length 2B. Okay? How many sample points would I take in the frequency domain? So again, if I have M sample points in the frequency domain, then I have M times – so M points say – then I have M times one over L is equal to 2B. That is M is equal to 2B L. Oh, but that’s N, all right? The number of sample points in the time domain. That is to say – I shouldn’t say N. Suppose M points, then M is equal to N. That is to say I take the same number of sample points from the time domain as in the frequency domain. So again you – that’s what I meant by saying again here. So again in the frequency domain, you again take N sample points. What are they? Then they are space one over L apart, and sample points spaced one over L apart, so they are like S zero is equal to zero, S1 is equal to one over L, S2 is equal to two over L, and so on going on to SN minus one is N minus one over L. Okay? Again, one feels by an appeal to the sampling theorem that if you are sampling the function often enough at those points here, you’re getting a reasonable enough approximation in the sense the sampling theorem would tell you you could reconstruct the function exactly from those sample points. Never mind that all this is being misapplied. Play along. All right? Okay. So what is the sampled version of the Fourier transform of the sampled function? What is the sample form of the Fourier transform of the sample version of F? Well, how do I sample a function? I multiply it by the corresponding delta function. So this would be the Fourier transform of the sample function, F sampled, times the sum of the corresponding delta function I’ve gotta call – what did I call it over there? I called it K in that sum. Let me call it something else, M. M equals zero to N minus one. Again, I have N points delta S minus S K where these are the S Ks, those are sample points. Okay. That’s the sampled version of the Fourier transform. What is that? Let’s write it down. I’m erasing this, but I’m gonna write it again. Oh, there it is. Okay, so the Fourier transform of F sampled once again at S is this sum: sum from K equals zero up to – K equals zero up to N minus one of F of T K, E to the minus 2 p I S T K. All right? So I multiply that by the corresponding delta function – sum of delta functions rather. So this K equals zero up to N minus one, N minus one of F of T K, E to the minus 2 p I S T K times the sum of deltas M equals zero up to N minus one. I’m calling M, right? Just to be consistent here. Yeah. Delta S minus S K gives me what? Gives me these terms times these terms, so it gives me the sum over K and L going from – K and M going from zero up to N minus one. F of T K, that’s a constant. I get an exponential function, a complex exponential function times the delta function. We know what that does. That pulls out the value of the exponential at the point where the delta function is shifted and then times the corresponding delta function. So F of T K, either the minus 2 p I S M T K times delta S minus S K. Cool. Okay? Cool, cool, cool. Pardon me?
Student:[Inaudible].
Instructor (Brad Osgood):S, S M. Now it’s cool. Is it cool?
Student:[Inaudible].
Instructor (Brad Osgood):Are we cool? Okay. All right. So what are the sampled values of the Fourier transform? It is there before us, actually. All right. I wanna repeat again how we got to this point. We got to this point by misapplying the sampling theorem that has led to something that actually turns out to be reasonable and useful. And again, as is the tradition here, once you reach this point you sort of cover your tracks and just say, “All right. Now I’m gonna turn this into a definition.”
How do we get to this point? We said we wanted to choose sample points of F that we thought were gonna be reasonable – sample points of the function little F in the time domain that we thought were gonna be reasonable – provide a reasonable approximation of F. We take the Fourier transform of that. That gives us a signal. That gives us a continuous signal, function of a continuous variable in the frequency domain.
Then I wanna sample that, and you say to yourself, “How do I sample that?” Well, you sample that according to what the properties are in the other domain. That says I take sample values one over L apart, and I sample according to that criteria. And then the sample version of the Fourier transform of the sampled function is this. I’m gonna say that one more time to make sure I’ve said it right. The sample version of the Fourier transform of the sampled function looks like this.
So what are the sampled values of the Fourier transform of the sampled function are – let me call them – let me just use a different notation, [inaudible] call it capital F – are F of S zero, say that’s the sum from K equals zero to N minus one. If M is fixed at zero here, the first entry, the zeroth entry is F of T K E to the minus 2 p I S is not – S zero times T K. F of S1 is the sum from K equals zero up to N minus one of F of T K, E to the minus 2 p I S1 T K, and so on. I get N sample values of the Fourier transform, and so on down to F of S M minus one is the sum from K equals zero up to N minus one of F of T K, E to the minus 2 p I S N minus one T K. All right? That’s the discrete approximation to the Fourier transform of the discrete version of F – discrete approximation to the Fourier transformation of the discrete approximation of F. All right. I approximate F by taking N samples in the time domain. I approximate the Fourier transform N values in the frequency domain according to this rule, according to this formula. All right. Let me take stock here because we are actually – we are there almost. So again F – F of T is approximated by – or discretized by [inaudible] better here – F is discretized to F of T not F of T N minus one, and the Fourier transform of F of S is discretized to F of capital F S not F S N minus one where the formula relating capital F to little F to the sampled – to the values here, to the values here, are the formula that I just have. F of – capital F of S M is equal to the sum from K equals zero to N minus one of F of T K, E to the minus 2 p I S M T K.
Okay. Now there’s one more step in actually defining the Fourier transform as people usually think of the Fourier transform. This is still – a continuous side of things is still in sight. All right? We start off by looking at continuous functions and try to approximate it. You still see the continuous variables here. You still see the continuous picture. All right? And in fact, that’s most often where the Fourier transform comes up when you’re actually gonna apply it. There’s usually some continuous process working in the background that you are approximating discretely. That’s where it comes from. But the definition of the discrete Fourier transform as it’s usually given is purely in terms of discrete data and discrete signals. So the final step in defining the DFT is to sort of eliminate the continuous completely, and define – and everything is defined in terms of discrete signals and use only discrete signals, or digital signals, however you wanna call it, discrete signals. Now how do you do that?
Well, it’s not hard actually. According to our spacing, according to the way we set this up – so in our set up, T K – the Kth value is K over 2B, right? The points are spaced 2B apart, one over 2B apart in the time domain. The sample points in the time domain are spaced one over 2B apart. It’s zero, one over 2B, two over 2B, three over 2B, and so on and so on. Those are the sample points in the time domain. In the frequency domain, the sample points S M are M over L. All right? They’re spaced one over L apart, zero over L, one over L, two over L, and so on and so on. All right? T K times S M – if I use this how they are in relation to the spacing, then it’s K times M over 2B times L, but you remember 2 B times L in the way we did the set up is actually the number of sample points. 2 B L equals N, the number of the sample points. All right? So in the complex exponential – so what do I have in my complex exponential? If I still keep the shadow of the continuous variable, I have 2 p I S M T K, but then if I use this, I can write this as E to the minus 2 p I K M over 2 B L. That’s K M over N. All right? Only the discrete indices K and M now appear in that complex exponential. No more do you see on the right hand side where those points – where the K and the M so to speak came from. You just see the indices K and M. All right. They came from the Mth index of the continuous variable S, the Kth index of the continuous variable K, but there’s a relationship here. That is we sampled at a certain rate. T K was K over 2 B. S M was M over L. The product is K M over 2 B L and 2 B L is the total number of sample points you take in either domain. All right? So the product there is just minus 2 p I K M over N. That’s one – that’s sort of the first step in eliminating the continuous variable from the picture. The last step in eliminating the continuous picture from the variable is to identify the value of the function in this Fourier transform at the sample points with just the index that determines that value. So finally, you identify the values of F of T K with the value of a discrete signal with a value – say let me call it this: F K of a discrete signal. That is discrete signal F is F – I need a nonsum notation for this – F zero up to F N minus one. And I’m following the sort of common notation here of using brackets when you talk about discrete variable rather than parentheses when you talk about a continuous variable. Where these entries here are nothing but the values of the measured signal – of the continuous signal at the point T K. F K is equal to F of T K, so you have to be a little careful here. I’m trying to make a distinction somehow between the discrete signal indexed by K coming from the values of the continuous signal at the sample point T sub K, okay? And likewise, in the frequency domain, you replace in your mind or in the definition the continuous S K or S M by the index that determines it. So likewise, we replace S M by the index M, i.e. F by the discrete signal, capital F, underline – I’m trying to use that as an indication that I have a discrete signal – of this n-tuple F zero, capital F, N minus one where its value at the Kth index is before what I was calling F of S K. All right?
The right hand side made sense from what I had before. It’s the value of this approximate Fourier transform at the Kth sample point. But identify the Kth sample point just with this index, and I consider that to be defining a discrete signal, F0, F1, F2, F3, and so on and so on. Okay? And if I do that, then all traces of the continuous variable are gone, and I now have a transformation from one discrete signal to another discrete signal. If I do this, then all traces of a continuous variable are gone, and you have a transformation from one discrete signal to another discrete signal. That is to say if you start off with the signal little F, discrete signal, which I’m writing like that – if you think of it as an n-tuple, F0 up to F N minus one. All right? So just given by N discrete values, indexed here from zero to N minus one, then it’s discrete Fourier transform, the DFT of this discrete signal is the discrete signal capital F, which is again an n-tuple indexed from zero to N minus one the way I’ve indexed things.
And what is the definition? The definition is F of M is the sum from K equals zero up to N minus one of F of K. I’ll write that a little bit nicer. E to the minus 2 p I M K over N. Right? All traces of the continuous have disappeared, and some would consider this a great step forward. All right? Oftentimes, when you see treatments of the discrete Fourier transform, if you just look at a book that’s devoted to the discrete Fourier transform, or sometimes even if you look at other books on Fourier analysis and they talk about the discrete Fourier transform, they often jump right to this definition. All right? And that’s defensible. You can say the Fourier transform is for continuous function – is functions of continuous variables, and so on. The discrete Fourier transform is for functions of discrete variables. It’s for discrete signals. Here’s the definition of the continuous case. Here’s the definition in the discrete case. Don’t bother me. All right? It’s a definition. I get to do what I want. But what you often miss in that treatment – [inaudible] it’s a choice. And I chose to do it this way because I wanted to make the connection with the continuous case because I think actually that in applications, that’s how most often you see it. You wanna pass from the continuous to the discrete. You wanna pass from a continuous signal to a discrete approximation, and you still want the tools of Fourier analysis that you worked so hard to learn in the continuous case to be available to you in the discrete case.
So what you have to do most often in applying this is to say to yourself, “All right. That’s the definition. Fine.” That’s what the discrete Fourier transform looks like. I have a discrete signal, little F. I have its discrete Fourier transform, capital F. This is how they’re related. The indices of capital F, the values of capital F at the discrete points, 0, 1, 2, 3, and so on, are related to the values of little F, so on and – according to this formula, everything is discrete, but what it comes from is – you have to realize that these are coming from values of a continuous signal approximated at a discrete set of points. These are values of the approximation of the Fourier transformation, the continuous Fourier transform at a discrete set of points. Okay? That is the burden of my remarks. Okay, now what we’re gonna do is – like I say, I’m gonna try to make the discrete Fourier transform look as much as possible like the continuous Fourier transform. I’m gonna try write the – we’re gonna wrap up today. I’m gonna to write the formulas for the discrete Fourier transform in a way that look like the formulas for the continuous Fourier transform. I’m gonna write the theorems for the discrete Fourier transform to look as much as possible like the continuous Fourier transform. The inverse of the discrete Fourier transform to look like the inverse of the Fourier transform – there’s a catch there as it turns out. But by and large, you can do this quite – you can take this quite far. You can take the analogy quite far. Now again, that’s a choice. You can just study this object the way it is. You can apply it the way it is to the particular cases that come up. But I think again from my experience, you gain much more from trying to make a connection to the continuous case than you lose by – you gain much more by doing that than by just taking this as the accepted definition and working with it as it is. All right? So that’s gonna be our modus operandi. Now there are lots of little points along the way. There are lots of little observations of the similarities and the differences. I don’t want to talk about all of them because there are – it’s difficult to sort of see the whole picture at once, so I wanna try to do this at a level where you can see the whole argument go. So be sure to read through these sections carefully. Before you come to class, you should always do this naturally. Just so there’s some small points – I won’t always talk about this or always talk about that, but I wanna assume you’ll have some familiarity with how some of the calculations go. I’m gonna do a certain number of them so you can see how the techniques go, and so you can see how the formulas come about, but there are a number of sort of little points along the way that have to do with the discrete, and then the continuous, and so on that I don’t always wanna emphasize. So I’m asking you to sort of keep up with that as we go ahead and develop some of the properties of this. All right? So next time, we’re gonna start to unwind this a little bit, and see how it works, and see how it works analogous to the continuous case. Thank you.
[End of Audio]
Duration: 52 minutes