1 00:00:00,040 --> 00:00:02,470 The following content is provided under a Creative 2 00:00:02,470 --> 00:00:03,880 Commons license. 3 00:00:03,880 --> 00:00:06,920 Your support will help MIT OpenCourseWare continue to 4 00:00:06,920 --> 00:00:10,570 offer high quality educational resources for free. 5 00:00:10,570 --> 00:00:13,460 To make a donation or view additional materials from 6 00:00:13,460 --> 00:00:19,290 hundreds of MIT courses, visit MIT OpenCourseWare at 7 00:00:19,290 --> 00:00:20,540 ocw.mit.edu. 8 00:00:55,450 --> 00:00:57,940 PROFESSOR: In the last lecture, we discussed discrete 9 00:00:57,940 --> 00:01:00,760 time processing of continuous time signals. 10 00:01:00,760 --> 00:01:04,069 And, as you know, the basis for that arises essentially 11 00:01:04,069 --> 00:01:06,150 out of a sampling theorem. 12 00:01:06,150 --> 00:01:10,240 Now in that context, and also in its own right, another 13 00:01:10,240 --> 00:01:14,850 important sampling issue is the sampling of discrete time 14 00:01:14,850 --> 00:01:18,640 signals, in other words, the sampling of a sequence. 15 00:01:18,640 --> 00:01:23,000 One common context in which this arises, for example, is, 16 00:01:23,000 --> 00:01:26,690 if we've converted from a continuous time signal to a 17 00:01:26,690 --> 00:01:32,150 sequence, and we then carry out some additional filtering, 18 00:01:32,150 --> 00:01:35,260 then there's the possibility that we can resample that 19 00:01:35,260 --> 00:01:38,460 sequence, and as we'll see as we go through the discussion, 20 00:01:38,460 --> 00:01:42,300 save something in the way of storage or whatever. 21 00:01:42,300 --> 00:01:47,800 So discrete time sampling, as I indicated, has important 22 00:01:47,800 --> 00:01:51,930 application in a context referred to here, namely 23 00:01:51,930 --> 00:01:55,830 resampling after discrete time filtering. 24 00:01:55,830 --> 00:01:59,370 And closely related to that, as we'll indicate in this 25 00:01:59,370 --> 00:02:04,270 lecture, is the concept of using discrete time sampling 26 00:02:04,270 --> 00:02:08,740 for what's referred to as sampling rate conversion. 27 00:02:08,740 --> 00:02:15,220 And also closely associated with both of those ideas is a 28 00:02:15,220 --> 00:02:18,120 set of ideas that I'll bring up in today's lecture, 29 00:02:18,120 --> 00:02:22,980 referred to as decimation and interpolation of discrete time 30 00:02:22,980 --> 00:02:25,420 signals or sequences. 31 00:02:25,420 --> 00:02:30,550 Now the basic process for discrete time sampling is the 32 00:02:30,550 --> 00:02:33,720 same as it is for continuous time sampling. 33 00:02:33,720 --> 00:02:38,880 Namely, we can analyze it and set it up on the basis of 34 00:02:38,880 --> 00:02:43,330 multiplying or modulating a discrete time signal by an 35 00:02:43,330 --> 00:02:47,430 impulse train, the impulse train essentially, or pulse 36 00:02:47,430 --> 00:02:51,140 train, pulling out sequence values at the times that we 37 00:02:51,140 --> 00:02:52,950 want to sample. 38 00:02:52,950 --> 00:02:58,400 So the basic block diagram for the sampling process is to 39 00:02:58,400 --> 00:03:01,430 modulate or multiply the sequence that we want to 40 00:03:01,430 --> 00:03:05,520 sample by an impulse train. 41 00:03:05,520 --> 00:03:11,380 And here, the impulse train has impulses spaced by integer 42 00:03:11,380 --> 00:03:14,160 multiples of capital N. This then becomes 43 00:03:14,160 --> 00:03:16,170 the sampling period. 44 00:03:16,170 --> 00:03:20,010 And the result of that modulation is then the sample 45 00:03:20,010 --> 00:03:23,230 sequence x of p of n. 46 00:03:23,230 --> 00:03:28,250 So if we just look at what a sequence and a sampled version 47 00:03:28,250 --> 00:03:33,750 of that sequence might look like, what we have here is an 48 00:03:33,750 --> 00:03:36,220 original sequence x of n. 49 00:03:36,220 --> 00:03:41,790 And then we have the sampling impulse train, or sampling 50 00:03:41,790 --> 00:03:46,120 sequence, and it's the modulation or product of these 51 00:03:46,120 --> 00:03:50,840 two that gives us the sample sequence x of p of n. 52 00:03:50,840 --> 00:03:55,090 And so, as you can see, multiplying this by this 53 00:03:55,090 --> 00:03:59,640 essentially pulls out of the original sequence sample 54 00:03:59,640 --> 00:04:02,740 values at the times that this pulse train is on. 55 00:04:02,740 --> 00:04:06,330 And of course here, I've drawn this for the case where 56 00:04:06,330 --> 00:04:12,570 capital N, the sampling period, is equal to 3. 57 00:04:12,570 --> 00:04:18,540 Now the analysis of discrete time sampling is very similar 58 00:04:18,540 --> 00:04:21,579 to the analysis of continuous time sampling. 59 00:04:21,579 --> 00:04:24,100 And let's just quickly look through the 60 00:04:24,100 --> 00:04:26,990 steps that are involved. 61 00:04:26,990 --> 00:04:28,380 We're modulating or 62 00:04:28,380 --> 00:04:30,430 multiplying in the time domain. 63 00:04:30,430 --> 00:04:33,870 And what that corresponds to in the frequency domain is a 64 00:04:33,870 --> 00:04:35,330 convolution. 65 00:04:35,330 --> 00:04:43,020 And so the spectrum of the sampled sequence is the 66 00:04:43,020 --> 00:04:47,710 periodic convolution of the spectrum of the sampling 67 00:04:47,710 --> 00:04:51,700 sequence and the spectrum of the 68 00:04:51,700 --> 00:04:54,210 sequence that we're sampling. 69 00:04:54,210 --> 00:04:59,680 And since the sampling sequence is an impulse train, 70 00:04:59,680 --> 00:05:03,500 as we know, the Fourier transform of an impulse train 71 00:05:03,500 --> 00:05:05,560 is itself an impulse train. 72 00:05:05,560 --> 00:05:09,500 And so this is the Fourier transform of 73 00:05:09,500 --> 00:05:11,990 the sampling sequence. 74 00:05:11,990 --> 00:05:17,340 And now, finally, the Fourier transform of the resulting 75 00:05:17,340 --> 00:05:23,080 sample sequence, being the convolution of this with the 76 00:05:23,080 --> 00:05:26,300 Fourier transform of the sequence that we're sampling, 77 00:05:26,300 --> 00:05:32,090 gives us then a spectrum which consists of a sum of 78 00:05:32,090 --> 00:05:35,370 replicated versions of the Fourier transform of the 79 00:05:35,370 --> 00:05:37,970 sequence that we're sampling. 80 00:05:37,970 --> 00:05:40,940 In other words, what we're doing, very much as we did in 81 00:05:40,940 --> 00:05:44,790 continuous time, is, through the sampling process when we 82 00:05:44,790 --> 00:05:49,460 look at it in the frequency domain, taking the spectrum of 83 00:05:49,460 --> 00:05:53,190 the sequence there were sampling and shifting it and 84 00:05:53,190 --> 00:05:54,540 then adding it in-- 85 00:05:54,540 --> 00:05:57,470 shifting it by integer multiples of 86 00:05:57,470 --> 00:05:58,900 the sampling frequency. 87 00:05:58,900 --> 00:06:02,620 In particular, looking back at this equation, what we 88 00:06:02,620 --> 00:06:09,120 recognize is that this term, k times 2 pi over capital N, is 89 00:06:09,120 --> 00:06:14,460 in fact an integer multiple of the sampling frequency. 90 00:06:14,460 --> 00:06:17,260 And the same thing is true here. 91 00:06:17,260 --> 00:06:23,080 This is k times omega sub s, where omega sub s, the 92 00:06:23,080 --> 00:06:30,580 sampling frequency, is 2 pi divided by capital N. 93 00:06:30,580 --> 00:06:34,720 All right, so now let's look at what this means pictorially 94 00:06:34,720 --> 00:06:37,520 or graphically in the frequency domain. 95 00:06:37,520 --> 00:06:42,110 And as you can imagine, since the analysis and algebra is 96 00:06:42,110 --> 00:06:45,740 similar to what happens in continuous time, we would 97 00:06:45,740 --> 00:06:49,410 expect the pictures to more or less be identical to what 98 00:06:49,410 --> 00:06:51,570 we've seen previously for continuous time. 99 00:06:51,570 --> 00:06:53,660 And indeed that's the case. 100 00:06:53,660 --> 00:06:58,890 So here we have the spectrum of the signal 101 00:06:58,890 --> 00:07:00,460 that's we're sampling. 102 00:07:00,460 --> 00:07:04,160 This is its Fourier transform, with an assumed highest 103 00:07:04,160 --> 00:07:08,700 frequency omega sub m, highest frequency over a 2pi range, or 104 00:07:08,700 --> 00:07:10,810 over a range of pi, rather. 105 00:07:10,810 --> 00:07:18,520 And now the spectrum of the sampling signal is what I show 106 00:07:18,520 --> 00:07:22,680 below, which is an impulse train with impulses occurring 107 00:07:22,680 --> 00:07:27,260 at integer multiples of the sampling frequency. 108 00:07:27,260 --> 00:07:31,930 And then finally, the convolution of these two is 109 00:07:31,930 --> 00:07:35,760 simply this one replicated at the 110 00:07:35,760 --> 00:07:37,910 locations of these impulses. 111 00:07:37,910 --> 00:07:41,610 And so that's finally what I show below. 112 00:07:41,610 --> 00:07:46,770 And here I made one particular choice for 113 00:07:46,770 --> 00:07:48,460 the sampling period. 114 00:07:48,460 --> 00:07:54,760 This in particular corresponds to a sampling period which is 115 00:07:54,760 --> 00:08:00,570 capital N equal to 3. 116 00:08:00,570 --> 00:08:04,520 And so the sampling frequency, omega sub s, is 117 00:08:04,520 --> 00:08:07,210 2pi divided by 3. 118 00:08:09,740 --> 00:08:16,060 Now when we look at this, what we recognize is that we have 119 00:08:16,060 --> 00:08:20,060 basically the same issue here as we had in continuous time, 120 00:08:20,060 --> 00:08:25,730 in the sense that when these individual replications of the 121 00:08:25,730 --> 00:08:30,600 Fourier transform, when the sampling frequency is chosen 122 00:08:30,600 --> 00:08:34,370 high enough so that they don't overlap, then we see the 123 00:08:34,370 --> 00:08:37,539 potential for being able to get one of them back. 124 00:08:37,539 --> 00:08:40,659 On the other hand, when they do overlap then what we'll 125 00:08:40,659 --> 00:08:43,309 have is aliasing, in particular, discrete time 126 00:08:43,309 --> 00:08:46,460 aliasing, much as we had continuous time aliasing in 127 00:08:46,460 --> 00:08:48,030 the continuous time case. 128 00:08:48,030 --> 00:08:53,330 Well notice in this picture that what we have is we've 129 00:08:53,330 --> 00:08:59,370 chosen this picture so that omega sub s minus omega sub m 130 00:08:59,370 --> 00:09:04,360 is greater than omega sub m, or equivalently, so that omega 131 00:09:04,360 --> 00:09:11,890 sub s is greater than 2 omega sub m. 132 00:09:11,890 --> 00:09:15,240 And so with omega sub s greater than 2 omega sum m, 133 00:09:15,240 --> 00:09:17,600 that corresponds to this picture. 134 00:09:17,600 --> 00:09:23,330 Whereas, if that condition is violated then, in fact, the 135 00:09:23,330 --> 00:09:27,160 picture that we would have is a picture that looks like. 136 00:09:27,160 --> 00:09:32,030 And in this picture, the individual replications of the 137 00:09:32,030 --> 00:09:36,700 Fourier transform of the original signal overlap. 138 00:09:36,700 --> 00:09:41,770 And we can no longer recover the Fourier transform of the 139 00:09:41,770 --> 00:09:43,000 original signal. 140 00:09:43,000 --> 00:09:47,390 And this, just as it was in continuous time, is referred 141 00:09:47,390 --> 00:09:50,860 to as aliasing. 142 00:09:50,860 --> 00:09:54,870 Now let's look more closely at the situation in which there 143 00:09:54,870 --> 00:09:56,120 is no aliasing. 144 00:09:58,680 --> 00:10:07,280 So in that case, what we have is a Fourier transform for the 145 00:10:07,280 --> 00:10:13,980 sampled signal, which is as I indicated here, and the 146 00:10:13,980 --> 00:10:17,380 Fourier transform for the original signal, as I indicate 147 00:10:17,380 --> 00:10:18,710 at the top. 148 00:10:18,710 --> 00:10:22,190 And the question now is how do we recover this 149 00:10:22,190 --> 00:10:23,590 one from this one. 150 00:10:23,590 --> 00:10:27,340 Well, the way that we do that, just as we did in a continuous 151 00:10:27,340 --> 00:10:31,010 time case, is by a low pass filtering. 152 00:10:31,010 --> 00:10:34,520 In particular, processing in the time domain or in the 153 00:10:34,520 --> 00:10:40,590 frequency domain, this with an ideal low pass filter has the 154 00:10:40,590 --> 00:10:46,080 effect of extracting that part of the spectrum that in fact 155 00:10:46,080 --> 00:10:53,400 we identify with the original signal that we began with. 156 00:10:53,400 --> 00:10:57,470 So what we see, again, is that the process is 157 00:10:57,470 --> 00:10:58,460 very much the same. 158 00:10:58,460 --> 00:11:01,170 As long as there's no aliasing, we can recover the 159 00:11:01,170 --> 00:11:06,150 original signal by ideal low pass filtering. 160 00:11:06,150 --> 00:11:13,290 So the overall system is, just to reiterate, a system which 161 00:11:13,290 --> 00:11:20,400 consists of modulating the original sequence with a pulse 162 00:11:20,400 --> 00:11:22,960 train or impulse train. 163 00:11:22,960 --> 00:11:27,160 And then that is going to be processed 164 00:11:27,160 --> 00:11:30,370 with a low pass filter. 165 00:11:30,370 --> 00:11:34,140 The spectrum of the original signal x of n 166 00:11:34,140 --> 00:11:36,770 is what I show here. 167 00:11:36,770 --> 00:11:40,020 The spectrum of the sampled signal, where I'm drawing the 168 00:11:40,020 --> 00:11:43,830 picture on the assumption that the sampling period is 3, is 169 00:11:43,830 --> 00:11:47,470 now what's indicated, where these are replicated, where 170 00:11:47,470 --> 00:11:50,320 the original spectrum is replicated. 171 00:11:50,320 --> 00:11:56,740 This is now processed through a filter which, for exact 172 00:11:56,740 --> 00:12:01,220 reconstruction, is an ideal low pass filter. 173 00:12:01,220 --> 00:12:04,820 And so we would multiply this spectrum by this one. 174 00:12:04,820 --> 00:12:08,980 And the result, after doing that, will generate a 175 00:12:08,980 --> 00:12:11,890 reconstructed spectrum which, in fact, is 176 00:12:11,890 --> 00:12:14,300 identical to the original. 177 00:12:14,300 --> 00:12:21,450 So the frequency domain picture is the same. 178 00:12:21,450 --> 00:12:24,740 And what we would expect then is that the time domain 179 00:12:24,740 --> 00:12:26,110 picture would be the same. 180 00:12:26,110 --> 00:12:29,380 Well, let's in fact look at the time domain. 181 00:12:29,380 --> 00:12:34,780 And in the time domain, what we have is an analysis more or 182 00:12:34,780 --> 00:12:38,340 less identical to what we had in continuous time. 183 00:12:38,340 --> 00:12:41,360 We of course have the same system. 184 00:12:41,360 --> 00:12:45,260 And in the time domain, we are multiplying 185 00:12:45,260 --> 00:12:47,550 by an impulse train. 186 00:12:47,550 --> 00:12:54,340 Consequently, the sample sequence is an impulse train 187 00:12:54,340 --> 00:12:58,820 whose values are samples of x of at integer multiples of 188 00:12:58,820 --> 00:13:05,310 capital N. For the reconstruction, this is now 189 00:13:05,310 --> 00:13:10,220 processed through an ideal low pass filter. 190 00:13:10,220 --> 00:13:11,610 And that implements a 191 00:13:11,610 --> 00:13:13,900 convolution in the time domain. 192 00:13:13,900 --> 00:13:17,700 And so the reconstructed signal is the convolution of 193 00:13:17,700 --> 00:13:22,720 the sample sequence and the filter impulse response. 194 00:13:22,720 --> 00:13:26,010 And expressed another way, namely writing out the 195 00:13:26,010 --> 00:13:29,250 convolution as a sum, we have this expression. 196 00:13:29,250 --> 00:13:34,010 And so it says then that the reconstruction is carried out 197 00:13:34,010 --> 00:13:41,430 by replacing the impulses here, these impulses, by 198 00:13:41,430 --> 00:13:44,460 versions of the filter impulse response. 199 00:13:47,300 --> 00:13:53,360 Well, if the filter is an ideal low pass filter, then 200 00:13:53,360 --> 00:13:58,020 that corresponds in the time domain to sine nx over sine x 201 00:13:58,020 --> 00:13:58,840 kind of function. 202 00:13:58,840 --> 00:14:03,570 And that is the interpolation in between the samples to do 203 00:14:03,570 --> 00:14:05,800 the reconstruction. 204 00:14:05,800 --> 00:14:10,870 Also, as is discussed somewhat in the text, we can consider 205 00:14:10,870 --> 00:14:14,680 other kinds of interpolation, for example discrete time zero 206 00:14:14,680 --> 00:14:18,640 order hold or discrete time first order hold, just as we 207 00:14:18,640 --> 00:14:20,420 had in continuous time. 208 00:14:20,420 --> 00:14:23,530 And the issues and analysis for the discrete times zero 209 00:14:23,530 --> 00:14:28,170 order hold and first order hold are very similar to what 210 00:14:28,170 --> 00:14:30,950 they were in continuous time-- the zero order hold just 211 00:14:30,950 --> 00:14:34,340 simply holding the value until the next sampling instant, and 212 00:14:34,340 --> 00:14:38,160 the first order hold carrying out linear interpolation in 213 00:14:38,160 --> 00:14:39,410 between the samples. 214 00:14:42,400 --> 00:14:49,610 Now in this sampling process, if we look again at the wave 215 00:14:49,610 --> 00:14:53,910 forms involved, or sequences involved, the process 216 00:14:53,910 --> 00:15:01,090 consisted of taking a sequence and extracting from it 217 00:15:01,090 --> 00:15:03,980 individual values. 218 00:15:03,980 --> 00:15:08,560 And in between those values, we have sequence 219 00:15:08,560 --> 00:15:10,930 values equal to 0. 220 00:15:10,930 --> 00:15:18,030 So what we're doing in this case is retaining the same 221 00:15:18,030 --> 00:15:21,950 number of sequence values and simply setting some number of 222 00:15:21,950 --> 00:15:24,980 them equal to 0. 223 00:15:24,980 --> 00:15:28,380 Well, let's say, for example, that we want 224 00:15:28,380 --> 00:15:29,930 to carry out sampling. 225 00:15:29,930 --> 00:15:32,200 And what we're talking about is a sequence. 226 00:15:32,200 --> 00:15:36,170 And let's say this sequence is stored in a computer memory. 227 00:15:36,170 --> 00:15:40,150 As you can imagine, the notion of sampling it and actually 228 00:15:40,150 --> 00:15:44,250 replacing some of the values by zero is somewhat 229 00:15:44,250 --> 00:15:44,790 inefficient. 230 00:15:44,790 --> 00:15:47,550 Namely, it doesn't make sense to think of storing in the 231 00:15:47,550 --> 00:15:50,900 memory a lot of zeros, when in fact those are zeros that we 232 00:15:50,900 --> 00:15:52,460 can always put back in. 233 00:15:52,460 --> 00:15:54,670 We know exactly what the values are. 234 00:15:54,670 --> 00:15:57,920 And if we know what the sampling rate was in discrete 235 00:15:57,920 --> 00:16:00,760 time, then we would know when and how to put 236 00:16:00,760 --> 00:16:03,070 the zeros back in. 237 00:16:03,070 --> 00:16:07,700 So actually, in discrete time sampling, what we've talked 238 00:16:07,700 --> 00:16:10,710 about so far is really only one part or 239 00:16:10,710 --> 00:16:12,610 one step in the process. 240 00:16:12,610 --> 00:16:16,190 Basically, the other step is to take those zeros and just 241 00:16:16,190 --> 00:16:18,820 throw them away because we could put them in any time we 242 00:16:18,820 --> 00:16:22,790 want to and really only retain, for example in our 243 00:16:22,790 --> 00:16:26,800 computer memory or list of sequence values or whatever, 244 00:16:26,800 --> 00:16:30,830 only retain the non-zero values. 245 00:16:30,830 --> 00:16:34,540 So that process and the resulting sequence that we end 246 00:16:34,540 --> 00:16:39,020 up with is associated with a concept called decimation. 247 00:16:39,020 --> 00:16:42,050 What I mean by decimation is very simple. 248 00:16:42,050 --> 00:16:47,200 What we're doing is, instead of working with this sequence, 249 00:16:47,200 --> 00:16:50,190 we're going to work with this sequence. 250 00:16:50,190 --> 00:16:55,440 Namely, we'll toss out the zeros in between here and 251 00:16:55,440 --> 00:17:00,270 collapse the sequence down only to the sequence values 252 00:17:00,270 --> 00:17:03,860 that are associated with the original x of n. 253 00:17:03,860 --> 00:17:07,839 Now, in talking about a decimated sequence, we could 254 00:17:07,839 --> 00:17:12,450 of course do that directly from this step down to here, 255 00:17:12,450 --> 00:17:15,890 although again in the analysis it will be somewhat more 256 00:17:15,890 --> 00:17:20,650 convenient to carry that out by thinking, at least 257 00:17:20,650 --> 00:17:23,839 analytically, in terms of a 2-step process-- 258 00:17:23,839 --> 00:17:27,079 one being a sampling process, then the other being a 259 00:17:27,079 --> 00:17:28,079 decimation. 260 00:17:28,079 --> 00:17:32,930 But basically, this is a decimated version of that. 261 00:17:32,930 --> 00:17:38,040 Now for the grammatical purists out there, the word 262 00:17:38,040 --> 00:17:40,620 decimation of course means taking every tenth one. 263 00:17:40,620 --> 00:17:43,910 The implication is not that we're always sampling with a 264 00:17:43,910 --> 00:17:45,220 period of 10. 265 00:17:45,220 --> 00:17:49,650 The idea of decimating is to pick out every nth sample and 266 00:17:49,650 --> 00:17:53,390 end up with a collapsed sequence. 267 00:17:53,390 --> 00:17:59,410 Let's now look at a little bit of the analysis and understand 268 00:17:59,410 --> 00:18:02,870 what the consequence is in the frequency domain. 269 00:18:02,870 --> 00:18:07,690 In particular what we want to develop is how the Fourier 270 00:18:07,690 --> 00:18:12,000 transform of the decimated sequence is related to the 271 00:18:12,000 --> 00:18:15,060 Fourier transform of the original sequence or the 272 00:18:15,060 --> 00:18:16,540 sample sequence. 273 00:18:16,540 --> 00:18:19,125 So let's look at this in the frequency domain. 274 00:18:21,730 --> 00:18:28,040 So what we have is a decimated sequence, which consists of 275 00:18:28,040 --> 00:18:32,250 pulling out every capital Nth value of x of n. 276 00:18:32,250 --> 00:18:36,080 And of course that's the same as we can either decimate x of 277 00:18:36,080 --> 00:18:40,710 n or we can decimate the sample signal. 278 00:18:40,710 --> 00:18:45,960 Now in going through this analysis, I'll kind of go 279 00:18:45,960 --> 00:18:49,520 through it quickly because again there's the issue of 280 00:18:49,520 --> 00:18:51,170 some slight mental gymnastics. 281 00:18:51,170 --> 00:18:55,400 And if you're anything like I am, it's usually best to kind 282 00:18:55,400 --> 00:18:58,390 of try to absorb that by yourself quietly, rather than 283 00:18:58,390 --> 00:19:00,410 having somebody throw it at you. 284 00:19:00,410 --> 00:19:03,640 Let me say, though, that the steps that I'm following here 285 00:19:03,640 --> 00:19:06,090 are slightly different than the steps that 286 00:19:06,090 --> 00:19:07,120 I use in the text. 287 00:19:07,120 --> 00:19:11,250 It's a slightly different way of going through the analysis. 288 00:19:11,250 --> 00:19:13,790 I guess you could say for one thing that if we've gone 289 00:19:13,790 --> 00:19:16,560 through it twice, and it comes out the same, well of course 290 00:19:16,560 --> 00:19:18,930 it has to be right. 291 00:19:18,930 --> 00:19:24,760 Well anyway, here we have then the relationship between the 292 00:19:24,760 --> 00:19:29,320 decimated sequence, the original sequence, and the 293 00:19:29,320 --> 00:19:30,990 sampled sequence. 294 00:19:30,990 --> 00:19:34,260 And we know of course that the Fourier transform of the 295 00:19:34,260 --> 00:19:38,560 sample sequence is just simply this summation. 296 00:19:38,560 --> 00:19:43,320 And now kind of the idea in the analysis is that we can 297 00:19:43,320 --> 00:19:51,020 collapse this summation by recognizing that this term is 298 00:19:51,020 --> 00:19:55,420 only non-zero at every nth value. 299 00:19:55,420 --> 00:19:58,200 And so if we do that, essentially making a 300 00:19:58,200 --> 00:20:02,260 substitution of variables with n equal to small m times 301 00:20:02,260 --> 00:20:06,260 capital N, we can turn this into a summation on m. 302 00:20:06,260 --> 00:20:09,160 And that's what I've done here. 303 00:20:09,160 --> 00:20:13,170 And we've just simply used the fact that we can collapse the 304 00:20:13,170 --> 00:20:18,340 sum because of the fact that all but every nth value is 305 00:20:18,340 --> 00:20:20,080 equal to zero. 306 00:20:20,080 --> 00:20:23,110 So this then is the Fourier transform all 307 00:20:23,110 --> 00:20:25,590 of the sampled signal. 308 00:20:25,590 --> 00:20:29,920 And now if we look at the Fourier transform of the 309 00:20:29,920 --> 00:20:34,800 decimated signal, that Fourier transform, of course, is this 310 00:20:34,800 --> 00:20:38,680 summation on the decimated sequence. 311 00:20:38,680 --> 00:20:41,480 Well, what we want to look at is the correspondence between 312 00:20:41,480 --> 00:20:43,790 this equation and the one above it. 313 00:20:43,790 --> 00:20:47,780 So we want to compare this equation to this one. 314 00:20:47,780 --> 00:20:51,460 And recognizing that this decimated sequence is just 315 00:20:51,460 --> 00:20:59,070 simply related to the sample sequence this way, these two 316 00:20:59,070 --> 00:21:02,960 become equal under a substitution of variables. 317 00:21:02,960 --> 00:21:09,090 In particular, notice that if we replace in this equation 318 00:21:09,090 --> 00:21:14,650 omega by omega times capital N, then these two equations 319 00:21:14,650 --> 00:21:16,740 become equal. 320 00:21:16,740 --> 00:21:20,180 So the consequence of that, then, what it all boils down 321 00:21:20,180 --> 00:21:27,625 to and says, is that the relationship between the 322 00:21:27,625 --> 00:21:30,360 Fourier transform of the decimated sequence and the 323 00:21:30,360 --> 00:21:34,680 Fourier transform of the sampled sequence is simply a 324 00:21:34,680 --> 00:21:38,540 frequency scaling corresponding to dividing the 325 00:21:38,540 --> 00:21:41,350 frequency axis by capital N. 326 00:21:41,350 --> 00:21:44,040 So that's essentially what happens. 327 00:21:44,040 --> 00:21:45,680 That's really all that's involved in 328 00:21:45,680 --> 00:21:47,420 the decimation process. 329 00:21:47,420 --> 00:21:50,180 And now, again, let's look at that pictorially 330 00:21:50,180 --> 00:21:52,550 and see what it means. 331 00:21:52,550 --> 00:21:55,780 So what we want to look at, now that we've looked in the 332 00:21:55,780 --> 00:22:00,540 time domain in this particular view graph, we now want to 333 00:22:00,540 --> 00:22:04,470 look in the frequency domain. 334 00:22:04,470 --> 00:22:11,620 And in the frequency domain, we have, again, the Fourier 335 00:22:11,620 --> 00:22:17,470 transform of the original sequence and we have the 336 00:22:17,470 --> 00:22:23,350 Fourier transform of the sampled sequence. 337 00:22:23,350 --> 00:22:28,490 And now the Fourier transform of the decimated sequence is 338 00:22:28,490 --> 00:22:35,030 simply this spectrum with a linear frequency scaling. 339 00:22:35,030 --> 00:22:38,450 And in particular, it simply corresponds to multiplying 340 00:22:38,450 --> 00:22:44,150 this frequency axis by capital N. And notice that this 341 00:22:44,150 --> 00:22:48,840 frequency now, 2 pi over capital N, that frequency ends 342 00:22:48,840 --> 00:22:55,800 up getting rescaled to a frequency of 2 pi. 343 00:22:55,800 --> 00:23:00,980 So in fact now, in the rescaling, it's that this 344 00:23:00,980 --> 00:23:07,200 point in the decimation gets rescaled to this point. 345 00:23:07,200 --> 00:23:10,480 And correspondingly, of course, this whole spectrum 346 00:23:10,480 --> 00:23:11,650 broadens out. 347 00:23:11,650 --> 00:23:14,770 Now we can also look at that in the context of 348 00:23:14,770 --> 00:23:16,010 the original spectrum. 349 00:23:16,010 --> 00:23:19,130 And you can see that the relationship between the 350 00:23:19,130 --> 00:23:22,020 original spectrum and the spectrum of the decimated 351 00:23:22,020 --> 00:23:27,730 signal corresponds to simply linearly scaling this. 352 00:23:27,730 --> 00:23:32,740 But it's important also to keep in mind that that 353 00:23:32,740 --> 00:23:37,330 analysis, that particular relationship, assumes that 354 00:23:37,330 --> 00:23:38,850 we've avoided aliasing. 355 00:23:38,850 --> 00:23:41,870 The relationship between the spectrum of the decimated 356 00:23:41,870 --> 00:23:46,050 signal and the spectrum of the sample signal is true whether 357 00:23:46,050 --> 00:23:47,700 or not we have aliasing. 358 00:23:47,700 --> 00:23:51,820 But being able to clearly associate it with just simply 359 00:23:51,820 --> 00:23:56,480 scaling of this spectrum of the original signal assumes 360 00:23:56,480 --> 00:24:00,380 that the spectrum of the original signal, the shape of 361 00:24:00,380 --> 00:24:03,950 it, is preserved when we generate the sample signal. 362 00:24:06,940 --> 00:24:11,870 Well, when might discrete time sampling, and for that matter, 363 00:24:11,870 --> 00:24:14,080 decimation, be used? 364 00:24:14,080 --> 00:24:18,450 Well, I indicated one context in which it might be useful at 365 00:24:18,450 --> 00:24:19,710 the beginning of this lecture. 366 00:24:19,710 --> 00:24:22,320 And let me now focus in on that a little more 367 00:24:22,320 --> 00:24:23,570 specifically. 368 00:24:25,730 --> 00:24:33,450 In particular, suppose that we have gone through a process in 369 00:24:33,450 --> 00:24:39,730 which the continuous time signal has been converted to a 370 00:24:39,730 --> 00:24:41,810 discrete time signal. 371 00:24:41,810 --> 00:24:44,200 And we then carry out some additional 372 00:24:44,200 --> 00:24:45,690 discrete time filtering. 373 00:24:45,690 --> 00:24:49,060 So we have a situation where we've gone through a 374 00:24:49,060 --> 00:24:52,710 continuous to discrete time conversion. 375 00:24:52,710 --> 00:24:56,470 And after that conversion, we carry out some 376 00:24:56,470 --> 00:24:58,035 discrete time filtering. 377 00:25:01,380 --> 00:25:03,940 And in particular, in going through this part of the 378 00:25:03,940 --> 00:25:09,990 process, we choose the sampling rate for going from 379 00:25:09,990 --> 00:25:13,710 the continuous time signal to the sequence so that we don't 380 00:25:13,710 --> 00:25:15,750 violate the sampling theorem. 381 00:25:15,750 --> 00:25:19,500 Well let's suppose, then, that this is the spectrum of the 382 00:25:19,500 --> 00:25:22,380 continuous time signal. 383 00:25:22,380 --> 00:25:27,170 Below it, we have the spectrum of the output of the 384 00:25:27,170 --> 00:25:31,200 continuous to discrete time conversion. 385 00:25:31,200 --> 00:25:36,090 And I've chosen the sampling frequency to be just high 386 00:25:36,090 --> 00:25:38,560 enough so that I avoid aliasing. 387 00:25:41,350 --> 00:25:47,220 Well that then is the lowest sampling frequency I can pick. 388 00:25:47,220 --> 00:25:51,860 But now, if we go through some additional low pass filtering, 389 00:25:51,860 --> 00:25:53,580 then let's see what happens. 390 00:25:53,580 --> 00:25:59,790 If I now low pass filter the sequence x of n, then in 391 00:25:59,790 --> 00:26:03,340 effect, I'm multiplying the sequence 392 00:26:03,340 --> 00:26:06,490 spectrum by this filter. 393 00:26:06,490 --> 00:26:10,470 And so the result of that, the product of the filter 394 00:26:10,470 --> 00:26:14,380 frequency response and the Fourier transform of x of n 395 00:26:14,380 --> 00:26:20,130 would have a shape somewhat like I indicate below. 396 00:26:20,130 --> 00:26:25,490 Now notice that in this spectrum, although in the 397 00:26:25,490 --> 00:26:31,490 input to the filter this entire band was filled up, in 398 00:26:31,490 --> 00:26:38,380 the output of the filter, there is a band that in fact 399 00:26:38,380 --> 00:26:40,190 has zero energy in it. 400 00:26:40,190 --> 00:26:45,310 So what I can consider doing is taking the output sequence 401 00:26:45,310 --> 00:26:49,590 from the filter and in fact resampling it, in other words 402 00:26:49,590 --> 00:26:53,520 sampling it, which would be more or less associated with a 403 00:26:53,520 --> 00:26:56,230 different sampling rate for the continuous 404 00:26:56,230 --> 00:26:58,560 time signals involved. 405 00:26:58,560 --> 00:27:02,830 So I could now go through a process which is commonly 406 00:27:02,830 --> 00:27:05,900 referred to as down sampling that is lowering 407 00:27:05,900 --> 00:27:07,270 the sampling rate. 408 00:27:07,270 --> 00:27:10,570 When we do that, of course, what's going to happen is that 409 00:27:10,570 --> 00:27:13,690 in fact this spectral energy will now fill 410 00:27:13,690 --> 00:27:16,110 out more of the band. 411 00:27:16,110 --> 00:27:21,950 And for example, if this was a third, then in fact if I down 412 00:27:21,950 --> 00:27:25,470 sampled by a factor of three, then I would fill up the 413 00:27:25,470 --> 00:27:27,400 entire band with this energy. 414 00:27:27,400 --> 00:27:29,870 But since I've done some additional low pass filtering, 415 00:27:29,870 --> 00:27:34,260 as I indicate here, there's no problem with aliasing. 416 00:27:34,260 --> 00:27:38,230 If I had, let's say, down sampled by a factor of three 417 00:27:38,230 --> 00:27:40,880 and I'm now taking that signal and converting it back to a 418 00:27:40,880 --> 00:27:45,430 continuous time signal, then of course the way I can do 419 00:27:45,430 --> 00:27:51,170 that is by simply running my output clock for the discrete 420 00:27:51,170 --> 00:27:52,760 to continuous time converter. 421 00:27:52,760 --> 00:27:56,600 I can run my output clock at a third the rate 422 00:27:56,600 --> 00:27:58,380 of the input clock. 423 00:27:58,380 --> 00:28:00,250 And that, in effect, takes care of the 424 00:28:00,250 --> 00:28:01,500 bookkeeping for me. 425 00:28:03,930 --> 00:28:11,000 So here we have now the notion of sampling a sequence, and 426 00:28:11,000 --> 00:28:14,250 very closely tied in with that, the notion of decimating 427 00:28:14,250 --> 00:28:19,000 a sequence, and related to both of those, the notion of 428 00:28:19,000 --> 00:28:22,630 down sampling, that is changing the sampling rates so 429 00:28:22,630 --> 00:28:25,880 that, if we were trying this in with continuous time 430 00:28:25,880 --> 00:28:30,170 signals, we've essentially changed our clock rate. 431 00:28:30,170 --> 00:28:35,030 And we might also want to, and it's important to, consider 432 00:28:35,030 --> 00:28:36,800 the opposite of that. 433 00:28:36,800 --> 00:28:41,140 So now a question is what's the opposite of decimation. 434 00:28:41,140 --> 00:28:45,080 Suppose that we had a sequence and we decimate it. 435 00:28:45,080 --> 00:28:49,470 Thinking about it as a 2-step process, that would correspond 436 00:28:49,470 --> 00:28:52,170 to first multiplying by an impulse train, where there are 437 00:28:52,170 --> 00:28:56,920 bunch of zeros in there, and then choosing, throwing away 438 00:28:56,920 --> 00:29:00,880 the zeros and keeping only the values that are non-zero, 439 00:29:00,880 --> 00:29:03,370 because the zeros we can always recreate. 440 00:29:03,370 --> 00:29:06,570 Well, in fact, the inverse process is very specifically a 441 00:29:06,570 --> 00:29:10,955 process of recreating the zeros and then doing the 442 00:29:10,955 --> 00:29:12,860 desampling. 443 00:29:12,860 --> 00:29:22,610 So in the opposite operation, what we would do is undo the 444 00:29:22,610 --> 00:29:24,890 decimation step. 445 00:29:24,890 --> 00:29:28,330 And that would consist of converting the decimated 446 00:29:28,330 --> 00:29:35,790 sequence back to an impulse train and then processing that 447 00:29:35,790 --> 00:29:42,470 impulse train by an ideal low pass filter to do the 448 00:29:42,470 --> 00:29:46,500 interpolation or reconstruction, filling in the 449 00:29:46,500 --> 00:29:51,610 values which, in this impulse train, are equal to zero. 450 00:29:51,610 --> 00:29:53,640 So we now have the two steps. 451 00:29:53,640 --> 00:29:56,490 We take the decimated sequence and we expand it 452 00:29:56,490 --> 00:29:58,950 out, putting in zeros. 453 00:29:58,950 --> 00:30:03,380 And then we desample that by processing it through a low 454 00:30:03,380 --> 00:30:05,150 pass filter. 455 00:30:05,150 --> 00:30:12,680 So just kind of looking at sequences again, what we have 456 00:30:12,680 --> 00:30:18,360 is an original sequence, the sequence x of n. 457 00:30:18,360 --> 00:30:23,510 And then the sample sequence is simply a sequence which 458 00:30:23,510 --> 00:30:26,100 alternates, in this particular case, those 459 00:30:26,100 --> 00:30:28,300 sequence values was zero. 460 00:30:28,300 --> 00:30:35,610 Here what we're assuming is that the sampling period is 2. 461 00:30:35,610 --> 00:30:40,160 And so every other value here is equal to zero. 462 00:30:40,160 --> 00:30:45,350 The decimated sequence then is this sequence, collapsed as I 463 00:30:45,350 --> 00:30:48,400 show in the sequence above. 464 00:30:48,400 --> 00:30:52,960 And so it's, in effect, time compressing the sample 465 00:30:52,960 --> 00:30:57,160 sequence or the original sequence so that we throw out 466 00:30:57,160 --> 00:30:59,890 the sequence values which were equal to zero 467 00:30:59,890 --> 00:31:02,500 in the sample sequence. 468 00:31:02,500 --> 00:31:06,270 Now in recovering the original sequence from the decimated 469 00:31:06,270 --> 00:31:09,400 sequence, we can think of a 2-step process. 470 00:31:09,400 --> 00:31:15,640 Namely, we spread this out alternating with zeros, and 471 00:31:15,640 --> 00:31:18,050 again, keeping in mind that this is drawn for the case 472 00:31:18,050 --> 00:31:19,950 where capital N is 2. 473 00:31:19,950 --> 00:31:23,630 And then finally, we interpolate between the 474 00:31:23,630 --> 00:31:28,700 non-zero values here by going through a low pass filter to 475 00:31:28,700 --> 00:31:32,240 reconstruct the original sequence. 476 00:31:32,240 --> 00:31:36,650 And that's what we show finally on the bottom curve. 477 00:31:36,650 --> 00:31:39,730 So that's what we would see in the time domain. 478 00:31:39,730 --> 00:31:43,950 Let's look at what we would see in the frequency domain. 479 00:31:43,950 --> 00:31:48,860 In the frequency domain, we have to begin with the 480 00:31:48,860 --> 00:31:52,020 sequence on the bottom, or the spectrum on the bottom, which 481 00:31:52,020 --> 00:31:56,400 would correspond to the original spectrum. 482 00:31:56,400 --> 00:31:59,710 Then, through the sampling process, that is periodically 483 00:31:59,710 --> 00:32:00,910 replicated. 484 00:32:00,910 --> 00:32:04,990 Again, this is drawn on the assumption that the sampling 485 00:32:04,990 --> 00:32:09,870 frequency is pi or the sampling period is equal to 2. 486 00:32:09,870 --> 00:32:12,480 And so this is now replicated. 487 00:32:12,480 --> 00:32:17,310 And then, in going from this to the spectrum of the 488 00:32:17,310 --> 00:32:23,990 decimated sequence, we would rescale the frequency axis so 489 00:32:23,990 --> 00:32:29,590 that the frequency pi now gets rescaled in the spectrum for 490 00:32:29,590 --> 00:32:34,090 the decimated sequence to a frequency which is 2 pi. 491 00:32:34,090 --> 00:32:36,900 And so this now is the spectrum of 492 00:32:36,900 --> 00:32:38,970 the decimated sequence. 493 00:32:38,970 --> 00:32:44,990 If we now want to reconvert to the original sequence we would 494 00:32:44,990 --> 00:32:49,210 first intersperse in the time domain with zeros, 495 00:32:49,210 --> 00:32:54,910 corresponding to compressing in the frequency domain. 496 00:32:54,910 --> 00:32:58,610 This would then be low pass filtered. 497 00:32:58,610 --> 00:33:02,680 And the low pass filtering would consist of throwing away 498 00:33:02,680 --> 00:33:06,600 this replication, accounting for a factor which is the 499 00:33:06,600 --> 00:33:10,630 factor capital N, and extracting the portion of the 500 00:33:10,630 --> 00:33:16,680 spectrum which is associated with the spectrum of the 501 00:33:16,680 --> 00:33:20,110 original signal which we began with. 502 00:33:20,110 --> 00:33:24,420 So once again, we have decimation and interpolation. 503 00:33:24,420 --> 00:33:30,150 And the decimation can be thought of as a time 504 00:33:30,150 --> 00:33:34,250 compression that corresponds to a frequency expansion then. 505 00:33:34,250 --> 00:33:37,890 And the interpolation process is then just the reverse. 506 00:33:41,080 --> 00:33:45,130 Now there are lots of situations in which decimation 507 00:33:45,130 --> 00:33:48,980 and interpolation and discrete time sampling are useful. 508 00:33:48,980 --> 00:33:52,390 And one context that I just want to quickly draw your 509 00:33:52,390 --> 00:33:56,480 attention to is the use of decimation and interpolation 510 00:33:56,480 --> 00:34:00,030 in what is commonly referred to as sampling rate 511 00:34:00,030 --> 00:34:01,480 conversion. 512 00:34:01,480 --> 00:34:05,710 What the basic issue and sampling rate conversion is is 513 00:34:05,710 --> 00:34:10,650 that, in some situations, and a very common one is digital 514 00:34:10,650 --> 00:34:15,330 audio, a continuous time signal is sampled. 515 00:34:15,330 --> 00:34:18,850 And those sampled values are stored or whatever. 516 00:34:18,850 --> 00:34:22,699 And kind of the notion is that, perhaps when that is 517 00:34:22,699 --> 00:34:26,530 played back, it's played back through a different system. 518 00:34:26,530 --> 00:34:31,350 And the different system has a different assumed sampling 519 00:34:31,350 --> 00:34:33,480 frequency or sampling period. 520 00:34:33,480 --> 00:34:36,630 So that's kind of the issue and the idea. 521 00:34:36,630 --> 00:34:41,090 We have, let's say, a continuous time signal which 522 00:34:41,090 --> 00:34:45,070 we've converted to a sequence through a sampling process 523 00:34:45,070 --> 00:34:48,830 using an assumed sampling period of T1. 524 00:34:48,830 --> 00:34:54,420 And these sequence values may then, for example, be put into 525 00:34:54,420 --> 00:34:55,710 digital storage. 526 00:34:55,710 --> 00:34:59,360 In the case of a digital audio system, it may, for example, 527 00:34:59,360 --> 00:35:01,720 go onto a digital record. 528 00:35:01,720 --> 00:35:06,660 And it might be the output of this that we want to recreate. 529 00:35:06,660 --> 00:35:11,350 Or we might in fact follow that with some additional 530 00:35:11,350 --> 00:35:14,120 processing, whatever that additional processing is. 531 00:35:14,120 --> 00:35:17,400 And I'll kind of put a question mark in there because 532 00:35:17,400 --> 00:35:21,030 we don't know exactly what that might be. 533 00:35:21,030 --> 00:35:25,900 And then, in any case, the result of that is going to be 534 00:35:25,900 --> 00:35:30,540 converted back to a continuous time signal. 535 00:35:30,540 --> 00:35:36,470 But it might be converted through a system that has a 536 00:35:36,470 --> 00:35:40,660 different assumed sampling period. 537 00:35:40,660 --> 00:35:44,950 And so a very common issue, and it comes up as I indicated 538 00:35:44,950 --> 00:35:50,190 particularly in digital audio, a very common issue is to be 539 00:35:50,190 --> 00:35:55,490 able to convert from one assumed sampling period, T1, 540 00:35:55,490 --> 00:35:58,660 our sampling frequency, to another 541 00:35:58,660 --> 00:36:00,780 assumed sampling period. 542 00:36:00,780 --> 00:36:02,120 Now how do we do that? 543 00:36:02,120 --> 00:36:07,460 Well in fact, we do that by using the ideas of decimation 544 00:36:07,460 --> 00:36:09,140 and interpolation. 545 00:36:09,140 --> 00:36:14,110 In particular, if we had, for example, a situation where we 546 00:36:14,110 --> 00:36:19,180 wanted to convert from a sampling period, T1, to a 547 00:36:19,180 --> 00:36:24,210 sampling period which was twice as long as that, then 548 00:36:24,210 --> 00:36:29,340 essentially, we're going to take the sequence and process 549 00:36:29,340 --> 00:36:32,710 it in a way that would, in effect, correspond to assuming 550 00:36:32,710 --> 00:36:36,190 that we had sampled at half the original frequency. 551 00:36:36,190 --> 00:36:37,440 Well how do we do that? 552 00:36:37,440 --> 00:36:40,210 The way we do it is we take the sequence we have and we 553 00:36:40,210 --> 00:36:43,460 just throw away every other value. 554 00:36:43,460 --> 00:36:47,370 So in that case, we would then, for this sampling rate 555 00:36:47,370 --> 00:36:51,560 conversion, down sample and decimate. 556 00:36:51,560 --> 00:36:54,770 Or actually, we might not go through this step formally. 557 00:36:54,770 --> 00:36:57,520 We might just simply decimate. 558 00:36:57,520 --> 00:37:02,590 Now we might have an alternative situation where in 559 00:37:02,590 --> 00:37:05,680 fact the new sampling period, or the sampling period of the 560 00:37:05,680 --> 00:37:09,230 output, is half the sampling period of the input, 561 00:37:09,230 --> 00:37:13,670 corresponding to an assumed sampling frequency, which is 562 00:37:13,670 --> 00:37:15,550 twice as high. 563 00:37:15,550 --> 00:37:20,010 And in that case, then., we would go through a process of 564 00:37:20,010 --> 00:37:21,000 interpolation. 565 00:37:21,000 --> 00:37:25,730 And in particular, we would up sample and interpolate by a 566 00:37:25,730 --> 00:37:27,780 factor of 2 to one. 567 00:37:27,780 --> 00:37:31,090 So in one case, we're simply throwing 568 00:37:31,090 --> 00:37:32,260 away every other value. 569 00:37:32,260 --> 00:37:34,080 In the other case, what we're going to do is take our 570 00:37:34,080 --> 00:37:37,630 sequence, put in zeros, put it through a low pass filter to 571 00:37:37,630 --> 00:37:39,470 interpolate. 572 00:37:39,470 --> 00:37:43,300 Now life would be simple if everything happened in simple 573 00:37:43,300 --> 00:37:45,070 integer amounts like that. 574 00:37:45,070 --> 00:37:49,690 A more common situation is that we may have an assumed 575 00:37:49,690 --> 00:37:55,250 output sampling period which is 3/2 of the 576 00:37:55,250 --> 00:37:57,250 input sampling period. 577 00:37:57,250 --> 00:38:00,530 And now the question is what are we going to do to convert 578 00:38:00,530 --> 00:38:04,520 from this sampling period to this sampling period. 579 00:38:04,520 --> 00:38:09,850 Well, in fact, the answer to that is to use a combination 580 00:38:09,850 --> 00:38:13,090 of down sampling and up sampling, or up sampling and 581 00:38:13,090 --> 00:38:17,470 down sampling, equivalently interpolation and decimation. 582 00:38:17,470 --> 00:38:21,900 And for this particular case, in fact, what we would do is 583 00:38:21,900 --> 00:38:28,630 to first take the data, up sample by a factor of 2, and 584 00:38:28,630 --> 00:38:33,370 then down sample the result of that by a factor of 3. 585 00:38:33,370 --> 00:38:37,290 And what that would give us is a sampling rate conversion, 586 00:38:37,290 --> 00:38:42,750 overall, of 3/2, or a sampling period conversion of 3/2. 587 00:38:42,750 --> 00:38:45,730 And more generally, what you could think of is how you 588 00:38:45,730 --> 00:38:51,240 might do this if, in general, the relationship between the 589 00:38:51,240 --> 00:38:54,090 input and output sampling periods was some rational 590 00:38:54,090 --> 00:38:56,190 number p/q. 591 00:38:56,190 --> 00:39:00,350 And so in fact, in many systems, in hardware systems 592 00:39:00,350 --> 00:39:04,370 related to digital audio, very often the sampling rate 593 00:39:04,370 --> 00:39:07,160 conversion, most typically the sampling rate conversion, is 594 00:39:07,160 --> 00:39:12,570 done through a process of up sampling or interpolating and 595 00:39:12,570 --> 00:39:15,280 then down sampling by some other amount. 596 00:39:18,470 --> 00:39:23,970 Now what we've seen, what we talked about in a set of 597 00:39:23,970 --> 00:39:29,830 lectures, is the concepts of sampling a signal. 598 00:39:29,830 --> 00:39:32,640 And what we've seen is that the signal can be represented 599 00:39:32,640 --> 00:39:35,140 by samples under certain conditions. 600 00:39:35,140 --> 00:39:38,240 And the sampling that we've been talking about is sampling 601 00:39:38,240 --> 00:39:39,020 in the time domain. 602 00:39:39,020 --> 00:39:41,920 And we've done that for continuous time and we've done 603 00:39:41,920 --> 00:39:45,150 it for discrete time. 604 00:39:45,150 --> 00:39:49,450 Now we know that there is some type of duality both 605 00:39:49,450 --> 00:39:52,600 continuous time and discrete time, some type of duality, 606 00:39:52,600 --> 00:39:55,240 between the time domain and frequency domain. 607 00:39:55,240 --> 00:40:01,220 And so, as you can imagine, we can also talk about sampling 608 00:40:01,220 --> 00:40:07,720 in the frequency domain and expect that, more or less, the 609 00:40:07,720 --> 00:40:11,640 kinds of properties and analysis will be similar to 610 00:40:11,640 --> 00:40:15,400 those related to sampling in the time domain. 611 00:40:15,400 --> 00:40:21,020 Well I want to talk just briefly about that and leave 612 00:40:21,020 --> 00:40:24,810 the more detailed discussion to the text and 613 00:40:24,810 --> 00:40:26,550 video course manual. 614 00:40:26,550 --> 00:40:29,980 But let me indicate, for example, one context in which 615 00:40:29,980 --> 00:40:32,370 frequency domain sampling is important. 616 00:40:32,370 --> 00:40:38,220 Suppose that you have a signal and what you'd like to measure 617 00:40:38,220 --> 00:40:41,770 is its Fourier transform, its spectrum. 618 00:40:41,770 --> 00:40:46,130 Well of course, if you want to measure it or calculate it, 619 00:40:46,130 --> 00:40:49,150 you can never do that exactly at every single frequency. 620 00:40:49,150 --> 00:40:50,630 There are too many frequencies, namely, an 621 00:40:50,630 --> 00:40:52,280 infinite number of them. 622 00:40:52,280 --> 00:40:55,670 And so, in fact, all that you can really calculate or 623 00:40:55,670 --> 00:41:00,920 measure is the Fourier transform at a set of sample 624 00:41:00,920 --> 00:41:02,170 frequencies. 625 00:41:02,170 --> 00:41:06,570 So essentially, if you are going to look at a spectrum, 626 00:41:06,570 --> 00:41:09,950 continuous time or discrete time, you can only really look 627 00:41:09,950 --> 00:41:11,060 at samples. 628 00:41:11,060 --> 00:41:15,210 And a reasonable question to ask, then, is when does a set 629 00:41:15,210 --> 00:41:19,500 of samples in fact tell you everything that there is to 630 00:41:19,500 --> 00:41:23,450 know about the Fourier transform. 631 00:41:23,450 --> 00:41:27,100 That, and the answer to that, is very closely related to the 632 00:41:27,100 --> 00:41:31,140 concept of frequency domain sampling. 633 00:41:31,140 --> 00:41:33,770 Well, frequency domain sampling, just to kind of 634 00:41:33,770 --> 00:41:37,900 introduce the topic, corresponds and can be 635 00:41:37,900 --> 00:41:44,300 analyzed in terms doing modulation in the frequency 636 00:41:44,300 --> 00:41:48,280 domain, very much like the modulation that we carried out 637 00:41:48,280 --> 00:41:51,160 in the time domain for time domain sampling. 638 00:41:51,160 --> 00:41:57,440 And so we would multiply the Fourier transform of the 639 00:41:57,440 --> 00:42:02,200 signal whose spectrum is to be sampled by an 640 00:42:02,200 --> 00:42:05,060 impulse train in frequency. 641 00:42:05,060 --> 00:42:10,520 And so shown below is what might be a representative 642 00:42:10,520 --> 00:42:13,660 spectrum for the input signal. 643 00:42:13,660 --> 00:42:19,550 And the spectrum, then for the signal associated with the 644 00:42:19,550 --> 00:42:23,760 frequency domain sampling, consists of multiplying the 645 00:42:23,760 --> 00:42:27,670 frequency domain by this impulse train. 646 00:42:27,670 --> 00:42:32,950 Or correspondingly, the Fourier transform of the 647 00:42:32,950 --> 00:42:39,430 resulting signal is an impulse train in frequency with an 648 00:42:39,430 --> 00:42:42,670 envelope which is the original spectrum 649 00:42:42,670 --> 00:42:45,420 that we were sampling. 650 00:42:45,420 --> 00:42:48,360 Well, this of course is what we would do in 651 00:42:48,360 --> 00:42:49,620 the frequency domain. 652 00:42:49,620 --> 00:42:52,560 It's modulation by an impulse train. 653 00:42:52,560 --> 00:42:55,690 What does this mean in the time domain? 654 00:42:55,690 --> 00:42:57,070 Well, let's see. 655 00:42:57,070 --> 00:42:59,690 Multiplication in the time domain is convolution in the 656 00:42:59,690 --> 00:43:01,220 frequency domain. 657 00:43:01,220 --> 00:43:04,210 Convolution in the frequency domain is multiplication-- 658 00:43:04,210 --> 00:43:04,880 I'm sorry. 659 00:43:04,880 --> 00:43:07,700 Multiplication in the frequency domain, then, is 660 00:43:07,700 --> 00:43:09,660 convolution in the time domain. 661 00:43:09,660 --> 00:43:12,490 And in fact, the process in the time domain is a 662 00:43:12,490 --> 00:43:14,120 convolution process. 663 00:43:14,120 --> 00:43:22,020 Namely, the time domain signal is replicated at integer 664 00:43:22,020 --> 00:43:26,840 amounts of a particular time associated with the spacing in 665 00:43:26,840 --> 00:43:29,050 frequency under which we're doing the 666 00:43:29,050 --> 00:43:31,340 frequency domain sampling. 667 00:43:31,340 --> 00:43:39,590 So in fact, if we look at this in the time domain, the 668 00:43:39,590 --> 00:43:46,170 resulting picture corresponds to an original signal whose 669 00:43:46,170 --> 00:43:50,150 spectrum or Fourier transform we've sampled. 670 00:43:50,150 --> 00:43:53,980 And a consequence of the sampling is that the 671 00:43:53,980 --> 00:43:58,220 associated time domain signal is just like the original 672 00:43:58,220 --> 00:44:02,490 signal, but periodically replicated, in time now, not 673 00:44:02,490 --> 00:44:07,020 frequency, but in time, at integer multiples of 2 pi 674 00:44:07,020 --> 00:44:12,720 divided by the spectral sampling interval omega 0. 675 00:44:12,720 --> 00:44:18,050 And so this then is the time function associated with the 676 00:44:18,050 --> 00:44:20,630 sample frequency function. 677 00:44:20,630 --> 00:44:24,640 Now, that's not surprising because what we've done is 678 00:44:24,640 --> 00:44:27,750 generated an impulse train and frequency 679 00:44:27,750 --> 00:44:29,660 with a certain envelope. 680 00:44:29,660 --> 00:44:32,460 We know that an impulse train in frequency is the Fourier 681 00:44:32,460 --> 00:44:36,340 transform of a periodic time function. 682 00:44:36,340 --> 00:44:39,180 And so in fact, we have a periodic time function. 683 00:44:39,180 --> 00:44:43,240 We also know that the envelope of those impulses-- 684 00:44:43,240 --> 00:44:46,500 we know this from way back when we talked about Fourier 685 00:44:46,500 --> 00:44:47,670 transforms-- 686 00:44:47,670 --> 00:44:49,560 the envelope, in fact, is the Fourier 687 00:44:49,560 --> 00:44:51,060 transform of one period. 688 00:44:51,060 --> 00:44:54,400 And so all of this, of course, fits together as it should in 689 00:44:54,400 --> 00:44:56,620 a consistent way. 690 00:44:56,620 --> 00:45:02,340 Now given that we have this periodic time function whose 691 00:45:02,340 --> 00:45:05,460 Fourier transform is the samples in the frequency 692 00:45:05,460 --> 00:45:10,250 domain, how do we get back the original time function? 693 00:45:10,250 --> 00:45:17,070 Well, with time domain sampling, what we did was to 694 00:45:17,070 --> 00:45:21,370 multiply in the frequency domain by a gate, or window, 695 00:45:21,370 --> 00:45:24,060 to extract that part of the spectrum. 696 00:45:24,060 --> 00:45:29,080 What we do here is exactly the same thing, namely multiply in 697 00:45:29,080 --> 00:45:34,650 the time domain by a time window which extracts just one 698 00:45:34,650 --> 00:45:38,280 period of this periodic signal, which would then give 699 00:45:38,280 --> 00:45:42,930 us back the original signal that we started with. 700 00:45:42,930 --> 00:45:48,550 Now also let's keep in mind, going back to this time 701 00:45:48,550 --> 00:45:52,400 function and the relationship between them, then again, 702 00:45:52,400 --> 00:45:56,090 there is the potential, if this time function is too long 703 00:45:56,090 --> 00:46:00,780 in relation to 2 pi divided by omega 0, there's the potential 704 00:46:00,780 --> 00:46:02,420 for these to overlap. 705 00:46:02,420 --> 00:46:06,880 And so what this means is that, in fact, what we can end 706 00:46:06,880 --> 00:46:11,320 up with, if the sample spacing and the frequency is not small 707 00:46:11,320 --> 00:46:15,100 enough, what we can end up with is an overlap in the 708 00:46:15,100 --> 00:46:17,530 replication in the time domain. 709 00:46:17,530 --> 00:46:21,220 And what that corresponds to and what it's called is, in 710 00:46:21,220 --> 00:46:23,200 fact, time aliasing. 711 00:46:23,200 --> 00:46:27,590 So we can have time aliasing with frequency domain sampling 712 00:46:27,590 --> 00:46:30,440 just as we can have frequency aliasing 713 00:46:30,440 --> 00:46:33,440 with time domain sampling. 714 00:46:33,440 --> 00:46:37,730 Finally, let me just indicate very quickly that, although 715 00:46:37,730 --> 00:46:41,780 we're not going through this in any detail, the same basic 716 00:46:41,780 --> 00:46:44,820 idea applies in discrete time. 717 00:46:44,820 --> 00:46:50,280 Namely, if we have a discrete time signal and if the 718 00:46:50,280 --> 00:46:55,870 discrete time signal is a finite length, if we sample 719 00:46:55,870 --> 00:47:01,260 its Fourier transform, the time function associated with 720 00:47:01,260 --> 00:47:05,980 those samples is a periodic replication. 721 00:47:05,980 --> 00:47:11,270 And we can now extract, from this periodic signal, the 722 00:47:11,270 --> 00:47:16,080 original signal by multiplying by an appropriate time window, 723 00:47:16,080 --> 00:47:19,660 the product of that giving us the reconstructed time 724 00:47:19,660 --> 00:47:21,630 function as I indicate below. 725 00:47:24,730 --> 00:47:29,100 So we've now seen a little bit of the notion of frequency 726 00:47:29,100 --> 00:47:31,690 domain sampling, as well as time domain sampling. 727 00:47:31,690 --> 00:47:34,440 And let me stress that, although I haven't gone into 728 00:47:34,440 --> 00:47:38,800 this in a lot of detail, it's important. 729 00:47:38,800 --> 00:47:40,510 It's used very often. 730 00:47:40,510 --> 00:47:43,020 It's naturally important to understand it. 731 00:47:43,020 --> 00:47:46,550 But, in fact, there is so much duality between the time 732 00:47:46,550 --> 00:47:49,460 domain and frequency domain, that a thorough understanding 733 00:47:49,460 --> 00:47:53,270 of time domain sampling just naturally leads to a thorough 734 00:47:53,270 --> 00:47:55,520 understanding of frequency domain sampling. 735 00:47:58,810 --> 00:48:01,680 Now we've talked a lot about sampling. 736 00:48:01,680 --> 00:48:06,840 And this now concludes our discussion of sampling. 737 00:48:06,840 --> 00:48:10,170 I've stressed many times in the lectures associated with 738 00:48:10,170 --> 00:48:16,020 this that sampling is a very important topic in the context 739 00:48:16,020 --> 00:48:19,440 of our whole discussion, in part because it forms such an 740 00:48:19,440 --> 00:48:22,520 important bridge between continuous time and discrete 741 00:48:22,520 --> 00:48:23,890 time ideas. 742 00:48:23,890 --> 00:48:27,150 And your picture now should kind of be a global one that 743 00:48:27,150 --> 00:48:31,060 sees how continuous time and discrete time fit together, 744 00:48:31,060 --> 00:48:33,395 not just analytically, but also practically. 745 00:48:36,510 --> 00:48:42,560 Beginning in the next lecture, what I will introduce is the 746 00:48:42,560 --> 00:48:46,740 Laplace transform and, beyond that, the Z transform. 747 00:48:46,740 --> 00:48:51,460 And what those will correspond to are generalizations of the 748 00:48:51,460 --> 00:48:52,930 Fourier transform. 749 00:48:52,930 --> 00:48:55,730 So we now want to turn our attention back to some 750 00:48:55,730 --> 00:48:59,270 analytical tools, in particular developing some 751 00:48:59,270 --> 00:49:03,830 generalizations of the Fourier transform in both continuous 752 00:49:03,830 --> 00:49:05,780 time and discrete time. 753 00:49:05,780 --> 00:49:11,140 And what we'll see is that those generalizations provide 754 00:49:11,140 --> 00:49:16,510 us with considerably enhanced flexibility in dealing with 755 00:49:16,510 --> 00:49:21,210 and analyzing both signals and linear time invariant systems. 756 00:49:21,210 --> 00:49:22,460 Thank you.