0:00:00.650,0:00:03.830 In the preceding sub module, we saw conditions under which 0:00:03.830,0:00:07.620 a sequence actually has a finite-magnitude Fourier Transform, 0:00:07.620,0:00:10.530 namely, the sequence has to be absolutely summable. 0:00:10.530,0:00:12.249 We also saw that it can be extended 0:00:12.249,0:00:14.699 to square-summable sequences. 0:00:14.699,0:00:16.170 However in real life, 0:00:16.170,0:00:19.490 many sequences are neither absolutely nor square-summable. 0:00:19.490,0:00:22.769 For example, cosine of ω naught, times n 0:00:22.769,0:00:24.779 is an infinite-length sequence 0:00:24.779,0:00:27.380 that is neither absolutely nor square-summable. 0:00:27.380,0:00:31.380 Therefore it doesn't have, in the strict sense, a DTFT, 0:00:31.380,0:00:32.610 as we have seen before. 0:00:32.610,0:00:35.950 To be able to deal with sequences like this, 0:00:35.950,0:00:38.490 we need to introduce a new character in support.(?) 0:00:38.490,0:00:42.290 This is the δ function or δ distribution, 0:00:42.290,0:00:45.590 or also called the δ generalized function. 0:00:45.590,0:00:47.880 As you can see, this is a more subtle object 0:00:47.880,0:00:49.370 than what we are used too. 0:00:49.370,0:00:52.570 It's actually a function that this zero everywhere, 0:00:52.570,0:00:55.010 except at the origin where it's infinity. 0:00:55.010,0:00:56.350 Doesn't sound like a nice function, 0:00:56.350,0:00:59.270 but is actually is a very useful mathematical abstraction 0:00:59.270,0:01:02.530 and a very powerful object to have in the toolbox. 0:01:02.530,0:01:05.430 So we're going to introduce this δ function 0:01:05.430,0:01:08.720 and then, once we understand it intuitively, 0:01:08.720,0:01:10.500 we can use it to calculate, for example, 0:01:10.500,0:01:14.430 the DTFT of this cosine of ω naught times n 0:01:14.430,0:01:18.600 which will have the spectrum that contains Dirac δ's. 0:01:18.600,0:01:19.500 So the good news is that 0:01:19.500,0:01:23.850 now we have this subtle Dirac δ function that will allow us 0:01:23.850,0:01:26.780 to take Discrete Time Fourier Transforms 0:01:26.780,0:01:29.850 off a whole set of new functions and sequences 0:01:29.850,0:01:32.270 that we didn't know how to handle before, 0:01:32.270,0:01:33.609 and to look at their spectrum. 0:01:36.209,0:01:40.830 Module 4.6: Discrete Time Fourier Transform formalism. 0:01:40.830,0:01:43.659 The overview is simply that we are going to introduce 0:01:43.659,0:01:47.370 the Dirac δ functional, or generalized function. 0:01:47.370,0:01:53.130 And we can use this Dirac δ to study the spectras of sequences 0:01:53.130,0:01:57.020 for which we didn't know so far how to compute a DTFT. 0:01:57.020,0:01:58.920 We'll do this through a number of examples. 0:02:01.120,0:02:04.090 The tricky thing with the δ functional 0:02:04.090,0:02:06.909 is that we cannot describe the function itself, 0:02:06.909,0:02:09.420 we can only describe it indirectly, 0:02:09.420,0:02:11.999 through what's called the sifting property. 0:02:12.499,0:02:17.329 So for example here we have the integral between δ of t-s. 0:02:17.329,0:02:19.409 With the function f of t, 0:02:19.409,0:02:22.099 the result of the integral is that it takes out, 0:02:22.099,0:02:27.099 it weeds out (?) the value of f of t, at location s. 0:02:27.099,0:02:31.560 And this will be true for all functions -- or for all well-behaved functions -- 0:02:31.560,0:02:34.829 of t belonging to the set of real numbers. 0:02:37.329,0:02:40.579 The intuition for this Dirac δ function 0:02:40.579,0:02:45.260 is really through thinking about a family of functions. 0:02:45.260,0:02:48.560 We index them by k here, or k of t. 0:02:48.560,0:02:53.569 And k is a positive integer, t is a real number, 0:02:53.569,0:02:58.029 and the support of these functions is inversely proportional to k 0:02:58.029,0:02:59.569 and have a constant area. 0:02:59.569,0:03:02.309 We're going to specifically look at an example. 0:03:04.309,0:03:06.540 The example is the rect function. 0:03:06.540,0:03:08.219 We have seen this before. 0:03:08.219,0:03:10.349 It's a function that is piecewise constant. 0:03:10.349,0:03:14.329 It's zero inside an interval minus a half to one half 0:03:14.329,0:03:16.799 where it is actually equal to 1. 0:03:16.799,0:03:20.569 From the rect function, we can derive a localizing family, 0:03:20.569,0:03:24.969 r k of t, by simply scaling the rect function 0:03:24.969,0:03:27.620 both in its height and its width. 0:03:27.620,0:03:34.620 So it will be nonzero over an interval going from -1/2k to 1/2k. 0:03:35.279,0:03:38.799 So the support is of width 1/ k. 0:03:38.799,0:03:40.180 Since it's of height k, 0:03:40.180,0:03:44.000 the area is exactly equal to 1, independently of k. 0:03:47.000,0:03:52.230 So let's look at the few instantiations of this rect function, 0:03:52.230,0:03:55.180 scaled in height and in width. 0:03:55.180,0:03:56.919 So k is equal to 1, 0:03:56.919,0:03:58.430 k is equal to 5, 0:03:58.430,0:04:00.419 k is equal to 15, 0:04:00.419,0:04:02.099 k is equal to 40. 0:04:02.099,0:04:04.999 You can see it becomes higher and higher, obviously, 0:04:04.999,0:04:06.730 but it's narrower and narrower, 0:04:06.730,0:04:10.000 and its integral is always exactly equal to 1. 0:04:12.000,0:04:16.320 Now, let's see these localizing functions at work. 0:04:16.320,0:04:18.989 So remember, there are rk of t. 0:04:18.989,0:04:23.400 We take an integral of rk of t times f of t. 0:04:23.400,0:04:26.370 And this is equal to k times the integral 0:04:26.370,0:04:29.819 over an interval of length 1/k, 0:04:29.819,0:04:32.519 and the mean value theorem says that on this interval, 0:04:32.519,0:04:36.069 there is a value of f, namely f of γ, 0:04:36.069,0:04:38.590 there exists at least one value f of γ 0:04:38.590,0:04:41.009 which is equal to this integral. 0:04:41.009,0:04:42.520 And so, as k goes to infinity, 0:04:42.520,0:04:45.430 the interval becomes narrower and narrower, 0:04:45.430,0:04:49.449 and therefore, the limit of the integral is equal to f of 0. 0:04:49.449,0:04:54.190 Okay, so we have seen how taking the limit of the localizing functions, 0:04:54.190,0:04:58.110 extracts the value of f of t at the origin f0. 0:04:58.110,0:05:01.759 Now, in this case we have assumed that a function is continuous. 0:05:01.759,0:05:04.770 Otherwise, it's obviously more technical. 0:05:06.270,0:05:11.370 So, in the end, the Dirac δ functional is simply a shorthand, 0:05:11.370,0:05:14.300 instead of always writing the limiting process 0:05:14.300,0:05:19.150 -- so, for example, our integral on the previous page here, which is limit as k goes to infinity -- 0:05:19.150,0:05:25.860 we simply write the integral between δ of t minus s times f of t. 0:05:25.860,0:05:29.930 This integral is going to be equal to f of s, 0:05:29.930,0:05:32.490 as if we have taken the limit: 0:05:32.490,0:05:34.780 so it's a shorthand of this limiting process 0:05:34.780,0:05:36.650 that we have seen on the previous slide. 0:05:38.750,0:05:40.330 If we have one Dirac, 0:05:40.330,0:05:42.310 we can also look at a sequence of Dirac: 0:05:42.310,0:05:43.909 there is one, in particular, 0:05:43.909,0:05:46.210 that is used very often in signal processing. 0:05:46.210,0:05:49.580 It's δ of ω tilde. 0:05:49.580,0:05:53.900 This is equal to 2π times an infinite sum of Diracs, 0:05:53.900,0:05:56.190 located at multiples of 2π. 0:05:58.590,0:06:01.180 Let's look at the graphical representation. 0:06:01.180,0:06:06.030 So you have Diracs at zero, at plus minus 2π, 0:06:06.030,0:06:08.480 at plus minus 4π, etcetera. 0:06:10.880,0:06:14.509 Now this function, δ tilde of ω, 0:06:14.509,0:06:18.219 this sequence of Diracs, spaced 2πi apart, 0:06:18.219,0:06:19.699 is actually very useful. 0:06:19.699,0:06:21.650 So let's put it to good use. 0:06:21.650,0:06:26.229 So take the inverse DTFT of δ tilde. 0:06:26.229,0:06:30.030 So it's the integral over one period, minus π to π, 0:06:30.030,0:06:32.750 of δ tilde against (?) e to the j ω n. 0:06:32.750,0:06:36.409 This, of course, involves only a single Dirac at the origin, 0:06:36.409,0:06:40.740 because that's the only Dirac in the sequence that is inside the interval. 0:06:40.740,0:06:44.909 This is equal to the evaluation of e to the jωn: 0:06:44.909,0:06:49.270 at ω = 0, this is exactly equal to 1. 0:06:49.270,0:06:53.169 Therefore the inverse DTFT of δ tilde 0:06:53.169,0:06:56.879 is equal to the sequence x(n)O is equal to 1. 0:06:56.879,0:06:58.249 But that's a miracle because we didn't know 0:06:58.249,0:07:00.259 how to take the forward DTFT 0:07:00.259,0:07:04.159 of the constant signal x(n) is equal to 1, 0:07:04.159,0:07:06.100 so now we actually know what it is. 0:07:08.489,0:07:09.900 In conclusion, 0:07:09.900,0:07:14.699 the Discrete Time Fourier Transform of the constant sequence 0:07:14.699,0:07:17.389 is δ tilde of ω, 0:07:17.389,0:07:21.459 the sequence of Diracs spaced 2π apart. 0:07:23.259,0:07:25.520 Now this looks like we played a trick on you 0:07:25.520,0:07:28.120 because we started with a constant sequence, 0:07:28.120,0:07:30.499 we looked at the DTFT, 0:07:30.499,0:07:32.939 and we were confused what the result would be. 0:07:32.939,0:07:34.639 So let us do a sanity check. 0:07:34.639,0:07:38.449 Let's just calculate the partial sums of the DTFT. 0:07:38.449,0:07:43.719 So sk of ω is the sum between minus k and k, of e to the -jωn. 0:07:46.219,0:07:49.919 We plot the magnitude of sk of ω 0:07:49.919,0:07:51.499 for k is equal to 5, 0:07:51.499,0:07:57.749 k is equal to 10, 15, 30, 40, 0:07:57.749,0:08:00.400 and we start to see a Dirac emerging: 0:08:00.400,0:08:02.360 one spike at the origin. 0:08:04.200,0:08:09.230 The partial sum DTFT looks like a family of localizing functions. 0:08:09.230,0:08:16.430 So sk of ω will, as k grows, converge to δ tilde of ω. 0:08:18.810,0:08:21.529 Now we can do the exact same exercise 0:08:21.529,0:08:25.659 on δ tilde of ω minus ω naught 0:08:25.659,0:08:27.710 by the same argument as before. 0:08:27.710,0:08:32.360 We will sift out the Dirac that is inside the interval, minus π to π. 0:08:32.360,0:08:35.480 And this one will lead to a complex exponential, 0:08:35.480,0:08:37.580 e to the jω naught times n. 0:08:38.280,0:08:41.160 From this, we have DTFT pairs. 0:08:41.160,0:08:45.010 The DTFT of 1 is, as we have seen, δ tilde of ω, 0:08:45.010,0:08:48.260 the DTFT of e to the jω naught times n 0:08:48.260,0:08:52.420 is equal to δ tilde, ω minus ω naught. 0:08:52.420,0:08:56.510 More interestingly is the DTFT of cos ω naught times n: 0:08:56.510,0:09:00.380 Well, using Euler's formulas, we know that the cosine 0:09:00.380,0:09:02.710 is a combination of 2 complex exponential. 0:09:02.710,0:09:05.100 Each one will generate a δ tilde, 0:09:05.100,0:09:07.480 one shifted to ω naught, 0:09:07.480,0:09:10.180 the other one shifted to minus ω naught. 0:09:10.180,0:09:13.910 Finally, the DTFT of sine ω naught n 0:09:13.910,0:09:16.140 is equal to something very similar, 0:09:16.140,0:09:19.780 there is a scaling factor and multiplication by minus j 0:09:19.780,0:09:21.930 and then two δ tildes again 0:09:21.930,0:09:24.490 shifted to ω naught and minus ω naught. 0:09:26.300,0:09:29.410 It is time to summarize, and to see the parallels 0:09:29.410,0:09:33.430 between the DFT, which acts on CN, 0:09:33.430,0:09:36.630 and the DTFT that acts on C infinity. 0:09:36.630,0:09:38.080 Please note before starting 0:09:38.080,0:09:42.510 that the δ over sequences has square brackets, 0:09:42.510,0:09:43.930 as we have seen. 0:09:43.930,0:09:47.760 And the δ over the real line has round brackets. 0:09:47.760,0:09:49.390 So these are very different elements. 0:09:49.390,0:09:52.360 δ in discrete time is a very simple sequence 0:09:52.360,0:09:54.250 with a single nonzero element, 0:09:54.250,0:09:58.520 δ over the continuous line is a distribution 0:09:58.520,0:10:00.200 or a generalized function: 0:10:00.200,0:10:03.090 as we have seen, it's a Dirac δ function. 0:10:03.090,0:10:04.540 With this preliminaries, 0:10:04.540,0:10:07.920 let's look now at the left side, and properties on C N. 0:10:07.920,0:10:12.300 So we had verified that complex exponential, of length N, 0:10:12.300,0:10:15.880 with frequencies that are multiples of 2π/N, 0:10:15.880,0:10:17.270 are orthogonal to each other: 0:10:17.270,0:10:18.950 that's formula A, 0:10:18.950,0:10:24.060 this is written as also DFT of the complex exponential 0:10:24.060,0:10:26.400 of a frequency 2π/N times h, 0:10:26.400,0:10:32.400 gives a transform that is equal to N times a δ at the location h. 0:10:32.400,0:10:36.940 The inverse discrete Fourier transform of a δ at location h 0:10:36.940,0:10:43.470 is equal to a complex exponential at frequency 2π/n times h. 0:10:43.470,0:10:46.530 And this is written under d as explicitly 0:10:46.530,0:10:50.740 as a summation of the δ with respect to the complex exponential. 0:10:50.740,0:10:51.410 Same result 0:10:52.260,0:10:55.700 Now let's more to the right hand side. 0:10:55.700,0:11:00.000 There the inversion formula we have seen of Dirac tilde 0:11:00.000,0:11:02.080 which is a sequence of Diracs, 0:11:02.080,0:11:04.170 is integral over one period 0:11:04.170,0:11:06.800 and if the Dirac sequence is shifted to σ, 0:11:06.800,0:11:11.650 it will generate a complex exponential e to the jσn. 0:11:11.650,0:11:17.100 So that's under C', it's the IDTFT of δ tilde. 0:11:17.100,0:11:23.160 Then under B', the DTFT of e to the jσn 0:11:23.160,0:11:26.390 is δ tilde shifted by σ, 0:11:26.390,0:11:27.820 and this leads to A', 0:11:27.820,0:11:30.640 where we simply write that the inner product 0:11:30.640,0:11:34.700 -- so that's the expression the DTFT between two complex exponentials -- 0:11:34.700,0:11:38.300 leads to δ tilde shifted to σ. 0:11:39.100,0:11:43.770 So now we see these formal parallels between these two transforms: 0:11:43.770,0:11:46.640 one on CN as a DFT, which is very simple, 0:11:46.640,0:11:49.680 it's elementary linear algebra, 0:11:49.680,0:11:52.220 and the other one, the DTFT 0:11:52.220,0:11:55.830 which acts on infinite sequences, which is more subtle, 0:11:55.830,0:11:58.450 and which leads, in the cases we have seen here, 0:11:58.450,0:12:01.620 to generalized functions (?), sequences of Diracs. 0:12:01.620,0:12:06.330 Yet they act very similarly: the same intuitions about frequencies, 0:12:06.330,0:12:11.040 about complex exponentials, about Diracs appear in both cases. 0:12:11.040,0:12:13.400 And that's really the message we want to convey here. 0:12:15.500,0:12:17.210 Let us now conclude. 0:12:17.210,0:12:19.830 The final result we have seen shows 0:12:19.830,0:12:25.580 a formal orthogonality of the "basis" of e to the jωn, 0:12:25.580,0:12:29.020 the sequence of infinite-length complex exponentials. 0:12:29.020,0:12:32.470 So if you're careful enough, everything works just nice. 0:12:32.470,0:12:36.850 But remember the δ notation presumes that you took a limiting operation. 0:12:36.850,0:12:40.980 And it's just a lazy shorthand to express something 0:12:40.980,0:12:44.470 that always implies a limit. A δ in the spectrum, 0:12:44.470,0:12:49.600 so if we have an x of e to the jω, and there is a δ function there, 0:12:49.600,0:12:52.450 indicates that the signal has infinite energy, 0:12:52.450,0:12:57.200 So we are not within our comfortable Hilbert space framework of l2 of Z. 0:12:57.200,0:13:00.010 But the δ notation proves to be very useful 0:13:00.010,0:13:02.200 in derivation of certain results, 0:13:02.200,0:13:03.920 for example, the modulation theorems 0:13:03.920,0:13:06.560 that we are going to see later in this module. 0:13:06.560,0:13:08.250 Yet, there is a word of care. 0:13:08.250,0:13:09.870 As a friend of mine says, 0:13:09.870,0:13:14.490 when you use δ's it's like walking on the edge of a precipice. 0:13:14.490,0:13:17.290 If you put the foot on the wrong side 0:13:17.290,0:13:18.890 you might actually die. 0:13:18.890,0:13:21.130 With this word of caution, let's move on.