1 00:00:00,012 --> 00:00:04,772 We have now encountered several version of the fully transformed four sequences 2 00:00:04,772 --> 00:00:09,690 finite lengths and infinite lengths. Namely the Discrete Fourier Transform for 3 00:00:09,690 --> 00:00:13,650 finite length sequences. So Discrete Fourier series for periodic 4 00:00:13,650 --> 00:00:17,668 infinite length sequences. And finally, the Discrete Time Fourier 5 00:00:17,668 --> 00:00:20,685 transform or DTFT for infinite length sequences. 6 00:00:20,685 --> 00:00:25,430 How do these various forms of the Fourier Transform interact with each other? 7 00:00:25,431 --> 00:00:30,210 So first we are going to look at how to compute the DTFT of a periodic sequence. 8 00:00:30,210 --> 00:00:32,852 That will involve the delta function again. 9 00:00:32,852 --> 00:00:36,962 And, we are also going to see how to compute the DTFT of a finite length 10 00:00:36,962 --> 00:00:41,037 sequence and how it relates to the DFT of a finite length sequence. 11 00:00:41,038 --> 00:00:45,787 At the end, where we look at a technique called zero padding, which is a way to 12 00:00:45,787 --> 00:00:50,362 interpolate the spectrum of a finite length signal using a DFT of a longer 13 00:00:50,362 --> 00:00:53,892 signal which has zero appended to the initial signal. 14 00:00:53,892 --> 00:00:59,211 So it's a technique that's very often used to displace spectra so it's important to 15 00:00:59,211 --> 00:01:03,902 understand how it functions. Module 4.7, relationships between 16 00:01:03,902 --> 00:01:07,453 transforms. We have seen the Discrete Fourier 17 00:01:07,453 --> 00:01:13,393 Transform, the Discrete Fourier Series, as well as the Discrete-time Fourier 18 00:01:13,393 --> 00:01:17,132 Transform. Now we are going to look at the DTFT of 19 00:01:17,132 --> 00:01:23,141 periodic sequences on the one hand and the DTFT of finite-support sequences. 20 00:01:23,141 --> 00:01:27,241 And create the relationship between these two cases. 21 00:01:27,241 --> 00:01:32,352 And the DFT or DFS. Finally, we will look at zero padding, 22 00:01:32,353 --> 00:01:39,096 techniques that is often used to smooth specra from finite length signals. 23 00:01:39,096 --> 00:01:44,846 The DFT and the DFS can be seen as changes of basis in c, capital N. 24 00:01:44,846 --> 00:01:50,196 It's obvious, because it's a matrix vector multiplication. 25 00:01:50,196 --> 00:01:54,234 And we go from the original domain to the DFT domain. 26 00:01:54,234 --> 00:02:00,306 The DTFT, on the other hand, we introduced as a, quote unquote, formal change of 27 00:02:00,306 --> 00:02:04,301 basis over l2 of z. Is a space of finite energy sequences. 28 00:02:04,301 --> 00:02:07,951 So, basis vectors are building blocks for any signal. 29 00:02:07,951 --> 00:02:12,501 So we can write the signal as a linear combination of basis vectors. 30 00:02:12,501 --> 00:02:17,897 In the case of the DTFTs, this is formal. Because the index for the DTFT, which is 31 00:02:17,897 --> 00:02:23,161 frequency omega, is uncountable. So we don't have a countable basis. 32 00:02:23,161 --> 00:02:28,315 Yet the intuition we have from the DFT or the DFS carries over in some sense to the 33 00:02:28,315 --> 00:02:31,571 DTFT as we have seen in the preceding sub-module. 34 00:02:31,571 --> 00:02:36,559 The DFT and the DTFT are really two sides of the same coin. 35 00:02:36,559 --> 00:02:41,633 The DFT leads to numerical algorithms. It's essentially linear algebra. 36 00:02:41,633 --> 00:02:45,835 And we can derive fast algorithms based on this formulation. 37 00:02:45,835 --> 00:02:51,127 The DTFT is more of a mathematical tool. It comes in handy when we want to make 38 00:02:51,127 --> 00:02:53,945 proofs. And to see properties of Fourier 39 00:02:53,945 --> 00:02:56,056 Transform. Transformed. 40 00:02:56,056 --> 00:03:02,446 If we are given finite length signal x n, which has, capital n non-zero entries. 41 00:03:02,446 --> 00:03:05,831 Say, for n goes from 0 to capital n minus 1. 42 00:03:05,831 --> 00:03:11,957 Then the natural spectral representation as we have seen is a DFT given by capital 43 00:03:11,957 --> 00:03:17,231 X of Okay, now there are two ways to embed x n into an infinite sequence. 44 00:03:17,231 --> 00:03:22,340 One is we can do a periodic extension so we take the index module capital N and 45 00:03:22,340 --> 00:03:27,524 that gives us x tilde of N which is simply the repetition where the period is of 46 00:03:27,524 --> 00:03:31,385 length capital N. Another way is it's finite support 47 00:03:31,385 --> 00:03:35,403 extension. So, we denote this by x over bar which is 48 00:03:35,403 --> 00:03:41,293 equal to xn on the interval 0 to capital N minus 1 and equal to 0 otherwise. 49 00:03:41,293 --> 00:03:46,879 How does xk, the DFT of the finite link signal relate to the DTFT of these two 50 00:03:46,879 --> 00:03:51,146 forms of signals. This is what we shall persue in the next 51 00:03:51,146 --> 00:03:55,161 few slides. So what is the DTFT of x tilde of n? 52 00:03:55,161 --> 00:04:02,015 Well, it's capital X tilde of e to the j omega which is a formal power series of x 53 00:04:02,015 --> 00:04:06,286 tilde of n multiplied by e to the minus j omega n. 54 00:04:06,286 --> 00:04:12,686 In this expression, we placed x tilde of n as the inverse Fourier series. 55 00:04:12,686 --> 00:04:17,954 Of capital X tilde, it's in the expression between parenthesis. 56 00:04:17,954 --> 00:04:24,692 This of course is equal to the inverse dft and we simply reorder the sums, so we take 57 00:04:24,692 --> 00:04:31,127 out the sum over k, in front, and we leave inside the parenthesis the sum over n, 58 00:04:31,127 --> 00:04:35,342 gathering the e to the j to the various power terms. 59 00:04:35,343 --> 00:04:44,290 Then we recall that this infinite sum, of e to the j 2 pi over N, n k times e to the 60 00:04:44,290 --> 00:04:49,037 j omega n. Is simply the DTFT of a complex 61 00:04:49,037 --> 00:04:55,726 exponential, of frequency 2 pi over capital N, times n k. 62 00:04:55,726 --> 00:05:03,839 And this we know, is going to be our Delta tilde signal shifted to the location 2 pi 63 00:05:03,839 --> 00:05:09,887 over capital N times k. With this we have now a formal expression 64 00:05:09,887 --> 00:05:17,081 for x tilde equals the omega namely it's 1 over n, the sum of the DFD coefficients 65 00:05:17,081 --> 00:05:24,275 capital Xk multiplied by delta tilde shifted to the frequency 2 pi over capital 66 00:05:24,275 --> 00:05:29,354 N x k. Let us look at an example and take a good 67 00:05:29,354 --> 00:05:38,612 old friend, the 32-tap sawtooth sequence. We remember also the DFT of this 32-tap 68 00:05:38,612 --> 00:05:44,732 sawtooth. The periodic sawtooth sequence is shown in 69 00:05:44,732 --> 00:05:52,216 this figure for a few periods. The DTFT of the periodic extension now is 70 00:05:52,216 --> 00:05:58,567 this weighted set of deluxe. So the deluxe sit at multiples of 2 pi 71 00:05:58,567 --> 00:06:06,027 over N and they are weighted by X of k. So characteristically at the frequency 0 72 00:06:06,027 --> 00:06:12,488 it's equal to 0 because the sawtooth sequence has an average of zero. 73 00:06:12,489 --> 00:06:18,352 And then because of shapes that we know from the DFT of the sawtooth sequence. 74 00:06:18,352 --> 00:06:22,709 To recap, this spectrum looks exactly like capital x of k. 75 00:06:22,709 --> 00:06:29,123 Except that the display different, because the zero frequency is at the center rather 76 00:06:29,123 --> 00:06:33,530 than at the left hand. And we have a 2 pi here of the spectrum 77 00:06:33,530 --> 00:06:37,728 where we only show the spectrum between minus pi and pi. 78 00:06:37,728 --> 00:06:41,466 And of course, rather than having finite values . 79 00:06:41,467 --> 00:06:46,174 This capital XK. We have delta as, as is indicated here 80 00:06:46,174 --> 00:06:50,769 with the red arrows. Let us do the very same exercise. 81 00:06:50,769 --> 00:06:57,464 But now, with a finite support signal. So x over bar, as we indicated, is equal 82 00:06:57,464 --> 00:07:01,810 to xn over the interval 0 to N minus 1, 0 otherwise. 83 00:07:01,810 --> 00:07:08,122 It's a DTFT denoted by x over bar, e to the j omega is simply the sum of x over 84 00:07:08,122 --> 00:07:14,107 bar times e to the minus j omega, and which in this case, is a finite sum 85 00:07:14,107 --> 00:07:19,565 because x n is 0 elsewhere. So it's a sum from zero to capital N minus 86 00:07:19,565 --> 00:07:24,297 1 of e to the minus j omega N. Now this looks very much like the DFT 87 00:07:24,297 --> 00:07:28,180 except we don't have K in the exponent we have omega. 88 00:07:28,180 --> 00:07:33,321 Okay on the second line of this development we can replace X over bar. 89 00:07:33,321 --> 00:07:40,191 By the inverse dft of the Xk so which is written between parenthesis. 90 00:07:40,191 --> 00:07:46,521 Then we can take sum over k outside with the xK and within the parenthesis we 91 00:07:46,521 --> 00:07:53,355 simply have the complex exponential and the exponent now is only omega minus 2 pi 92 00:07:53,355 --> 00:07:59,118 over N times k multiplied by n. The key therefore is this expression 93 00:07:59,118 --> 00:08:04,201 between parenthesis. This finite sum with the exponent omega 94 00:08:04,201 --> 00:08:09,914 minus 2 pi over n times k. And this, we denote by r over bar with the 95 00:08:09,914 --> 00:08:15,889 Fifth to the location omega minus 2 pi over capital n times k. 96 00:08:15,889 --> 00:08:22,677 This r over bar is actually the dtft of the interval indicator signal. 97 00:08:22,677 --> 00:08:29,013 So, indicator is 0 elsewhere, but only interval 0 n to capital N. 98 00:08:29,013 --> 00:08:33,030 This one. So we show here r over bar simply in the 99 00:08:33,030 --> 00:08:39,797 case of n is equal to, well let's count, must be 9 or something like this in this 100 00:08:39,797 --> 00:08:47,008 case here very simple elementary signal. And we're going to calculate the DTFT of 101 00:08:47,008 --> 00:08:52,091 this r over bar signal. So R over bar e to the j omega, it's a sum 102 00:08:52,091 --> 00:08:56,311 of e to the minus j omega n from 0 to capital N minus 1. 103 00:08:56,311 --> 00:09:02,461 This is our good old friend, it's a finite geometric series, we see this on the 104 00:09:02,461 --> 00:09:06,299 second line, we take out a phase factor, Factor. 105 00:09:06,299 --> 00:09:11,555 E to the minus j omega, N over 2. Both upstairs and downstairs. 106 00:09:11,555 --> 00:09:14,959 But downstairs, we also have the capital N. 107 00:09:14,959 --> 00:09:22,050 And this allows us to replace what's between square brackets as sine of omega N 108 00:09:22,050 --> 00:09:27,070 over 2 versus, in the denominator, sine of omega over 2. 109 00:09:27,070 --> 00:09:31,250 And the face factor is simply, factored out. 110 00:09:31,250 --> 00:09:35,555 We see, now, the DTFT for the case, N is equal to 9. 111 00:09:35,555 --> 00:09:42,676 And in this case, we show the real part. And if we center, actually, these signals. 112 00:09:42,676 --> 00:09:48,680 Then the face factor would be equal to one, and we'd see exactly this. 113 00:09:48,681 --> 00:09:55,595 Now we can finish the computation of the DTFT of the finite-support signal. 114 00:09:55,595 --> 00:10:02,156 So x over bar of e to the j omega is the sum from 0 to capital N minus 1 of X k 115 00:10:02,156 --> 00:10:09,803 times Lambda, only got minus 2 pi over n times k, where lambda of omega is simply 116 00:10:09,804 --> 00:10:17,796 renormalized version of r over bar as a DTFT of, as a finite interval indicator 117 00:10:17,796 --> 00:10:22,398 signal. Let us look at what happens if we take a 118 00:10:22,398 --> 00:10:28,962 32-tap sawtooth sequence. We know the DFT an old trend, it must be 119 00:10:28,962 --> 00:10:35,922 the third time that we see this DFT with a 0 value at the origin 0 and it's 120 00:10:35,922 --> 00:10:41,626 characteristic details on going back up towards 31. 121 00:10:41,626 --> 00:10:46,026 One. A finite support extension is shown here 122 00:10:46,026 --> 00:10:53,892 for a support of, I guess, 128, plus -128, so we see the sawtooth in the middle and 123 00:10:53,892 --> 00:11:00,748 it's zero elsewhere. Is a DTFT of the finite support extension 124 00:11:00,748 --> 00:11:10,200 is now sketched here by taking the DFT and smoothing It by interpolating with the R 125 00:11:10,200 --> 00:11:16,692 of E to the G omega function. So we add one two three, et cetera. 126 00:11:16,692 --> 00:11:23,298 And as we go, we find the smooth interpolation here between the points of 127 00:11:23,298 --> 00:11:27,706 the DFT that are in Light grey in the background. 128 00:11:27,706 --> 00:11:34,308 This should look familiar because we have computed this spectrum already once in 129 00:11:34,308 --> 00:11:37,849 module 4.4 and we got the exact same result. 130 00:11:37,849 --> 00:11:44,127 As a comparison to the DTFT of the periodic extension, we see some similarity 131 00:11:44,127 --> 00:11:50,688 but some differences, so here we have a small spectrum, in the case of Periodic 132 00:11:50,688 --> 00:11:55,152 extension we had a set of D-racks/g, but of course the coin side, that's the 133 00:11:55,152 --> 00:11:59,976 location of the D-rack, we pass exactly through with the red function here which 134 00:11:59,976 --> 00:12:04,782 is the smallest interpolation. Now, this was quite a bit of effort to 135 00:12:04,782 --> 00:12:08,713 actually compute a DTFT of a finite support signal. 136 00:12:08,713 --> 00:12:14,423 And so what people often do is I'll say take the finite support signals, the 137 00:12:14,423 --> 00:12:17,852 extended with zero, so called zero padding. 138 00:12:17,852 --> 00:12:24,454 And then they compute the DFT numerical It generates definitely nicer plots, and 139 00:12:24,454 --> 00:12:28,468 we'll shall see a few examples in the next slides. 140 00:12:28,468 --> 00:12:35,161 The DFT of the 32-tap sawtooth,[LAUGH] again, and we are going to zero pad it. 141 00:12:35,162 --> 00:12:42,198 So here, we zero pad it with 64 zeroes. So the first 32 entries are equal to the 142 00:12:42,198 --> 00:12:46,727 sawtooth and the next 64 entries are 12 zeroes. 143 00:12:46,727 --> 00:12:52,713 You see the DFT, it has a similar shape as the DFT of the initial period of length 144 00:12:52,713 --> 00:12:58,693 thirty-two at the origin at If the K is equal to zero, then it's still zero, so no 145 00:12:58,693 --> 00:13:03,135 suprise there. So let us compute discrete fully transform 146 00:13:03,135 --> 00:13:07,903 of a zero product signal. Let's call it capital Xm of h where h is a 147 00:13:07,903 --> 00:13:13,033 frequency, it is a sum from zero to capital m minus 1 of a signal X prime 148 00:13:13,033 --> 00:13:16,587 which is the extension of the initial signal. 149 00:13:16,587 --> 00:13:22,004 X and the usual expression, so this a sum from 0 to capital N minus one of Xn, e 150 00:13:22,004 --> 00:13:27,001 equal minus j 2 pi over capital M, that's an important point, n times h. 151 00:13:27,001 --> 00:13:33,409 We use the usual trick, by now you should be familiar with this one, so we have the 152 00:13:33,409 --> 00:13:39,229 sum over Small n and then we replace xn by the inverse dft of Xn, it's usual 153 00:13:39,229 --> 00:13:43,995 expression. And we then reorder the summations. 154 00:13:43,995 --> 00:13:49,672 So we take out a summation over k in front with the x, sub mk. 155 00:13:49,672 --> 00:13:57,022 And between parenthesis, we have this expression which now looks familiar to sum 156 00:13:57,022 --> 00:14:02,220 from 0 to M minus 1. And it has exactly the same expression as 157 00:14:02,220 --> 00:14:08,850 the DTFD over finite link symbol, but instead of having omega, we have 2 pi over 158 00:14:08,850 --> 00:14:13,870 capital N times h. And so this is simply the expression of x 159 00:14:13,870 --> 00:14:19,142 over bar e to the j omega. Evaluated at the location Omega is equal 160 00:14:19,142 --> 00:14:24,404 to two point Pi over capital N times H. The exercise we had done before. 161 00:14:24,404 --> 00:14:30,710 So obviously zero padding does not add any information that is not already in the DFT 162 00:14:30,710 --> 00:14:35,482 or for that matter in the DTFT. And so a zero padded DFT is simply a 163 00:14:35,482 --> 00:14:41,979 sampled version of the discreet time fluid transform of the finance support extension 164 00:14:41,979 --> 00:14:46,360 of the signal. Let us do this by example again. 165 00:14:46,360 --> 00:14:51,421 Guess what? We take the 32 tap sawtooth sequence, 0 166 00:14:51,421 --> 00:14:54,409 padded. So, the 32 point DFT. 167 00:14:54,409 --> 00:15:02,444 And we are, family width, of course. Here is 1 half of this 32 point, DFT. 168 00:15:02,444 --> 00:15:08,608 And then we have the DTFT of the finite support signal in blue. 169 00:15:08,608 --> 00:15:13,517 And we. Simply sample it, for example here we have 170 00:15:13,517 --> 00:15:21,005 the 96 point DFD which was the extension we have seen just earlier, and we find 171 00:15:21,005 --> 00:15:28,545 indeed the DFD as predicted by sampling. We do the same exercise now with a 200 172 00:15:28,545 --> 00:15:36,150 point DFT and this is a sampling of the DTFT of the finite support signal as show 173 00:15:36,150 --> 00:15:39,662 here in blue and the samples in red.