We have seen the discrete Fourier transform, the discrete Fourier series, as well as the discrete time Fourier transform. Now we are going to look at the DTFT of periodic sequences on the one hand and the DTFT of finite report sequences. And create the relationship between these two cases and the DFT or DFS. Finally, we will look at zero padding techniques that is often used to smooth spectras from finite length signals. The DFT and the DFS can be seen as changes of bases in C capital N. It's obvious because it's a matrix factor multiplication and we go from the original domain to the DFT domain. The DTFT, on the other hand, we introduced as a quote-unquote, formal change of basis over l2(Z) as a space of finite energy sequences. The basis factors are building blocks for any signal. So we can write the signal as a linear combination of basis vectors. In the case of the DTFT, this is formal because the index for the DTFT, which is frequency omega, is uncountable, so we don't have a countable basis. Yet the intuition we have from the DFT or the DFS carries over in that sense to the DTFT, as we have seen in the preceding sub-module. The DFT and the DTFT are really two sides of the same coin. The DFT leads to numerical algorithms. It's essentially linear algebra, and we can derive fast algorithms based on these formulaes. The DTFT is more of a mathematical tool. It comes in handy when we want to make proofs and to see properties of Fourier transforms. If we are given a finite-length signal x[n] which has capital N non-zero entries, say, for n goes from zero to capital N minus one, then the natural spectral representation, as we have seen, is a DFT given by capital X[k]. Now, there are two ways to embed x[n] into an infinite sequence. One is, we can do a periodic extension. So we take the index module, capital N. That gives us x tilde of n, which is simply the repetition, where the period is of length capital N. Another way is the finite support extension. So, we denote this by x over bar, which is equal to x[n] on the interval zero to capital N minus one, and equal to zero otherwise. How does X[k], the DFT of the finite-length signal, relate to the DTFT of these two forms of signals? This is what we shall pursue in the next few slides. So what is the DTFT of x tilde of n? Well, it's capital X tilde of e to the j omega, which is a formal power series of x tilde of n multiplied by e to the -j omega n. In this expression we replace x tilde of n as the inverse Fourier series of capital X tilde. It's in the expression between parentheses. This of course, is equal to the inverse DFT. And we simply reorders the sums, so we take out the a sum over k in front, and we leave inside the parentheses the sum over n, gathering the e to the j to various power terms. Then we recall that this infinite sum of e to the j, 2 pi over Nk times e to the minus j omega n is simply the DTFT of a complex exponential of frequency of 2 pi over capital N times nk. And this, we know, is going to be our delta tilde signal, shifted to the location 2 pi/N times k. With this, we have now a formal expression for x tilde of e to the j omega, namely, 1 over N the sum of the DFT coefficients, capital X k, multiplied by delta tilde, shifted to the frequency 2 pi over capital N times k. Let us look at an example and take a good old friend, the 32 tap sawtooth sequence. We remember also the DFT of this 32 tap sawtooth. The periodic sawtooth sequence is shown in this figure for a few periods. The DTFT of the periodic extension now is this weighted set of Dirac. So the Dirac's set at multiples of two pi over capital N, and they are weighted at capital X of k. So characteristically, at the frequency zero is equal to zero. Because both of those sequences has an average of zero, and then it has a shape that we know from the DFT of the sawtooth sequence. To recap, this spectrum looks exactly like capital X of k, except that the display is different, because the 0 frequency is at the center rather than at the left end. And we have a 2 pi periodic spectrum, where we only show the spectrum between -pi and pi. And of course, rather than having finite values capital Xk we have deltas, as is indicated here with the red arrows. Let us do the very same exercise, but now with a finite support signal. So, x over bar, as we indicated, is equal to x[n] over the interval zero to capital N minus 1, zero otherwise. The DTFT, denoted by x over bar e to the j omega is simply is the sum of x over bar times e to the minus j omega n, which, in this case, is a finite sum, because xn is 0 elsewhere. So, it's the sum from 0 to capital N minus 1 of e to the minus j omega n. Now, this looks very much like the DFT, except we don't have k in the exponent, we have omega. Okay, on the second line of this development, we can replace x over bar by the inverse DFT of capital Xk, which is written between parentheses. Then, we can take the sum over k outside, with the x capital K. And, within the parentheses, we simply have the complex exponentials. And the exponent, now, is omega minus 2 pi over capital N times k multiplied by n. The key, therefore, is this expression in between parenthesis, this finite sum with the exponent omega minus 2Pi over N times k. And this we denote by R over bar, with a shift to the location omega minus 2Pi over N times k. This R over bar is actually the DTFT of the interval indicator signal. So the interval indicator is zero elsewhere, but on the interval zero to capital N- 1. So we show here, Rover bar simply in the case of N is equal to, well, let's count. It must be 9 or something like this in this case here. A very simple elementary signal, and we're going to calculate the DTFT of this R over bar signal. So R over bar (e to the j omega) is the sum of e to the minus j omega n from 0 to N-1. This is our good old friend, the finite geometric series. We see this on the second line. We take out a phase factor, e to the minus j omega capital N over 2, both upstairs and downstairs. But downstairs without a capital N. And this allows us to replace what's between square brackets as sine of omega n over 2 versus, in the denominator, sine of omega over 2, and the phase factor is simply factored out. We see now the DTFT for the case N=9. And, in this case, we show the real part. And if we center actually these signals and the phase factor would be equal to one, and we'd see exactly this. Now, we can finish the computation of the DTFT of a finite-support signal. So X over bar of e to the j omega is a sum from zero to capital N-1 of X(k) times lambda omega minus 2 pi over N times k, where lambda of omega is simply renormalized version of R over bar, the DTFT of, is a finite interval indicator signal. Let us look at what happens if we take the 32-tap sawtooth sequence. We know the DFT, an old friend, it must be the third time that we see this DFT with zero value at zero, origin zero. And its characteristic decay ends on going back up towards 31. The finite support extension is shown here for a support of, I guess, 128 plus minus 128. So we see the sawtooth is in the middle, and it's zero elsewhere. The DTFT of the finite support extension is now sketched here by taking the DFT and smoothing it by interpolating with the R of e to the j omega function. So we add one, two, three, etc., and as we go, we find the smooth interpolation here. Between the points of the DFTs that are in light gray in the background. This should look familiar, because we have computed this spectrum already once in Module 4.4, and we got the exact same result. As a comparison to the DTFT of the periodic extension, we see some similarity but some differences. So here, we have a smooth spectrum. In the case of the periodic extension we had a set of Diracs, but of course they coincide. At the location of the Dirac, we pass exactly through with the red function here, which is a smooth interpolation. Now, this was quite a bit of effort to actually compute the DTFT of a finite support signal. And so what people often do is that they take the finite support signal, they extend it, with zero, so-called zero padding, and then they compute the DFT numerically. It generates, definitely, nicer plots and we shall see a few examples in the next slides. So, DFT of the 32-tap sawtooth, again. And we are going to zero pad it. So here we zero pad it with 64 0, so the first 32 entries are equal to the sawtooth, and the next 64 entries are just 0s. You see the DFT, it has a similar shape as the DFT of the initial period of length 32. At the origin, at k is equal to 0, it's still 0, so no surprise there. So, let us compute the discrete Fourier transform of a zero-padded signal. Let's call it XM[h], where h is a frequency. It is a sum from 0 to M minus 1 of a signal x-prime, which is the extension of the initial signal x, and the usual expression. So, this is a sum from 0 to N-1 of xn, e to the -j 2pi over M, that's an important point, n times h. We do the usual trick, by now you should be familiar with this one. So, we have the sum over n, and then we replace x n by the inverse DFT of XN. It's the usual expression. And then we reorder the summations. So we take out the summation over k in front, with the x sub n k. And between parentheses we have this expression, which now looks familiar. It's a sum from 0 to capital M minus 1. And it has exactly the same expression as the DTFT of a finite-length signal. But, instead of having omega, we have two pi over capital M times h. And so, this is simply the expression of X over bar e to the j omega, evaluated at the location omega is equal to two pi over capital M times h. The exercise we had done before. So, obviously, zero padding does not add any information that is not already in the DFT or, for that matter, in the DTFT. And so, a zero-padded DFT is simply a sampled version of the discrete time fourier transform of the finite-support extension of the signal. Let us do this by example again. Guess what, we take the 32-tap sawtooth sequence, zero-padded. So the 32-point DFT, we are familiar with, of course. Here is one half of the 32-point DFT. And then, we have the DTFT of the finite support signal in blue, and we simply sample it. For example, here we have the 96-point DFT, which was the extension we had seen just earlier. And we find indeed, the DFT, as predicted by sampling. We do the same exercise now with a 200-point DFT. And this is a sampling of the DTFT of the finite support signal, as shown here in blue, and the samples in red.
