1 00:00:00,012 --> 00:00:03,091 Welcome to Module Six of Digital Signal Processing. 2 00:00:03,091 --> 00:00:07,858 This module is concerned with one of the central topics of signal processing which 3 00:00:07,858 --> 00:00:12,231 is sampling an interpolation. Sampling an interpolation are at the heart 4 00:00:12,231 --> 00:00:16,871 of interacting between the continuous time world and the discreet time world. 5 00:00:16,871 --> 00:00:21,637 And we are going to review all the basic concepts and prove a central theorem which 6 00:00:21,637 --> 00:00:25,766 is sampling. First, what I do think about interpolation 7 00:00:25,766 --> 00:00:31,058 now interpolation is about as old as computation itself and we can see an old 8 00:00:31,058 --> 00:00:34,201 analog device which is called a slide rule. 9 00:00:34,201 --> 00:00:39,667 We have the picture here of a slide rule that was used to compute trigonometric 10 00:00:39,667 --> 00:00:44,632 function and other functions that are not easy to calculate by hand. 11 00:00:44,633 --> 00:00:48,997 Now why is interpolation important? Because, if you make a table of a 12 00:00:48,997 --> 00:00:52,859 function, and here we see an example of a table of a function. 13 00:00:52,859 --> 00:00:57,815 You want to know how many values you have to actually tabulate so as to have a good 14 00:00:57,815 --> 00:01:01,682 approximation of the function. And that's the whole theory of 15 00:01:01,682 --> 00:01:05,325 interpolations. That we are going to review in detail for 16 00:01:05,325 --> 00:01:08,893 passing from a sequence to a continuous time function. 17 00:01:08,893 --> 00:01:11,626 Interpolation raises two interesting questions. 18 00:01:11,626 --> 00:01:16,188 The first one, if you have the values of a function at a number of points how should 19 00:01:16,188 --> 00:01:20,734 you interpolate between these 2 point. Should you linearly interpolate between 20 00:01:20,734 --> 00:01:23,715 two values? That's probably not good enough when the 21 00:01:23,715 --> 00:01:27,330 function is complex. The second interesting question is, is 22 00:01:27,330 --> 00:01:32,010 there a minimum set of values you need to measure the function at so that you can 23 00:01:32,010 --> 00:01:35,792 perfectly constructed. That result is known as a sampling 24 00:01:35,792 --> 00:01:38,877 theorem. It's a very simple and very powerful 25 00:01:38,877 --> 00:01:41,745 result. Namely if a function has a maximum 26 00:01:41,745 --> 00:01:46,646 frequency F0 then it is sufficient to sample the function that twice F0. 27 00:01:46,646 --> 00:01:52,177 From these samples it is possible to perfectly reconstruct, so it's a function. 28 00:01:52,177 --> 00:01:55,645 That's a cornerstone result of signal processing. 29 00:01:55,645 --> 00:02:01,063 It allows to go from the continuous time world to the discreet time world, and go 30 00:02:01,063 --> 00:02:04,823 back perfectly. Assume you have just two samples, then 31 00:02:04,823 --> 00:02:08,523 it's simple enough. There is a straight line that goes 32 00:02:08,523 --> 00:02:14,308 perfectly through these two samples. If you have three samples examples same 33 00:02:14,308 --> 00:02:17,797 story. You have a parabola so close to three 34 00:02:17,797 --> 00:02:21,715 samples. If you have many samples, you also can try 35 00:02:21,715 --> 00:02:27,327 it when interpolate, and of course you have samples which can see this is a 36 00:02:27,327 --> 00:02:32,306 trickier issue, some what we are down with two or three samples. 37 00:02:32,306 --> 00:02:37,872 If we have a function we can take, any samples. 38 00:02:37,872 --> 00:02:47,178 Let's take equally spaced samples. This will generate the sequence xn, which 39 00:02:47,178 --> 00:02:55,870 in this case is equal to x of n times T. T is the space thing between two samples. 40 00:02:55,870 --> 00:03:02,638 So, given a sequence, we have seen how to obtain continuous time function through a 41 00:03:02,638 --> 00:03:09,400 process called interpolation, so going from the sequence to, say continuous time 42 00:03:09,400 --> 00:03:14,966 function, with interpolation. We had also seen how to start with a 43 00:03:14,966 --> 00:03:21,508 continuous time function, and get samples through a process called sampling. 44 00:03:21,508 --> 00:03:28,178 The key question is, when is there a one to one relationship between sequences and 45 00:03:28,178 --> 00:03:33,358 continuous time functions. When can we go back and forth sampling and 46 00:03:33,358 --> 00:03:38,770 interpolation and these two are exact images of each other, and that's exactly 47 00:03:38,770 --> 00:03:43,751 the topic of the sampling theorem. We study the question of that one to one 48 00:03:43,751 --> 00:03:48,821 relationship between a band limited function and its samples in great detail 49 00:03:48,821 --> 00:03:52,522 in this module. And to arise at these results, where again 50 00:03:52,522 --> 00:03:56,539 you can use all the tools in the box, that we have developed so far. 51 00:03:56,539 --> 00:04:00,658 So Albert's space his projections filtering thing functions and so on. 52 00:04:00,658 --> 00:04:05,086 Ans so every thing comes together here to give [inaudible] his profile and very 53 00:04:05,086 --> 00:04:08,612 useful result. The big message of this module on sampling 54 00:04:08,612 --> 00:04:12,400 an interpolation can be summarized in the following points. 55 00:04:12,400 --> 00:04:15,943 Continuous time is the physical world so it is a reality. 56 00:04:15,943 --> 00:04:20,899 It is a bit trickier than the reality of sequences and discreet time that we have 57 00:04:20,899 --> 00:04:24,598 seen so far. The space of band limited functions can be 58 00:04:24,598 --> 00:04:29,495 very well said in a Albert's space framework it is a sub space of general 59 00:04:29,495 --> 00:04:34,359 functions namely one set have no frequencies beyond certain limit. 60 00:04:34,359 --> 00:04:39,997 So we can use Albert space geometry to define an atom of basis for the subspace 61 00:04:39,997 --> 00:04:44,510 of band limited functions. That [inaudible] basis is going to be 62 00:04:44,510 --> 00:04:49,190 given by the sync function, and it's shifts by integral multiples of the 63 00:04:49,190 --> 00:04:53,183 sampling interval. And to sample a general signal, one that 64 00:04:53,183 --> 00:04:57,135 is not band limited. What we do is that we first projected onto 65 00:04:57,135 --> 00:05:02,174 the subspace of band limited functions. We do this by low pass filtering, and then 66 00:05:02,174 --> 00:05:05,798 we can represent perfectly that function on this subspace. 67 00:05:05,798 --> 00:05:10,745 So we see that we need all the traits that we have seen so far, we put them together. 68 00:05:10,745 --> 00:05:15,022 And we are able to understand, in detail, sampling and interpolation. 69 00:05:15,023 --> 00:05:18,851 The space of band limited function is a subspace. 70 00:05:18,851 --> 00:05:24,497 So in our two, would be a line going to a zero region lets call it BL for band 71 00:05:24,497 --> 00:05:28,806 limited. If particular signal or a function is band 72 00:05:28,806 --> 00:05:35,270 limited, it will belong to this subspace. That leaves here on the subspace, and we 73 00:05:35,270 --> 00:05:41,963 are going to prove the sampling theorem, which has such a vector x can be written 74 00:05:41,963 --> 00:05:48,365 as a linear combination of n log to z of the weighting coefficients alpha n times 75 00:05:48,365 --> 00:05:54,241 pi n, where pi n are the basis functions for this band limited subspace. 76 00:05:54,241 --> 00:05:59,431 And we're going to see the pi n are, so string functions so that's a 77 00:05:59,431 --> 00:06:03,706 representation theorem for band limited function. 78 00:06:03,706 --> 00:06:10,172 Now if we have the general vector that is not band limited then we can not represent 79 00:06:10,172 --> 00:06:16,537 it using a linear combination of string functions so we have the first project it 80 00:06:16,537 --> 00:06:21,720 down to band limited function. So we use a projection theorem, we find 81 00:06:21,720 --> 00:06:26,052 its projection x hat. And x hat now can be represented as linear 82 00:06:26,052 --> 00:06:31,039 combination of sinc function. So a general function can always be band 83 00:06:31,039 --> 00:06:36,224 limited by e projected to the subspace of band limited functions and then 84 00:06:36,224 --> 00:06:40,792 represented perfect. Before moving to the heart of the topic 85 00:06:40,792 --> 00:06:46,527 let us briefly review its history. The Shannon Sampling Theorem, has a very 86 00:06:46,527 --> 00:06:50,947 interesting history which goes back well before Shannon. 87 00:06:50,947 --> 00:06:56,713 So numerical analysis people were concerned about interpolating tables of 88 00:06:56,713 --> 00:07:02,383 functions and the first one to prove the version of the sampling theorem was 89 00:07:02,383 --> 00:07:07,468 Whittaker in England in 1915. Harry Nyquist of Bell Labs came up with 90 00:07:07,468 --> 00:07:12,176 the Nyquist criterion. Namely, that the function that had the 91 00:07:12,176 --> 00:07:16,367 maximum frequency, F0 could be sampled at 2 times F0. 92 00:07:16,367 --> 00:07:20,776 In the Soviet Union, Kotelnikov proved the sampling theorem. 93 00:07:20,776 --> 00:07:24,403 The son of the first Whittaker, another Whittaker. 94 00:07:24,403 --> 00:07:28,193 Further proved results on the sampling theorem. 95 00:07:28,193 --> 00:07:34,639 Then Herbert Raabe in Berlin in 1938 wrote his PhD thesis about the sampling theorem 96 00:07:34,639 --> 00:07:38,575 but wrong time, wrong city. He got 0 credit for it. 97 00:07:38,575 --> 00:07:44,431 Dennis Gabor worked on the version of the sampling theorem in the mid 1940s. 98 00:07:44,431 --> 00:07:50,217 Then Claude Shannon inventor of information theory wrote, beautiful papers 99 00:07:50,217 --> 00:07:53,553 that is in the further reading for this class. 100 00:07:53,553 --> 00:07:58,280 Where the Shannon sampling theorem really appears in the forms that we use today. 101 00:07:58,280 --> 00:08:02,801 Last but no least, in 1949, Someya in Japan also proved the sampling theorem. 102 00:08:02,801 --> 00:08:06,557 You can see that's a very valid history, it's a very fundamental result. 103 00:08:06,557 --> 00:08:13,700 So many different people independently, actually came up with this result.