1 00:00:00,012 --> 00:00:05,278 In this video, we're going to define the Fourier Transform for digital signals. 2 00:00:05,278 --> 00:00:10,104 It's known by the complicated name of a discrete-time Fourier Transform. 3 00:00:10,104 --> 00:00:13,689 it's so long-winded, everybody calls it the DTFT. 4 00:00:13,689 --> 00:00:18,857 We're going to see that it looks very similar to what we've already encountered 5 00:00:18,857 --> 00:00:21,952 and we're going to talk about its properties. 6 00:00:21,952 --> 00:00:28,039 Many of which are shared with the Fourier Transform we've already defined for 7 00:00:28,039 --> 00:00:32,144 analog signals. So this is a fairly easy leap to go into 8 00:00:32,144 --> 00:00:37,189 the discreet time world. So, let's define it and like I said the 9 00:00:37,189 --> 00:00:42,939 definition looks very similar What we have for analog signals. 10 00:00:42,939 --> 00:00:48,045 the big difference is, like I keep saying, is. 11 00:00:48,045 --> 00:00:52,637 That it's a function of f, which has no units. 12 00:00:52,637 --> 00:00:58,730 And f is in the range minus a half to a half or zero to one. 13 00:00:58,730 --> 00:01:03,958 is the case may be we'll figure this out a little bit later. 14 00:01:03,958 --> 00:01:09,407 You want to point out the notational change this is written, the DTFT is 15 00:01:09,407 --> 00:01:15,594 written as S(e^jt2pif) the variable is f but this helps us distinguish it from the 16 00:01:15,594 --> 00:01:22,294 Fourier Transform of an analog c So, this is the notation we're going to use for 17 00:01:22,294 --> 00:01:29,245 the DTFT, and when I, when you see a s(f), you'll know that means an analog 18 00:01:29,245 --> 00:01:34,364 Fourier Transform. And f in that case has units of hertz. 19 00:01:34,364 --> 00:01:39,942 Okay, so again the all spectra are periodic with period 1. 20 00:01:39,942 --> 00:01:44,754 And as we know, that comes from the fact that this is periodic. 21 00:01:44,754 --> 00:01:50,586 with a period of 1 as a function of f so it has to be periodic and I'm going to 22 00:01:50,586 --> 00:01:54,167 show you an example to show you how that works. 23 00:01:54,167 --> 00:01:59,432 So, here's a little simple example. It's a exponential signal. 24 00:01:59,432 --> 00:02:06,257 And let's plot it, so we understand it. So, a^n u(n). 25 00:02:06,257 --> 00:02:12,082 Okay, the first thing to note is that the unit 26 00:02:12,082 --> 00:02:20,152 step multiplies the a^n. So unit step, you recall Use 0 for the 27 00:02:20,152 --> 00:02:25,289 negative and it's 1 for n = 0 and positive. 28 00:02:25,289 --> 00:02:34,176 And that's going to the part that's back here for -n is going to set to 0 the 29 00:02:34,176 --> 00:02:42,513 exponential, so the only thing we get Is the exponential for positive, index 30 00:02:42,513 --> 00:02:45,159 values. Positive time values. 31 00:02:45,159 --> 00:02:51,803 And it may look something like that. If A is bigger than 1 this thing could 32 00:02:51,803 --> 00:02:54,933 take off. It's still 1 at the origin. 33 00:02:54,933 --> 00:02:59,622 But it could very big very quickly if A is bigger than 1. 34 00:02:59,622 --> 00:03:07,901 So, what I have done here is some example here with a [UNKNOWN]. 35 00:03:07,901 --> 00:03:18,485 Ok, well let's compute spectrum and way that proceeds the best referred I am just 36 00:03:18,485 --> 00:03:23,153 going to Plug in for s and I'll plug in what my signal is. 37 00:03:23,153 --> 00:03:26,758 There it is. And, again what the unit step does is 38 00:03:26,758 --> 00:03:32,292 that it sets to zero anything for n negative so I can change the limits of 39 00:03:32,292 --> 00:03:37,908 the sum and therefore get rid of the u(n) and get a much simpler for where I can 40 00:03:37,908 --> 00:03:43,020 play with. And I'd like to point out that the 41 00:03:43,020 --> 00:03:52,279 complex exponential here can be thought of as e to the minus j, 2pi f, all raised 42 00:03:52,279 --> 00:03:58,162 to the nth. And that means, I can merge those 2. 43 00:03:58,162 --> 00:04:04,030 Exponential's in the formula.This is going to be the key step for getting a 44 00:04:04,030 --> 00:04:09,720 analytic expression from the spectrum. So here's what I did same thing. 45 00:04:09,720 --> 00:04:16,375 And now we have to recall the geometric series, very important in digital signal 46 00:04:16,375 --> 00:04:23,017 processing to know this property. You sum up a exponential in alpha, in 47 00:04:23,017 --> 00:04:28,982 zero to infinity. As long as the absolute value of alpha. 48 00:04:28,982 --> 00:04:37,327 The magnitude of alpha is less than 1. It's hidden by this very concise formula. 49 00:04:37,327 --> 00:04:43,446 So I'm going to use that formula. Because that's exactly what I have here. 50 00:04:43,446 --> 00:04:47,571 And this formula works, even if the alpha is complex valued. 51 00:04:47,571 --> 00:04:53,088 The only thing that matters is that its magnitude is be, is less than 1. 52 00:04:53,088 --> 00:04:58,250 Which it certainly is, in this case. If I assume that the absolute value of A 53 00:04:58,250 --> 00:05:00,292 is less than 1. Alright. 54 00:05:00,292 --> 00:05:04,662 So we can use it. Very simple formula pops up. 55 00:05:04,662 --> 00:05:09,167 There it is. And so, that is the spectrum of the 56 00:05:09,167 --> 00:05:13,537 exponential, signal. let's plot it. 57 00:05:13,537 --> 00:05:18,512 And for a specific value of a, which we have a half. 58 00:05:18,512 --> 00:05:26,700 And here you see the periodic, nature of it, you can go between -1/2 and 1/2 or 0 59 00:05:26,700 --> 00:05:33,445 to 1, whichever you want. I want to, show you how I plotted those 60 00:05:33,445 --> 00:05:40,885 curves for the magnitude and phase. you'll notice I didn't actually give you 61 00:05:40,885 --> 00:05:44,400 a formula for the magnitude and the phase. 62 00:05:44,400 --> 00:05:51,217 it turns out that for, discreet time spectra, those expressions can be fairly 63 00:05:51,217 --> 00:05:55,509 unwieldy. So, just recall here's what the transfer 64 00:05:55,509 --> 00:06:03,472 function was for our example. The exponential signal. 65 00:06:03,472 --> 00:06:17,932 And what I want to show you, is that by, in using modern tools, like MATLAB Our 66 00:06:17,932 --> 00:06:21,982 octave. It turns out you can basically type this 67 00:06:21,982 --> 00:06:27,437 expression in as it stands. And get all the information about the 68 00:06:27,437 --> 00:06:32,847 magnitude and phase that you want. So, let's see how that works. 69 00:06:32,847 --> 00:06:36,422 So here, I have the MATLAB command window. 70 00:06:36,422 --> 00:06:42,251 And I'm going to type in. [SOUND] A range of frequencies going 71 00:06:42,251 --> 00:06:47,548 between minus 2 and 2. that's sort of what was shown in the 72 00:06:47,548 --> 00:06:53,241 previous figure. And I'm going to say that A is a half, 73 00:06:53,241 --> 00:06:58,620 which is what we had. And I'm going to type in the formula for 74 00:06:58,620 --> 00:07:04,531 h. [SOUND] And you notice I'm literally 75 00:07:04,531 --> 00:07:14,451 typing it in [SOUND] J and all. Turns out the default in MATLAB and 76 00:07:14,451 --> 00:07:22,572 Octave is that J is equal to the square root of minus 1. 77 00:07:22,572 --> 00:07:29,420 And the only, and the only thing that's interesting here is, notice the dot 78 00:07:29,420 --> 00:07:33,647 slash. What that means is term by term divide. 79 00:07:33,647 --> 00:07:38,662 Because f is a vector. And the exponential here of the, 80 00:07:38,662 --> 00:07:42,994 of an expression containing an f, is also a vector. 81 00:07:42,994 --> 00:07:49,204 And so, when you want turn by turn division, which is exactly what I want, 82 00:07:49,204 --> 00:07:54,425 this is the expression you'll want. You'll want to put that in. 83 00:07:54,425 --> 00:07:56,086 Okay. That's that. 84 00:07:56,086 --> 00:08:01,962 I'm going to create a subplot, it's called, in my plot window here. 85 00:08:01,962 --> 00:08:06,355 And, I'm just going to plot it. Plot f. 86 00:08:06,355 --> 00:08:16,035 Now, we want to plot the magnitude and in MATLAB an octave it's ab, abs function 87 00:08:16,035 --> 00:08:20,520 for absolute value. And there it is. 88 00:08:20,520 --> 00:08:28,442 Turn on the grid. So, the [UNKNOWN] range is between -1/2 89 00:08:28,442 --> 00:08:37,777 and 1/2 that's the range of which the frequencies are really an interest, the 90 00:08:37,777 --> 00:08:45,282 rest is periodic so you can get the Everything else is a periodic repetition 91 00:08:45,282 --> 00:08:51,187 just like we've been talking about. So that's negative frequency, that's 92 00:08:51,187 --> 00:08:55,757 positive frequency, negative, positive, negative etc. 93 00:08:55,757 --> 00:09:01,827 Notice how easy it was to apply, just type in the expression for the spectrum 94 00:09:01,827 --> 00:09:04,558 and there it is. Alright, 95 00:09:04,558 --> 00:09:14,219 so now I'm going to do the angle. [SOUND] [INAUDIBLE] plot, 96 00:09:14,219 --> 00:09:20,080 and I'm going to go back and change that to angle. 97 00:09:20,080 --> 00:09:26,863 That's the function you want. Now, it turns out, this is going to 98 00:09:26,863 --> 00:09:33,827 return an angle in radians, and I'm not you, but I find degrees a little bit 99 00:09:33,827 --> 00:09:41,018 easier to understand, so the way to do that is multiply your angle by 180/pi. 100 00:09:41,018 --> 00:09:47,559 And also, I should point out that [INAUDIBLE] octave know what pi is, too. 101 00:09:47,559 --> 00:09:53,741 That's a predefined variable. I didn't have to define, to very many 102 00:09:53,741 --> 00:09:57,052 digits. And there's the [INAUDIBLE]. 103 00:09:57,052 --> 00:10:01,722 turn on the grid abd now we can see that the 104 00:10:01,722 --> 00:10:06,498 angle never really gets beyond about 30 degrees. 105 00:10:06,498 --> 00:10:12,842 That's kind of interesting. you can prove that the phase at the 106 00:10:12,842 --> 00:10:17,496 origin, 0 frequency, is either going to be 0 or pi. 107 00:10:17,496 --> 00:10:23,863 It has to be real valued, and that's going to be the same at a half. 108 00:10:23,863 --> 00:10:33,669 Now, the the half may seems a little odd, until you realize what the complex 109 00:10:33,669 --> 00:10:40,041 exponential is? So, if you look at e to the minus j(2pif) 110 00:10:40,041 --> 00:10:46,977 and then evaluated at f equal a half. And you've already done that, 111 00:10:46,977 --> 00:10:53,077 that's minus 1 to the n. So when you calculate your spectrum, your 112 00:10:53,077 --> 00:10:58,642 DTFT at that frequency. It only contains real numbers. 113 00:10:58,642 --> 00:11:03,362 So again, the phase has to be either zero or pi. 114 00:11:03,362 --> 00:11:09,646 And so phase tends to have this rather complicated appearance to it. 115 00:11:09,646 --> 00:11:16,309 But also, we need to point out that the phase is odd and the magnitude is even, 116 00:11:16,309 --> 00:11:22,636 just like they should be and both are periodic because these are the J(2pi) of 117 00:11:22,636 --> 00:11:26,836 n's. But the real point of this segment is. 118 00:11:26,836 --> 00:11:33,969 How easy it is to plot very complicated transfer functions, once you have a 119 00:11:33,969 --> 00:11:40,666 formula for the, transfer function or the spectrum that you want. 120 00:11:40,666 --> 00:11:44,722 Okay, what's the inverse DTFT? Well, we are 121 00:11:44,722 --> 00:11:50,687 going to use under the [UNKNOWN] relationship that we used long time ago 122 00:11:50,687 --> 00:11:57,404 for [UNKNOWN] series and we show that the [UNKNOWN] for two different industries 123 00:11:57,404 --> 00:12:03,730 here was equal to this expression. [UNKNOWN] we can write as a uni Much more 124 00:12:03,730 --> 00:12:10,203 concisely than writing it like that. You know, a same kind of thing follows. 125 00:12:10,203 --> 00:12:16,651 We are going to multiply, our expression for the spectrum by the complex 126 00:12:16,651 --> 00:12:21,943 exponential integrate. And that will give us back our signal. 127 00:12:21,943 --> 00:12:27,932 So, driving the inverse. DTFT is very easy and again just like we 128 00:12:27,932 --> 00:12:33,975 had for analog signals, we can go back and find the time domain and the 129 00:12:33,975 --> 00:12:40,983 frequency domain, using these formulas. We go from time domain to the frequency 130 00:12:40,983 --> 00:12:47,332 domain using the DTFT and the inverse that So, just like we had before, we can 131 00:12:47,332 --> 00:12:52,027 think about a signal either way depending on the application. 132 00:12:52,027 --> 00:12:56,067 So, let's explore some of the properties of the DTFT. 133 00:12:56,067 --> 00:13:01,907 None of these should be terribly surprising of course, the DTFT is linear 134 00:13:01,907 --> 00:13:09,258 because it's just a A sum of terms, you can sum, a sum this way, or do it 135 00:13:09,258 --> 00:13:15,151 directly. So, it's linear, very important property 136 00:13:15,151 --> 00:13:23,524 it has conjugate symmetry, which is easy to show, so it negative frequency's the 137 00:13:23,524 --> 00:13:27,662 same Hence, the conjugated positive frequencies. 138 00:13:27,662 --> 00:13:32,977 And they also show through the properties of the complex exponential. 139 00:13:32,977 --> 00:13:39,217 Because it's periodic with period 1, it's also, what's at negative frequency also 140 00:13:39,217 --> 00:13:43,392 occurs at 1-f. So, the old time delay formula still 141 00:13:43,392 --> 00:13:48,323 works if you delay. A signal by, n zero, values. 142 00:13:48,323 --> 00:13:55,067 And in-, indices samples, if you will. That's the same as multiplying the 143 00:13:55,067 --> 00:14:00,101 spectrum by a complex exponential, having it delayed. 144 00:14:00,101 --> 00:14:06,552 But there, and the other way around, if you multiply by a complex, 145 00:14:06,552 --> 00:14:12,776 Exponential in the time domain is the same as shifting the spectrum in the 146 00:14:12,776 --> 00:14:18,602 frequency domain by the frequency [UNKNOWN] of the complex modulation. 147 00:14:18,602 --> 00:14:23,791 And of course our old friend Parseval's theorems still applies. 148 00:14:23,791 --> 00:14:29,479 Now in a computer, um,the power in the signal is not That role, not that 149 00:14:29,479 --> 00:14:33,148 important. So, this is definitely an abstraction 150 00:14:33,148 --> 00:14:37,541 about calling that a power, but what else we want to call it. 151 00:14:37,541 --> 00:14:42,968 And of course you can find it in the frequency domain or in the time domain, 152 00:14:42,968 --> 00:14:46,423 whichever is easier using Parseval's Theorem. 153 00:14:46,423 --> 00:14:52,982 The proof of this is just like it was Of all of the previous examples we've gone 154 00:14:52,982 --> 00:14:56,598 through. So, the DTFT shares many of the 155 00:14:56,598 --> 00:15:04,140 properties of the Fourier Transform we've already encountered for analog signals. 156 00:15:04,140 --> 00:15:11,612 It's very important to note all spectra are periodic and the reason for that is 157 00:15:11,612 --> 00:15:14,872 Just because of the way the math works out. 158 00:15:14,872 --> 00:15:20,285 Tthat's one way of looking at it. And because it has to be periodic, the 159 00:15:20,285 --> 00:15:25,942 highest possible frequency it can have in the Discrete-Time world is 1/2. 160 00:15:25,942 --> 00:15:31,022 There is no higher frequency in math because it has to be periodic. 161 00:15:31,022 --> 00:15:35,786 We'll get used to that. Now What we've talked about with the DTFT 162 00:15:35,786 --> 00:15:39,242 is how to, compute it. We've defined it, 163 00:15:39,242 --> 00:15:44,648 Remember back when we talked about signals? There are some signals for which 164 00:15:44,648 --> 00:15:47,979 there are no formulas. In particular, speech. 165 00:15:47,979 --> 00:15:53,442 How in the world did I show you that speech spectrogram several videos ago? 166 00:15:53,442 --> 00:15:59,337 How do they do it, I don't have a formula so it's going to be a little difficult to 167 00:15:59,337 --> 00:16:04,597 compute this directly and how we do that is the subject of the next video.