1 00:00:00,012 --> 00:00:05,384 In previous videos we have defined the spectrum of a discrete time signal. 2 00:00:05,384 --> 00:00:08,550 The discrete time Fourier transform or a DTFT. 3 00:00:08,550 --> 00:00:13,704 Well, it turns out if you try to apply that formula to the computational 4 00:00:13,704 --> 00:00:19,658 spectrum which you didn't have a formula for, example The signal was data, you'd 5 00:00:19,658 --> 00:00:24,208 be in big trouble. it turns out for all kinds of reasons as 6 00:00:24,208 --> 00:00:29,812 I'll show you, you actually could not compute this spectrum of that signal. 7 00:00:29,812 --> 00:00:36,115 You couldn't find the spectrum at all. So we're going to define, the tool, the 8 00:00:36,115 --> 00:00:41,772 Discrete Fourier Transform or the DFT, that allows us to perform spectral 9 00:00:41,772 --> 00:00:47,590 analysis from discrete time signals. I'm going to show you that this is not a 10 00:00:47,590 --> 00:00:53,337 new transform, it's directly related to That the DTFT, but its used for 11 00:00:53,337 --> 00:00:58,717 computational purposes, we actually can compute the spectrum. 12 00:00:58,717 --> 00:01:05,362 To go for its properties and it shouldn't be much surprising that there are some 13 00:01:05,362 --> 00:01:12,432 details when you actually try to apply in applications.So lets worry about actually 14 00:01:12,432 --> 00:01:17,683 computing. The DTFT, and I don't mean analytically I 15 00:01:17,683 --> 00:01:23,316 mean computing. So, there are two problems in computing 16 00:01:23,316 --> 00:01:27,780 the DTFT. The first is, that the, Formula here 17 00:01:27,780 --> 00:01:33,126 assumes the signal is infinite duration. Well, that's a problem because how in the 18 00:01:33,126 --> 00:01:38,007 world would you even store an infinite duration computer much less compute this 19 00:01:38,007 --> 00:01:41,249 expression. So I think it's pretty obvious how we're 20 00:01:41,249 --> 00:01:44,762 going to fix that. That one's not really very difficult. 21 00:01:44,762 --> 00:01:50,993 But the next one is, and that is F is a continuous variable. 22 00:01:50,993 --> 00:01:59,889 And this expression, F, is a, is a, fraction, let's say, going through zero 23 00:01:59,889 --> 00:02:04,512 up To 1. All right because it is periodic with 24 00:02:04,512 --> 00:02:12,129 period 1 or we have to compute it for every value in that interval, reason is 25 00:02:12,129 --> 00:02:18,577 the inverse transform. Let me write the inverse transform so we 26 00:02:18,577 --> 00:02:24,682 can remember what it was, so we take the DTFT multiplied by. 27 00:02:24,682 --> 00:02:28,806 An integrate. The problem is integration. 28 00:02:28,806 --> 00:02:35,746 We would need to compute this formula for every value of f, and there's an 29 00:02:35,746 --> 00:02:42,412 uncountably infinite number of values. In order to find what the original signal 30 00:02:42,412 --> 00:02:45,312 was. We don't want the spectrum to be a dead 31 00:02:45,312 --> 00:02:47,837 end. We want to be able to get back the 32 00:02:47,837 --> 00:02:53,237 original signal in many applications. So this continuous frequency variable is 33 00:02:53,237 --> 00:02:57,002 a real problem. So, we're going to fix these 2 problems 34 00:02:57,002 --> 00:03:01,067 And the first one will be, fixing the first ones easy. 35 00:03:01,067 --> 00:03:06,687 You're only going to deal with finite duration signals, so every signal is 36 00:03:06,687 --> 00:03:12,542 going to be linked in, as N values and we're going to know what N is because 37 00:03:12,542 --> 00:03:17,608 we're the ones computing the spectra That one's not hard. 38 00:03:17,608 --> 00:03:23,097 The second problem's got an interesting solution. 39 00:03:23,097 --> 00:03:30,925 We're going to sample infrequency. So we're only going to evaluate the DTFT 40 00:03:30,925 --> 00:03:38,930 at a set of values given by k/K. Okay, k is the frequency index from 0 up 41 00:03:38,930 --> 00:03:45,598 to K minus 1. And of course, that means we're 42 00:03:45,598 --> 00:03:51,982 evaluating f, from 0 up to K minus 1 over K. 43 00:03:51,982 --> 00:03:56,300 And that is sampling the interval zero to one. 44 00:03:56,300 --> 00:04:02,580 leaving off the last value because the value frequency equalt to 1 is the same 45 00:04:02,580 --> 00:04:07,021 as the frequency equal to 0. We don't need to compute that. 46 00:04:07,021 --> 00:04:12,626 So the sampling rate is 1/k. And that's the separation between these 47 00:04:12,626 --> 00:04:16,771 frequencies. Now, we know from the sampling theorem, 48 00:04:16,771 --> 00:04:23,044 that we've already talked about, that the sample in time we need the spectrum to be 49 00:04:23,044 --> 00:04:26,004 band limited. That's the result. 50 00:04:26,004 --> 00:04:33,409 Now here, we're sampling in frequency, which means in time, it needs to be time 51 00:04:33,409 --> 00:04:37,964 limited. And the reason we know this follows, is 52 00:04:37,964 --> 00:04:44,831 because of the similarity mathematical similarity between the expressions of the 53 00:04:44,831 --> 00:04:50,813 transform and its inverse transform. Well, a finite duration signal is time 54 00:04:50,813 --> 00:04:53,703 limited. So, we know it should work. 55 00:04:53,703 --> 00:04:59,169 The question is though, how big is k? We're going to have to worry about how 56 00:04:59,169 --> 00:05:04,184 big does k have to be. The bigger k is, the higher the sampling rate. 57 00:05:04,184 --> 00:05:10,053 Because this related to 1 over k. How big does it have to be? So, here's 58 00:05:10,053 --> 00:05:16,142 the expression for the discrete Fourier transform, the DFT. 59 00:05:16,142 --> 00:05:23,788 It is a sampled version of the DTFT specialized for finite duration signals. 60 00:05:23,788 --> 00:05:30,957 We always take that duration the so-called support To be over zeroed and 61 00:05:30,957 --> 00:05:36,307 minus one it's just the standard the notation for DFT is just S of K. 62 00:05:36,307 --> 00:05:42,777 We don't bother sticking in the detailed expressions for the DDFT and then saying 63 00:05:42,777 --> 00:05:49,102 evaluate it at, at frequencies of little K over big K just simply write it as S of 64 00:05:49,102 --> 00:05:52,847 K. k if the sequence were little k is the 65 00:05:52,847 --> 00:05:58,463 frequency index. This corresponds to a frequency of zero. 66 00:05:58,463 --> 00:06:02,494 And this index corresponds to Z of k minus 1 over K. 67 00:06:02,494 --> 00:06:09,992 All right, again, how long should, how big should k be? That's where we want to 68 00:06:09,992 --> 00:06:12,870 Figure out. Well I'm not going to appeal to the 69 00:06:12,870 --> 00:06:16,872 sampling theorem here. What I'm going to do is do, it in a 70 00:06:16,872 --> 00:06:21,041 slightly different way. And that is because we know the inverse 71 00:06:21,041 --> 00:06:28,967 transform has to look like this. It's going to fit in with every thing we 72 00:06:28,967 --> 00:06:33,547 know. it's going to have to be a sum over the 73 00:06:33,547 --> 00:06:35,692 DFT values times e to the plus j2 pi nk over capital K. 74 00:06:36,892 --> 00:06:44,682 What have I waited over the signals support with where it's defined be 75 00:06:44,682 --> 00:06:52,026 originally, what it's duration was. And if I take this expression, plug it 76 00:06:52,026 --> 00:06:58,445 into here, I better get back s of n to do something proportional to it. 77 00:06:58,445 --> 00:07:04,780 Well, how big does K have to be, in order to make that true? In order that we avoid 78 00:07:04,780 --> 00:07:10,356 aliasing and we get back our original signal at least to a constainable 79 00:07:10,356 --> 00:07:15,131 portionality. And, it's, shouldn't be too surprising, 80 00:07:15,131 --> 00:07:20,722 to see that the result is That big K has to be greater than or equal to the N. 81 00:07:20,722 --> 00:07:25,937 N is the derision of the signal. The details of are shown, are shown in 82 00:07:25,937 --> 00:07:29,709 the notes. you sh, you could do it yourself, it's 83 00:07:29,709 --> 00:07:34,300 not terribly difficult. There are a few little things you have to 84 00:07:34,300 --> 00:07:38,390 look out for, but it's pretty Pretty easy. 85 00:07:38,390 --> 00:07:47,588 Now, I have called this transform length. Let me go into that. 86 00:07:47,588 --> 00:07:56,613 If you look at this expression here, I can write it like this. 87 00:07:56,613 --> 00:08:06,252 I can write it like that. Notice I changed this upper limit here. 88 00:08:06,252 --> 00:08:15,698 Where, since I know that big K is greater than or equal to N, I know that S(n) is, 89 00:08:15,698 --> 00:08:24,146 is non zero, only from 0 to n minus 1, well I can make S(n) [SOUND], I can 90 00:08:24,146 --> 00:08:30,202 define a new S(n) if you will, at 0 not to K minus 1. 91 00:08:30,202 --> 00:08:38,446 Change what it is, and I'm now computing a D, DFT, whose length is given by this 92 00:08:38,446 --> 00:08:44,166 new duration. That's the same thing as taking a longer 93 00:08:44,166 --> 00:08:48,906 transform. So, if you wanted to sample infrequency 94 00:08:48,906 --> 00:08:54,867 more finely, all you do is take a longer transform, longer means. 95 00:08:54,867 --> 00:08:59,942 I have my original signal here, and I just add extra zeros. 96 00:08:59,942 --> 00:09:07,409 To the end of it, until I get to K - 1. Well, that's called padding, and it's 97 00:09:07,409 --> 00:09:13,292 something we do all the time. we want to evaluate the DFT. 98 00:09:13,292 --> 00:09:18,486 and for many reasons, the length greater than the signal's duration. 99 00:09:18,486 --> 00:09:23,755 Let me just call that padding, and just adding extra zeros to the end of it. 100 00:09:23,755 --> 00:09:27,732 Since we know what capital N is, there's no ambiguity. 101 00:09:27,732 --> 00:09:33,559 When we compute the Inverse DFT formula, we're only going to look over the result 102 00:09:33,559 --> 00:09:38,501 of this computation, where we know the original signal values were. 103 00:09:38,501 --> 00:09:43,792 So that's another difficulty, we won't be confused by these extra zeros. 104 00:09:43,792 --> 00:09:47,600 Not a big problem. Adding, your going to, as your going to 105 00:09:47,600 --> 00:09:54,410 discover, is a very important idea. So, let's, Show our DFT and inverse DFT 106 00:09:54,410 --> 00:10:00,103 formulas. And, what happens when you go through the 107 00:10:00,103 --> 00:10:08,562 details is that this normalization of 1/K occurs in the inverse DFT formula. 108 00:10:08,562 --> 00:10:13,635 And of course we need K>=M. Now, most of the routines that compute 109 00:10:13,635 --> 00:10:20,063 the inverse DFT formulas like the ones that come with octave or matlab take care 110 00:10:20,063 --> 00:10:25,223 of this normalization for you. So you don't need to worry about it. 111 00:10:25,223 --> 00:10:32,039 But, if you were going to write your own Or, if you try to find, problems with 112 00:10:32,039 --> 00:10:37,859 routines that you may be using, you need to know about this normalization. 113 00:10:37,859 --> 00:10:43,762 So, they look very similar to each other as you might expect and these 2 formulas 114 00:10:43,762 --> 00:10:49,275 allow us to go between the. Discrete the, the time domain if you will 115 00:10:49,275 --> 00:10:54,919 for a discrete time signal. In the, in its frequency domain, where we 116 00:10:54,919 --> 00:10:58,774 are sampling the actual continuous frequency. 117 00:10:58,774 --> 00:11:03,593 We're sampling it right. These values, I Emphasize that. 118 00:11:03,593 --> 00:11:08,695 And we'll see how this works in an example in just a second. 119 00:11:08,695 --> 00:11:12,558 So, we're evaluating at those frequencies. 120 00:11:12,558 --> 00:11:18,638 So, to show you what it looks like. Here's a constant signal, which I'm going 121 00:11:18,638 --> 00:11:23,070 to be using in my examples. And it's a constant, because it goes from 122 00:11:23,070 --> 00:11:26,519 between 0 and N - 1, and in, all of those values are 1. 123 00:11:26,519 --> 00:11:30,822 When we take a longer transform, what we're essentially doing is. 124 00:11:30,822 --> 00:11:38,132 Padding with 0s out to the new transformer and then we evaluate the dft 125 00:11:38,132 --> 00:11:46,052 expression here with the K essentially being the transformer. 126 00:11:46,052 --> 00:11:51,614 With the added zero stuck on. Now, I want you to notice something about 127 00:11:51,614 --> 00:11:57,087 the inverse DFT formula. So, I can evaluate, this expression for 128 00:11:57,087 --> 00:12:01,969 any value of n I want. I know that's where the signal is, but 129 00:12:01,969 --> 00:12:07,872 what about the other values of N? and what you can see, because of the 130 00:12:07,872 --> 00:12:14,732 properties of that complex exponential, that the Inverse DFT formula is periodic. 131 00:12:14,732 --> 00:12:20,414 With a period equal to capital K, the transform length. 132 00:12:20,414 --> 00:12:28,957 So, if you were to evaluate this inverse DFT expression For all possible values of 133 00:12:28,957 --> 00:12:34,897 n this is what you'd get. You'd get a periodic repetition, of the 134 00:12:34,897 --> 00:12:40,207 original signal. But the period, is k, not n but k because 135 00:12:40,207 --> 00:12:44,802 that's the transform link, that you were using. 136 00:12:44,802 --> 00:12:49,436 Essentially up here. So, what does this mean? That means that 137 00:12:49,436 --> 00:12:55,137 when you actually look at the inverse DFTs result you just ignore everything 138 00:12:55,137 --> 00:12:59,152 outside the range where you know where the signal is. 139 00:12:59,152 --> 00:13:04,321 The other pieces out here are just periodic repetitions, and they're, we 140 00:13:04,321 --> 00:13:09,644 know to ignore them, and we can ignore the padding, because we know why it's 141 00:13:09,644 --> 00:13:12,871 there. It's there just to sample in frequency 142 00:13:12,871 --> 00:13:16,163 more finely. And we didn't really need to do it. 143 00:13:16,163 --> 00:13:21,440 But sometimes, you do it for all kinds, you do it for all kinds of reasons that 144 00:13:21,440 --> 00:13:26,135 we'll talk about a little bit later. So anyway, the original signal only 145 00:13:26,135 --> 00:13:29,434 exists there. And that's all you need to evaluate. 146 00:13:29,434 --> 00:13:32,805 Alright. So, let's go through an extended example, 147 00:13:32,805 --> 00:13:35,813 using our constant signal There's our signal. 148 00:13:35,813 --> 00:13:39,532 It's, zero outside the interval. 0 to n-1. 149 00:13:39,532 --> 00:13:45,951 And we're going to compute its DTFT. So this is, if you will, the true 150 00:13:45,951 --> 00:13:50,036 spectrum. This is the Fourier Transform. 151 00:13:50,036 --> 00:13:57,164 Like I keep saying, if you don't have a formula for your s of n, you'd be you 152 00:13:57,164 --> 00:14:02,013 could be in very great difficulty trying to compute this thing for all 153 00:14:02,013 --> 00:14:05,670 frequencies. so that's why you're DTFT is an int. 154 00:14:05,670 --> 00:14:11,619 But let's compute it analytically for this example. So the way we do that is 155 00:14:11,619 --> 00:14:19,791 use the finite geometric series formula. So, I think you'll agree that this and 156 00:14:19,791 --> 00:14:27,478 this are the same thing when alpha is e to the minus j, 2 pi f, okay? So all we 157 00:14:27,478 --> 00:14:34,725 need to do is plug that in to this expression for the finite geometric 158 00:14:34,725 --> 00:14:42,133 series which you should have seen. And after some simplification, which involves 159 00:14:42,133 --> 00:14:48,129 pulling out at the phase, and the complex exponentials that you get is something 160 00:14:48,129 --> 00:14:54,225 similar we have already done before, we get this result that the DTFT is given 161 00:14:54,225 --> 00:14:58,886 by expression that looks very similar to what we had for the, in the analogue 162 00:14:58,886 --> 00:15:04,373 world, when they computed a Fourier transform of pulse, we get a very similar 163 00:15:04,373 --> 00:15:10,102 looking expression. Except it's not sine x over x, it's sine 164 00:15:10,102 --> 00:15:15,952 in x over sine x and this is called the digital sinc function. 165 00:15:15,952 --> 00:15:22,732 So recall back when we were doing this for analog, we had to define this 166 00:15:22,732 --> 00:15:29,277 function as called the sinc function. And here, what happened in the discrete 167 00:15:29,277 --> 00:15:37,154 time worlds, you get the discreet sync function and it's so called and it's a 168 00:15:37,154 --> 00:15:42,542 sine Nx over sine X. It looks, going to look very similar to 169 00:15:42,542 --> 00:15:48,935 the sin x over x, and the real difference is, and the importance difference this 170 00:15:48,935 --> 00:15:55,480 has to be periodic in N. And this is the way we make it periodic. 171 00:15:55,480 --> 00:16:01,540 So, there's our signal again and now we may compute the DFT. 172 00:16:01,540 --> 00:16:08,546 And expressions is going to look very similar because I'm just sampling The DTF 173 00:16:08,546 --> 00:16:15,162 one, the DTFT format we already did so we get exactly the same kind of expression 174 00:16:15,162 --> 00:16:21,397 that we had before using the finite Q method series and of course that is the 175 00:16:21,397 --> 00:16:31,130 same as sampling the DTFT. So this is the DFT, and this is the DTFT 176 00:16:31,130 --> 00:16:37,972 evaluated at these frequencies. Okay. 177 00:16:37,972 --> 00:16:45,097 So, this just goes to show you there's a sample version that I think that's pretty 178 00:16:45,097 --> 00:16:49,547 obvious. So, what does it look like? So, I'm going 179 00:16:49,547 --> 00:16:55,012 to be plotting this only over frequencies going from 0 to 1/2. 180 00:16:55,012 --> 00:17:01,119 Because we know that it has to be conjugate symmetric, and periodic. 181 00:17:01,119 --> 00:17:07,806 So the DTFT can be evaluated on and on, but this corresponds to positive 182 00:17:07,806 --> 00:17:14,123 frequencies in the range 0 to 0.5. So, this is what the digital sink looks 183 00:17:14,123 --> 00:17:20,450 like, which should be very familiar looking kind of thing, except it's going 184 00:17:20,450 --> 00:17:25,010 to be periodic. It's going to, return, re-, repeat 185 00:17:25,010 --> 00:17:28,527 itself. The phase, looks like this, has this 186 00:17:28,527 --> 00:17:32,797 linear expression. And we understand why this jump by pi 187 00:17:32,797 --> 00:17:38,492 here, has to do with the fact that the digital sync function goes, is really 188 00:17:38,492 --> 00:17:41,852 negative here. And magnitudes don't go negative. 189 00:17:41,852 --> 00:17:46,482 So we have to, make it positive. And that means we have to have a phase 190 00:17:46,482 --> 00:17:49,582 jump a pie. And that's what all of these jumps are 191 00:17:49,582 --> 00:17:52,517 here. They're, they're due to the fact it goes 192 00:17:52,517 --> 00:17:55,007 negative. So it is just a linear phase, 193 00:17:55,007 --> 00:17:59,009 and, and then the values with this technical 194 00:17:59,009 --> 00:18:03,290 requirement that having had the chance to pop. 195 00:18:03,290 --> 00:18:10,192 Alright, so, what does our sample version look like? So, capital N is 10, 196 00:18:10,192 --> 00:18:17,085 and what we get for a transform, which is exactly the same length as the signal's 197 00:18:17,085 --> 00:18:20,936 duration, is we get something very similar. 198 00:18:20,936 --> 00:18:29,588 It may be a little hard to see here, but you get the value there, and the rest are 199 00:18:29,588 --> 00:18:36,000 zero. I'm again, only showing this from little 200 00:18:36,000 --> 00:18:40,519 k equal to 0. Little k equal to capital K over 2, 201 00:18:40,519 --> 00:18:46,363 because the rest is negative frequencies and I don't need to repeat those values 202 00:18:46,363 --> 00:18:50,806 for you to see it. So, I've hidden the fact that the value 203 00:18:50,806 --> 00:18:56,151 at the origin there is 10 which has to do with the link to the transformer. 204 00:18:56,151 --> 00:19:01,471 So, this looks kind of weird is that really the spectrum? Doesn't, we've 205 00:19:01,471 --> 00:19:07,372 sampled and sort of missed all the. Nice parts that wiggle, that only focused 206 00:19:07,372 --> 00:19:11,079 on value of the origin and the values were zero. 207 00:19:11,079 --> 00:19:16,998 Can you actually get the original signal back? Lets worry about that first. 208 00:19:16,998 --> 00:19:25,648 So, does the original signal equal to 1 over K times the sum over k of K in a 209 00:19:25,648 --> 00:19:41,082 formula that we got for the DFT here.. Is that, because this is a unit sample at 210 00:19:41,082 --> 00:19:46,487 the origin, then it's zero everywhere else. 211 00:19:46,487 --> 00:19:53,472 And e plus j 2pi nk over K. Well, the delta k just means the only. 212 00:19:53,472 --> 00:20:01,578 A term that's non-zero, corresponds to k equal to 0. 213 00:20:01,578 --> 00:20:10,654 And these cancel so what we get is e squared plus j pi n k over k With this 214 00:20:10,654 --> 00:20:14,790 thing evaluated always at k equal to 0, which is just 1. 215 00:20:14,790 --> 00:20:19,669 Well, that was our original sequence for any value of n. 216 00:20:19,669 --> 00:20:25,440 So the inverse d of t works. So, even though the spectrum is high-, 217 00:20:25,440 --> 00:20:29,552 looks highly undersampled. It turns out it's not. 218 00:20:29,552 --> 00:20:34,602 Even though we're missing all these values, we don't need it in order to add 219 00:20:34,602 --> 00:20:38,677 an inverse transform. So if you take a longer transform now, 220 00:20:38,677 --> 00:20:41,702 you start to see the details in the spectrum. 221 00:20:41,702 --> 00:20:47,037 And, this is one of the reasons why If you're interested in what the spectrum 222 00:20:47,037 --> 00:20:52,681 looks like, like looking at the spectrum of speech, you take longer transforms and 223 00:20:52,681 --> 00:20:57,894 then the length of that data you have. Like here I just doubled the length and 224 00:20:57,894 --> 00:21:04,843 it filled in the guise of the spectrum, at the halfway point, if you will. 225 00:21:04,843 --> 00:21:11,447 Notice that the frequency index now goes from 0 to 10 and that's because K equal 226 00:21:11,447 --> 00:21:15,742 to 20. So again, this corresponds to a At the 227 00:21:15,742 --> 00:21:20,654 frequency variable named hat and it repeats. 228 00:21:20,654 --> 00:21:28,643 And here, I just took any transform of length 64 and that really goes in the 229 00:21:28,643 --> 00:21:32,244 details. And if you're interested in that detail 230 00:21:32,244 --> 00:21:36,182 and seeing what the spectrum looks like, this is what you'd do. 231 00:21:36,182 --> 00:21:40,678 However you don't really need it if all you want to do, is to do some signal 232 00:21:40,678 --> 00:21:44,382 processing for example, hop/g into the frequency domain. 233 00:21:44,382 --> 00:21:51,725 do some things and come back. You can take shorter transforms, and 234 00:21:51,725 --> 00:21:57,047 there's no error. We can get, go back and forth with no 235 00:21:57,047 --> 00:21:58,616 problem. Okay. 236 00:21:58,616 --> 00:22:01,122 So, the DFT. We can now. 237 00:22:01,122 --> 00:22:06,272 Compute the sample spectrum of any discrete time signal, we don't need a 238 00:22:06,272 --> 00:22:10,512 formula for it. We can, now find the spectrum any way we 239 00:22:10,512 --> 00:22:13,347 want. and it's not a new transform. 240 00:22:13,347 --> 00:22:18,392 The DFT is not a new Fourier Transform, it's just a sampled version. 241 00:22:18,392 --> 00:22:22,351 With the DTFT, which in some sense is the true spectrum. 242 00:22:22,351 --> 00:22:27,836 Which is still we don't want to compute it for all those different frequencies. 243 00:22:27,836 --> 00:22:33,084 And it's often true that we padd to calculate the transform longer than the 244 00:22:33,084 --> 00:22:36,903 signal's duration. I'm showing you that You can really 245 00:22:36,903 --> 00:22:40,739 sample the spectrum more. Finally this'll get a better idea of 246 00:22:40,739 --> 00:22:44,142 what's going on. I've routinely did that for example in 247 00:22:44,142 --> 00:22:48,801 this spectrogram calculation that I'm going to show you in a later video, how I 248 00:22:48,801 --> 00:22:52,408 actually did that. But I, they're seeing something really 249 00:22:52,408 --> 00:22:56,552 important to realize and that is positive frequency values occur. 250 00:22:56,552 --> 00:23:04,611 When little k, the frequency index is in that range, and negative frequency occurs 251 00:23:04,611 --> 00:23:11,116 at the higher indexes. Turns out this is what the, DFT packages 252 00:23:11,116 --> 00:23:15,107 return. They will return the values over the 253 00:23:15,107 --> 00:23:20,828 entire range zero to capital K minus 1. Well this is the only part that makes any 254 00:23:20,828 --> 00:23:23,973 sense. This is negative frequency. 255 00:23:23,973 --> 00:23:29,432 We don't need to worry about that. That's positive frequency. 256 00:23:29,432 --> 00:23:34,325 So, negative frequencies over here. So when plotting, I'm always just 257 00:23:34,325 --> 00:23:38,987 chopping off the second half because this is really not needed. 258 00:23:38,987 --> 00:23:44,367 And if you'll note here there's a little bit of overlap here and that's because 259 00:23:44,367 --> 00:23:48,030 the value at a frequency f=1/2 is a little ambiguous. 260 00:23:48,030 --> 00:23:52,962 Is that positive or negative frequency? doesn't really matter. 261 00:23:52,962 --> 00:23:56,517 for lots of applications but they do overlap. 262 00:23:56,517 --> 00:24:01,562 So, succeeding videos we're going to find out how padding really pays off 263 00:24:01,562 --> 00:24:06,280 especially if you want efficient algorithms for computing the DFT.