1 00:00:00,350 --> 00:00:04,090 Hi and welcome to module 4.4 of digital signal processing. 2 00:00:04,090 --> 00:00:08,040 In this module we will explore how Fourier analysis applies to 3 00:00:08,040 --> 00:00:11,890 the three different classes of signals that we introduced in our course. 4 00:00:11,890 --> 00:00:17,240 Namely finite line signals, periodic signals and infinite signals. 5 00:00:17,240 --> 00:00:19,610 We have already looked in detail at the case of finite 6 00:00:19,610 --> 00:00:24,060 length signals where the DFT is the Fourier tool of course. 7 00:00:24,060 --> 00:00:25,540 We have also shown in passing 8 00:00:25,540 --> 00:00:30,640 that for periodic signals the DFT extends naturally into the DFS. 9 00:00:30,640 --> 00:00:33,580 Which is a natural presentation for periodic sequences. 10 00:00:33,580 --> 00:00:36,825 And in the rest of the lecture today we will introduce, finally, 11 00:00:36,825 --> 00:00:40,723 the DTFT which is the Fourier tool of choice for infinite length sequences. 12 00:00:40,723 --> 00:00:44,820 And the rest of this module we will use the Karplus-Strong algorithm, which we 13 00:00:44,820 --> 00:00:50,885 first saw in module 2.3, to illustrate the key points of each different 14 00:00:50,885 --> 00:00:54,670 Fourier representation. Let's start with periodic sequences. 15 00:00:54,670 --> 00:00:57,330 An N-periodic sequence has only N degrees of 16 00:00:57,330 --> 00:00:59,990 freedom and the DFS captures the situation by 17 00:00:59,990 --> 00:01:03,070 providing us with a spectral representation for the 18 00:01:03,070 --> 00:01:07,310 sequence that only has N distinct Fourier coefficients. 19 00:01:07,310 --> 00:01:08,880 We can illustrate these points more in 20 00:01:08,880 --> 00:01:11,770 detail with the help of the Karplus-Strong algorithm. 21 00:01:11,770 --> 00:01:15,280 You remember how the Karplus-Stong curcuit works. 22 00:01:15,280 --> 00:01:16,360 You have an input, 23 00:01:16,360 --> 00:01:22,380 you have a delay line ff length big M, and matt generation factor alpha. 24 00:01:22,380 --> 00:01:26,000 As the samples go into the circuit they get pushed out 25 00:01:26,000 --> 00:01:29,470 to the output and they get pushed also to the delay line. 26 00:01:29,470 --> 00:01:33,310 They were stored here and output at the other end of the delay line after 27 00:01:33,310 --> 00:01:36,120 big M samples where they get accelerated by 28 00:01:36,120 --> 00:01:39,060 a factor alpha and summed to the current. 29 00:01:39,060 --> 00:01:41,460 If we were to describe this mathematically we would 30 00:01:41,460 --> 00:01:45,110 have what we call a difference equation that relates the current 31 00:01:45,110 --> 00:01:50,380 output to the past output that has gone through the delay line. 32 00:01:50,380 --> 00:01:53,251 So an output delayed by big M, scaled by 33 00:01:53,251 --> 00:01:57,590 the attenuation factor and summed to the original input. 34 00:01:57,590 --> 00:02:01,430 We can use this circuit to generate a simple periodics signal. 35 00:02:01,430 --> 00:02:06,870 And to do that we choose an input signal x that is non-zero only for n 36 00:02:06,870 --> 00:02:08,840 between zero and m. 37 00:02:08,840 --> 00:02:11,780 That means that x of n is actually a finance 38 00:02:11,780 --> 00:02:15,890 support sequence and that's why we use the over bar notation. 39 00:02:15,890 --> 00:02:21,680 You will only have big M non-zero samples and it will be zero everywhere else. 40 00:02:21,680 --> 00:02:26,110 Then we choose alpha equal to one so there will be no attenuation in the loop. 41 00:02:26,110 --> 00:02:29,000 If we input this signal to the Karplus-Strong circuit we 42 00:02:29,000 --> 00:02:32,400 will see that the output consists of a periodic signal where 43 00:02:32,400 --> 00:02:35,625 each period is constituted of the M 44 00:02:35,625 --> 00:02:39,330 non-zero samples of the input finite support signal. 45 00:02:39,330 --> 00:02:44,035 Suppose, for instance, that our finite support signal looks like this, has a 46 00:02:44,035 --> 00:02:51,550 non-zero support of 32 points, and over the support it looks like a straight line. 47 00:02:51,550 --> 00:02:53,250 And it's zero everywhere else. 48 00:02:53,250 --> 00:02:57,440 So if we use this as an input to the Karpus-Strong algorithm we will get a 49 00:02:57,440 --> 00:03:00,290 periodic repetition of this shape which, 50 00:03:00,290 --> 00:03:03,190 overall, will look like a saw-toothed wave. 51 00:03:03,190 --> 00:03:06,650 If we take the DFT of this signal, considered as a 52 00:03:06,650 --> 00:03:11,250 32 point finite length signal, the DFT will look like this. 53 00:03:11,250 --> 00:03:13,500 computing the exact value of the DFT 54 00:03:13,500 --> 00:03:16,500 coefficients is left as an exercise just note, 55 00:03:16,500 --> 00:03:19,425 for instance, that the coefficient of zero is 56 00:03:19,425 --> 00:03:22,725 zero because the signal is actually centered around 57 00:03:22,725 --> 00:03:25,040 zero so its average is zero. 58 00:03:25,040 --> 00:03:28,970 What happens, then, if we take the DFT of two periods? 59 00:03:28,970 --> 00:03:33,270 So we consider the first 64 points that come out 60 00:03:33,270 --> 00:03:37,110 of the Karplus-Strong algorithm and we take a DFT of this. 61 00:03:37,110 --> 00:03:41,860 Well, if we go through the math or even if we put this into a numerical package 62 00:03:41,860 --> 00:03:44,500 we will see that the shape of the DFT 63 00:03:44,500 --> 00:03:48,280 coefficient, the envelope so to speak, is the same 64 00:03:48,280 --> 00:03:52,010 as the one for just the first 32 points. 65 00:03:52,010 --> 00:03:57,840 However for every DFT coefficient there is an extra DFT coefficient with value zero. 66 00:03:57,840 --> 00:03:59,880 In other words, the DFT coefficients 67 00:03:59,880 --> 00:04:04,460 have been interleaved with zero valued coefficients. 68 00:04:04,460 --> 00:04:10,490 To get an intuition as to why it is so let's go back to the definition of DFT. 69 00:04:10,490 --> 00:04:13,280 Each DFT coefficient will be the inner product between 70 00:04:13,280 --> 00:04:15,830 the appropriate basis vector in the Fourier basis 71 00:04:15,830 --> 00:04:20,290 for c64 and this signal that we see here. 72 00:04:20,290 --> 00:04:23,800 So let's see graphically how this inner products are computed. 73 00:04:23,800 --> 00:04:25,400 Let's start with the first basis vector. 74 00:04:25,400 --> 00:04:29,510 We will show here in blue just the ideal shape of this basis factor. 75 00:04:29,510 --> 00:04:31,050 We don't really care about the real and 76 00:04:31,050 --> 00:04:34,200 imaginary part because we're just interested in the structure. 77 00:04:34,200 --> 00:04:38,700 The first factor is just the constant one and 78 00:04:38,700 --> 00:04:40,620 the result of the inter-product will be 79 00:04:40,620 --> 00:04:44,580 the non-normalized average of this signal in red. 80 00:04:44,580 --> 00:04:46,350 We know the average to be zero. 81 00:04:46,350 --> 00:04:49,800 The same holds for two periods, so the first coefficient is zero. 82 00:04:49,800 --> 00:04:52,590 For k equal to one we have the first basis vector and this 83 00:04:52,590 --> 00:04:57,630 will be a sinusoid that will spend a full period over 64 points. 84 00:04:57,630 --> 00:05:03,950 What that means is that the first 32 points will be multiplied by a shape that 85 00:05:03,950 --> 00:05:09,500 is exactly the inverse of the shape for the next 32 points. 86 00:05:09,500 --> 00:05:16,440 And so this sub sum of the inner product plus this will give zero. 87 00:05:16,440 --> 00:05:21,680 For k equal to two, on the other hand, the Fourier vector will span two periods over 88 00:05:21,680 --> 00:05:27,380 the space of 64 points and so here we simply have twice the same thing. 89 00:05:27,380 --> 00:05:29,270 This half of the inner product 90 00:05:29,270 --> 00:05:31,770 will be equal to the second half and the 91 00:05:31,770 --> 00:05:35,220 DFT coefficient will be twice the original DFT coefficient. 92 00:05:36,650 --> 00:05:38,330 For k equal to three we have another 93 00:05:38,330 --> 00:05:41,870 situation of anti-symmetry between the first part of 94 00:05:41,870 --> 00:05:44,270 the Fourier vector and the second part and 95 00:05:44,270 --> 00:05:46,550 so these two parts will cancel each other out. 96 00:05:46,550 --> 00:05:49,470 We can see that in general all odd index 97 00:05:49,470 --> 00:05:52,930 coefficients will be zero for this two period signal. 98 00:05:52,930 --> 00:05:54,430 So we can prove this for an arbitrary 99 00:05:54,430 --> 00:05:55,630 number of periods. 100 00:05:55,630 --> 00:05:58,990 Suppose y of n is a finite length signal that 101 00:05:58,990 --> 00:06:04,150 is composed of L repetitions of the same big M points. 102 00:06:04,150 --> 00:06:06,480 So we said that over bar x of n is a 103 00:06:06,480 --> 00:06:11,350 finite support signal that is zero everywhere except in a portion here. 104 00:06:11,350 --> 00:06:17,840 So we take this portion, this is M points, and we build y of n by putting 105 00:06:20,550 --> 00:06:25,020 L of these pieces together. So, this will be L of that. 106 00:06:26,180 --> 00:06:29,380 Before you transform of y of n is simply given by 107 00:06:29,380 --> 00:06:33,720 the sum for n that goes from zero to LM minus one. 108 00:06:33,720 --> 00:06:39,800 LM being the length of this signal now. Of y of n times E to the minus j two pi 109 00:06:39,800 --> 00:06:45,710 over LM times n times k. And k ranges from zero to 110 00:06:45,710 --> 00:06:47,040 LM minus one. 111 00:06:47,040 --> 00:06:49,070 So this is standard stuff, the only difference 112 00:06:49,070 --> 00:06:51,454 is that length of our signal is LM. 113 00:06:53,050 --> 00:06:58,570 We can split the sum in the following way, we have an outside sum where we span 114 00:06:58,570 --> 00:07:01,010 the number of periods and an inner sum 115 00:07:01,010 --> 00:07:02,920 where we go through the points in the period. 116 00:07:02,920 --> 00:07:09,650 And so here we simply replace k with n plus pm. 117 00:07:09,650 --> 00:07:10,760 So k was ranging 118 00:07:10,760 --> 00:07:16,230 over the entire signal now we split this into period plus index inside the period. 119 00:07:16,230 --> 00:07:18,880 We can do the same inside the complex exponential 120 00:07:18,880 --> 00:07:21,300 and so then we can split the complex exponential 121 00:07:21,300 --> 00:07:29,070 and we see that the inner sum is this one here and this term depends only on p. 122 00:07:29,070 --> 00:07:32,100 So we can bring it forward and have a product of 123 00:07:32,100 --> 00:07:36,200 two sums where we have this term here that ranges over 124 00:07:36,200 --> 00:07:39,990 the P index and this term here that ranges over the N index. 125 00:07:39,990 --> 00:07:41,186 And the two are independent. 126 00:07:42,310 --> 00:07:45,380 But now, this guy here we've seen before. 127 00:07:45,380 --> 00:07:50,530 This is exactly the same formula that we use to prove the orthogonality 128 00:07:50,530 --> 00:07:55,568 of the DFT basis. And so we know that this sum will be 129 00:07:55,568 --> 00:08:00,800 equal to big L if' k is a multiple of' L or zero otherwise. 130 00:08:00,800 --> 00:08:01,270 So with this 131 00:08:01,270 --> 00:08:05,252 knowledge we can plug this back into the formula for the Fourier Transform 132 00:08:05,252 --> 00:08:10,740 of' L periods and find out that the kth DFT coefficient will be equal 133 00:08:10,740 --> 00:08:15,420 to L times the original DFT coefficient that you could have computed for the 134 00:08:15,420 --> 00:08:23,513 finite support signal if K is a multiple of L and zero otherwise. 135 00:08:23,513 --> 00:08:26,730 So given the DFT of L periods 136 00:08:26,730 --> 00:08:31,180 you will have only one known zero DFT coefficient out of L 137 00:08:31,180 --> 00:08:35,120 and this will be equal to L times the original DFT coefficient. 138 00:08:35,120 --> 00:08:38,200 Well this was a long way to show that, once again, all the spectral 139 00:08:38,200 --> 00:08:43,670 information for a periodic signal is contained in the DFT of a single period. 140 00:08:43,670 --> 00:08:47,370 And that's why for periodic singal in the end we use a DFS. 141 00:08:47,370 --> 00:08:51,880 So the situation so far is the following. For N-point finite length signals we will 142 00:08:51,880 --> 00:08:53,350 use the DFT. 143 00:08:53,350 --> 00:08:56,750 For N-point periodic signals we will use the DFS. 144 00:08:58,000 --> 00:09:00,640 One category is missing and that is 145 00:09:00,640 --> 00:09:04,079 the category of infinite length, non-periodic signals. 146 00:09:05,990 --> 00:09:10,166 We can use the Karplus-Strong algorithm to generate one such signal 147 00:09:10,166 --> 00:09:13,675 simply by putting the gain factor alpha to less than one. 148 00:09:13,675 --> 00:09:17,304 In this case we will have an infinite length signal 149 00:09:17,304 --> 00:09:22,520 that is non-periodic because for every repetition of the m 150 00:09:22,520 --> 00:09:27,720 point sequence the gain factor will decrease. 151 00:09:27,720 --> 00:09:33,270 So the first period will be unaffected. The second period will be scaled by alpha. 152 00:09:33,270 --> 00:09:37,160 The third period will be scaled by alpha square and so on and so forth. 153 00:09:37,160 --> 00:09:39,600 So what is a good spectral representation for this signal? 154 00:09:41,630 --> 00:09:43,540 We can start with a DFT and we can see 155 00:09:43,540 --> 00:09:47,710 what happens when the length of the signal goes towards infinity. 156 00:09:47,710 --> 00:09:53,120 Intuitively, the fundamental frequency in cn, remember, the 157 00:09:53,120 --> 00:09:58,630 fundamental frequency of the Fourier basis in cn is omega equal to two pi over n. 158 00:09:58,630 --> 00:10:02,880 As n goes to infinity omega becomes smaller and smaller and 159 00:10:02,880 --> 00:10:06,940 the set of frequencies in the zero to pi range becomes 160 00:10:06,940 --> 00:10:08,660 denser and denser. 161 00:10:08,660 --> 00:10:14,040 In the limit the set of multiples of the fundamental frequency two pi over n will 162 00:10:14,040 --> 00:10:16,040 become so dense that we will try to 163 00:10:16,040 --> 00:10:19,910 replace this by a real valued variable omega. 164 00:10:19,910 --> 00:10:24,190 And this real valued variable will span the zero to pi interval. 165 00:10:24,190 --> 00:10:27,570 So if we replace that in the formulation for the DFT we get 166 00:10:27,570 --> 00:10:32,110 a sum now over all the points in the signal and instead of having 167 00:10:32,110 --> 00:10:34,980 multiples of the fundamental frequency we have a real variable. 168 00:10:34,980 --> 00:10:37,940 Does this make sense mathematically at least? 169 00:10:37,940 --> 00:10:43,590 So let's try and give a formal definition of what we call the Discrete-Time Fourier 170 00:10:43,590 --> 00:10:49,260 Transform, a Fourier transform geared at infinite length known periodic signals. 171 00:10:50,500 --> 00:10:56,050 We require that our infinite signal is square syllable. 172 00:10:56,050 --> 00:10:58,310 That means finite energy. 173 00:10:58,310 --> 00:11:02,490 It's a reasonable requirement to prevent summations from blowing up. 174 00:11:02,490 --> 00:11:07,269 We define now a function of a real valued variable omega, and remember 175 00:11:07,269 --> 00:11:11,886 this is a function not a sequence, and the summation goes like so: F 176 00:11:11,886 --> 00:11:15,612 of omega is the sum for n that goes from minus infinity to 177 00:11:15,612 --> 00:11:19,190 plus infinity of x of n times e to the minus j omega n. 178 00:11:21,330 --> 00:11:26,530 When this value exists we can actually invert it and retrieve 179 00:11:26,530 --> 00:11:30,530 our sequence values by taking the integral from minus pi to 180 00:11:30,530 --> 00:11:34,030 pi of F of omega e to the j omega n 181 00:11:34,030 --> 00:11:39,050 into omega and normalize in the integral by one over two pi. 182 00:11:39,050 --> 00:11:42,180 It's easy to verify that this is so. 183 00:11:42,180 --> 00:11:46,560 If you replace F omega inside here by this definition and invoke 184 00:11:46,560 --> 00:11:53,900 the fact that x of n is clear solvable. Now f of omega is two pi periodic. 185 00:11:53,900 --> 00:11:57,320 We can see that because it depends on e to the minus 186 00:11:57,320 --> 00:12:01,850 j omega n and this animal is two pi periodic in omega. 187 00:12:01,850 --> 00:12:06,880 To stress the periodicity of the DTFT, instead of writing f of omega 188 00:12:06,880 --> 00:12:11,720 for a sequence x of n, we will write the DTFT as x 189 00:12:11,720 --> 00:12:13,290 of e to the j omega. 190 00:12:13,290 --> 00:12:16,580 So, although the free variable is omega, we will write 191 00:12:16,580 --> 00:12:20,490 e to the j omega as the argument of the function. 192 00:12:20,490 --> 00:12:26,140 This will remind us that this is a Fourier transform and that it is two 193 00:12:26,140 --> 00:12:28,590 pi periodic no matter what happens because the 194 00:12:28,590 --> 00:12:31,050 argument of the function is two pi periodic. 195 00:12:31,050 --> 00:12:37,110 Another difference with respect to DFT is that for the DTFT we choose the 196 00:12:37,110 --> 00:12:42,410 minus pi pi interval as the representative interval for the transform. 197 00:12:42,410 --> 00:12:45,460 So these are conventions of a historic nature 198 00:12:45,460 --> 00:12:48,590 and although they're a little bit confusing it's 199 00:12:48,590 --> 00:12:52,470 particularly unfortunate, for instance, that the difference between 200 00:12:52,470 --> 00:12:57,060 DFT and DTFT is just a T here. 201 00:12:57,060 --> 00:13:02,200 We will preserve the nomenclature and the conventions in order to be compatible or 202 00:13:02,200 --> 00:13:06,060 congruent with the DSP literature out there. 203 00:13:06,060 --> 00:13:08,290 So let's look at an example of DTFT. 204 00:13:08,290 --> 00:13:10,745 Let's take a simple sequence, an exponentially 205 00:13:10,745 --> 00:13:13,170 decaying sequence, we know the sequence from the 206 00:13:13,170 --> 00:13:15,830 introduction of this class and we know that 207 00:13:15,830 --> 00:13:18,440 it is a no periodic infinite support sequence. 208 00:13:19,540 --> 00:13:22,180 When alpha is less than one we also know that 209 00:13:22,180 --> 00:13:26,820 this sequence has finite energy so we can compute the DTFT. 210 00:13:26,820 --> 00:13:28,030 We do that. 211 00:13:28,030 --> 00:13:29,790 So we write the formal definition. 212 00:13:29,790 --> 00:13:32,440 This is the sum from minus infinity to plus infinity of' 213 00:13:32,440 --> 00:13:35,800 x of' n times e to the minus j omega n. 214 00:13:35,800 --> 00:13:39,340 Here we use the values for the sequence. The sequence is one-sided. 215 00:13:39,340 --> 00:13:40,800 There's a unit step here. 216 00:13:40,800 --> 00:13:45,960 So that means that the index of the sum will start in zero and for n 217 00:13:45,960 --> 00:13:51,640 equal to zero or larger, the value of xn will be alpha to the power of n. 218 00:13:51,640 --> 00:13:53,110 We can collect the two powers under 219 00:13:53,110 --> 00:13:55,330 the same exponent and we can see that this is 220 00:13:55,330 --> 00:13:59,210 simply a geometric series with ratio alpha e to the minus 221 00:13:59,210 --> 00:14:01,948 j omega and so the result will be, in the end, 222 00:14:01,948 --> 00:14:05,300 one over one minus alpha e to the minus j omega. 223 00:14:07,340 --> 00:14:10,640 The magnitude of the Fourier transform is easy to compute. 224 00:14:10,640 --> 00:14:16,890 It will be one over one plus alpha square minus two times alpha cosine of omega. 225 00:14:16,890 --> 00:14:21,980 And when we plot this remember now the convention is that we're 226 00:14:21,980 --> 00:14:26,770 plotting frequencies from minus pi to pi rather than from zero to pi. 227 00:14:26,770 --> 00:14:31,110 So the positive frequencies will be on the right-hand side of the frequency axis. 228 00:14:31,110 --> 00:14:32,560 The negative frequencies, 229 00:14:32,560 --> 00:14:36,800 the one that turned clockwise, will be on the negative side of the frequency axis. 230 00:14:37,850 --> 00:14:41,350 The low frequencies will be now centered around zero and 231 00:14:41,350 --> 00:14:44,080 the high frequencies will be on the extremes of the bat. 232 00:14:45,610 --> 00:14:49,860 With this convention in mind we can look at the spectrum of the exponentially 233 00:14:49,860 --> 00:14:54,620 decaying sequence and look like this for say alpha equal to zero point nine. 234 00:14:54,620 --> 00:14:57,600 So it's a signal that contains energy 235 00:14:57,600 --> 00:15:00,410 in the frequency of the main mostly around the low 236 00:15:00,410 --> 00:15:04,390 frequencies, of course, because it moves rather slowly to zero. 237 00:15:06,020 --> 00:15:11,260 However, never forget the inherent periodicity of the Fourier transform. 238 00:15:11,260 --> 00:15:17,230 If we expand the frequency axis outside of the minus pi pi interval, and we can 239 00:15:17,230 --> 00:15:19,650 certainly do that because omega is a real 240 00:15:19,650 --> 00:15:23,030 valued variable, what we find is that the shape 241 00:15:23,030 --> 00:15:27,760 of the spectrum repeats outside with a periodicity of two pi. 242 00:15:27,760 --> 00:15:30,280 So the fundamental interval is this but as we 243 00:15:30,280 --> 00:15:34,250 plot outside we get further copies of the spectrum. 244 00:15:34,250 --> 00:15:38,700 Again, fundamental interval, first repetition, second repetition, and the 245 00:15:38,700 --> 00:15:41,690 positive axis and same thing on the other side. 246 00:15:42,770 --> 00:15:45,430 So let's go back to the Karplus-Strong algorithm. 247 00:15:45,430 --> 00:15:48,210 Try to generate a non-periodic infinite 248 00:15:48,210 --> 00:15:50,970 support signal and then compute its 249 00:15:50,970 --> 00:15:54,510 spectrum according to the new DTFT paradigm. 250 00:15:54,510 --> 00:15:58,985 So we start with the same shape as before for the initial data for this 251 00:15:58,985 --> 00:16:02,295 Karplus-Strong algorithm since we're going to be 252 00:16:02,295 --> 00:16:05,100 presice in the the derivation of the spectrum. 253 00:16:05,100 --> 00:16:08,500 It is useful at this point to look at the analytical formulation for 254 00:16:08,500 --> 00:16:13,502 this shape so x of n between zero and 31 is equal to 255 00:16:13,502 --> 00:16:19,993 two n divided by big M minus one minus one where big M in this case is 32. 256 00:16:23,100 --> 00:16:24,612 If we put in a decay factor 257 00:16:24,612 --> 00:16:27,852 in the Karplus-Strong algorithm equal to zero point 258 00:16:27,852 --> 00:16:30,660 nine you see that the repetitions generated by 259 00:16:30,660 --> 00:16:35,500 the Karplus-Strong algorithm have a exponentially decaying envelope. 260 00:16:35,500 --> 00:16:41,690 And can we can express the output as alpha to the power of the Flour of n divided by 261 00:16:41,690 --> 00:16:48,600 big M that multiplies the periodic signal obtained by putting 262 00:16:48,600 --> 00:16:50,310 copies of the pattern we saw in the 263 00:16:50,310 --> 00:16:53,350 previous picture one after the other and all of 264 00:16:53,350 --> 00:16:56,470 this is multiplied by the unistep because we assume 265 00:16:56,470 --> 00:16:59,514 that the signal starts at n equal to zero. 266 00:16:59,514 --> 00:17:02,968 So zero everywhere here and exponentially decaying 267 00:17:02,968 --> 00:17:06,775 saw tooth wave for N greater than zero. 268 00:17:06,775 --> 00:17:12,640 Analytically, the Fourier transform of this signal can be computed like so. 269 00:17:12,640 --> 00:17:13,940 Remember the definition. 270 00:17:13,940 --> 00:17:17,970 So y of e to the j omega, the DTFT of the 271 00:17:17,970 --> 00:17:21,520 signal we just showed in the picture, is equal to the sum for 272 00:17:21,520 --> 00:17:24,600 n that goes from minus infinity to plus infinity of the value 273 00:17:24,600 --> 00:17:28,220 of the signal in n times e to the minus j omega n. 274 00:17:29,360 --> 00:17:32,700 Just like we did before we split the sum into two parts. 275 00:17:32,700 --> 00:17:38,070 An outer sum that spans every quote unquote repetition of the basic shape. 276 00:17:38,070 --> 00:17:39,090 Although, of course the standard 277 00:17:39,090 --> 00:17:44,310 signal is not periodic, so each repetition will be scaled by a different factor. 278 00:17:44,310 --> 00:17:48,780 And an inner sum that goes inside each repetition. 279 00:17:48,780 --> 00:17:53,740 Inside each repetition we have the values for the basic pattern and alpha to 280 00:17:53,740 --> 00:17:56,900 the power of p an exponentially decreasing 281 00:17:56,900 --> 00:18:00,600 gain factor that creates the decaying envelope. 282 00:18:00,600 --> 00:18:04,170 We can split the exponent in the complex exponential 283 00:18:04,170 --> 00:18:08,300 again as p big M plus n and by doing so 284 00:18:08,300 --> 00:18:11,530 we can split the sum into the product of two sums. 285 00:18:11,530 --> 00:18:18,040 The first term is something that looks like a DTFT. 286 00:18:18,040 --> 00:18:21,020 Notice that the index is p and we add alpha to the 287 00:18:21,020 --> 00:18:25,840 power of p then multiplies e to the minus j omega big MP. 288 00:18:25,840 --> 00:18:29,640 So if it wasn't for the big M here this would be a discrete 289 00:18:29,640 --> 00:18:33,660 time for the transform of the sequence that starts at zero and goes 290 00:18:33,660 --> 00:18:38,770 to infinity and whose samples take the value offered to the power of p. 291 00:18:38,770 --> 00:18:42,590 Namely, this is the DTFT of an 292 00:18:42,590 --> 00:18:46,200 exponentially decaying sequence except for this factor here. 293 00:18:46,200 --> 00:18:48,392 We'll see how to take care of this in a second. 294 00:18:48,392 --> 00:18:51,500 The second factor is equal to the DTFT of 295 00:18:51,500 --> 00:18:54,925 a signal that is equal to the basic pattern from 296 00:18:54,925 --> 00:18:58,490 zero to big M minus one and zero everywhere else. 297 00:18:58,490 --> 00:19:02,350 So we can write this as the product of two DTFTs. 298 00:19:02,350 --> 00:19:04,228 The first one is the DTFT of 299 00:19:04,228 --> 00:19:07,540 the exponentially decaying sequence that we saw before. 300 00:19:07,540 --> 00:19:12,680 And the factor of M in the exponent propagates to the argument of the DTFT 301 00:19:12,680 --> 00:19:17,380 and simply means that we are contracting the frequency axis by a factor of M. 302 00:19:17,380 --> 00:19:19,890 It's just a re-scaling of the frequency axis. 303 00:19:19,890 --> 00:19:22,980 The second term we'll compute in just a second. 304 00:19:22,980 --> 00:19:25,210 So let's look back at what the 305 00:19:25,210 --> 00:19:29,450 Fourier transform of the exponential decay looks like. 306 00:19:29,450 --> 00:19:31,510 The fact that there is a factor of M in the 307 00:19:31,510 --> 00:19:35,910 exponent simply implies that there's a scaling of the frequency axis. 308 00:19:35,910 --> 00:19:39,780 So we're contracting the frequency axis by a factor of big M. 309 00:19:39,780 --> 00:19:42,220 But be careful because this contraction will 310 00:19:42,220 --> 00:19:45,360 actually have to take periodicity into account. 311 00:19:45,360 --> 00:19:50,020 So when big M is equal to one we have the standard spectrum of decaying exponential. 312 00:19:50,020 --> 00:19:53,080 When M is equal to two we're bringing in two 313 00:19:53,080 --> 00:19:57,220 copies of the spectrum inside the minus pi pi interval. 314 00:19:57,220 --> 00:20:02,610 So what before was periodic over two pi now becomes periodic over pi. 315 00:20:02,610 --> 00:20:06,340 And when M is equal to three you will have three copies of the basic 316 00:20:06,340 --> 00:20:10,710 spectrum that fall into the minus pi pi interval and so on and so forth. 317 00:20:10,710 --> 00:20:13,083 This is, for instance, the case for M equal to 12. 318 00:20:14,960 --> 00:20:17,800 Now onto the second term of the product. 319 00:20:19,050 --> 00:20:22,560 As we said, that was the DTFT of a finite support 320 00:20:22,560 --> 00:20:27,090 sequence that is linear between zero and big M minus one. 321 00:20:27,090 --> 00:20:32,330 The result is a little bit ugly and a little bit cumbersome to drive so we leave 322 00:20:32,330 --> 00:20:36,650 that as an exercise and we put some slides in the end of detail how to compute this. 323 00:20:36,650 --> 00:20:40,950 But fundamentally this is the result and if you plot the magnitude of this function 324 00:20:40,950 --> 00:20:45,230 you have something like this. In the figure you have the magnitude of 325 00:20:45,230 --> 00:20:51,750 the DTFT of the 32 point saw tooth period that we saw before. 326 00:20:51,750 --> 00:20:53,870 This is known zero between zero and 31. 327 00:20:53,870 --> 00:20:58,390 And indeed if you count the local maxima here there are 32 of them. 328 00:20:59,420 --> 00:21:02,590 Okay, to compute the final spectrum we have to multiply 329 00:21:02,590 --> 00:21:08,900 the first term which is, remember, 32 repetition of the 330 00:21:08,900 --> 00:21:14,960 basic spectrum of a decaying exponential times the spectrum we just computed. 331 00:21:14,960 --> 00:21:20,800 It turns out that these peaks in a of e to the j omega M align with local maxima of 332 00:21:20,800 --> 00:21:24,140 the spectrum of the first period so that the final 333 00:21:24,140 --> 00:21:27,750 result looks like this where the peaks of the first term 334 00:21:27,750 --> 00:21:32,190 in the product slim down the lobes of the second term. 335 00:21:33,300 --> 00:21:37,660 So here we have derived the DTFT, namely the spectrum 336 00:21:37,660 --> 00:21:42,460 of an infinite non-periodic signal that is not a trivial signal. 337 00:21:42,460 --> 00:21:48,020 Now so far we have treated the DTFT as a formal operator and in the next module 338 00:21:48,020 --> 00:21:53,240 we will see how the DTFT relates to the concept of change of basis 339 00:21:53,240 --> 00:21:54,760 in an appropriate Gilbert space.