4.4 - DFT, DFS, DTFT [21:37]

See "Chapter 4 Fourier Analysis" in "Signal Processing for Communications" by Paolo Prandoni and Martin Vetterli, available from http://www.sp4comm.org/ , and the slides for the entire module 4 of the Digital Signal Processing Coursera course, in https://spark-public.s3.amazonaws.com/dsp/slides/module4-0.pdf .

And if you are registered for this Coursera course, see https://class.coursera.org/dsp-001/wiki/view?page=week3

>> We now understand the Fourier transform of a finite length signal

namely, the Discrete Fourier Transform.

We are interested to see what happens

if the length of the signal grows and grows to infinity.

There are two ways to do this:

either we take the DFT and we look at what happens

as the length goes to infinity,

or we take a finite length signal, we periodize it,

and compute the discrete Fourier series,

and then let the period go to infinity.

In both cases, the limit will be the Discrete Time Fourier Transform,

which is the natural Fourier transform for infinite-length sequences.

This is a powerful, but more subtle object than the DFT,

and we will need to understand it quite in detail and with some care.

And equipped with a DTFT, we'll be able to think about sequences and their spectras.

Module 4.4. Discrete Fourier Transform , Discrete Fourier Series and Discrete Time Fourier Transform.

To move from the DFT, to the Discrete Fourier Series, into the Discrete Time Fourier Transform,

we are going to start by revisiting the Karplus-Strong algorithm from module two,

we're going to see that we can naturally extend the analysis of the DFT

to a larger class of signals, and this will lead to the DTFT,

and we're going to give an interpretation of this phenomenon.

Remember the Karplus-Strong algorithm: you have an input x[n]

and there is a feedback from the output with a delay factor z to the minus n,

so that's a delay of M samples and multiplication by α,

and this is added to the current input.

So we have a recursive equation,

given at the bottom that describes this Karplus-Strong algorithm.

Let's take a signal that is nonzero on exactly one period.

So it's nonzero, from 0 to M-1,

and for now, we pick α is equal to 1.

With this, the period will simply repeat, so the signal starts at 0

and we get the first period, x over bar 0 to x over bar M-1,

then this period is repeated a second time, a third time and so on, to infinity.

As an example, take a 32-tap sawtooth wave.

So the sawtooth, starts at -1 at 0, and goes up to +1 at 31.

The Discrete Fourier Transform of a length-32 sawtooth wave form can be computed by hand,

but we shall not do this here explicitly.

There is one value, however, that we can recognize immediately,

it's a value for k is equal to 0,

because the sawtooth is asymmetric around the x-axis, this will be 0.

The other values are computed numerically and are shown on this plot.

What if we take the DFT of two periods?

So we will repeat the sawtooth from 0 to 31

and then from 32 to 63, we have two periods here,

and we take a DFT now of size 64.

The 64 point DFT looks similar to the 32 point DTF,

except that all odd entries are actually exactly equal to 0.

So we have same shape of DFT,

however in between every nonzero value, there is a 0 value,

so there must be something going on that we need to understand.

Let's develop some intuition for the DFT of two periods.

So when we take the DFT of two periods,

we take inner products with the DFT basis vectors of lengths 64.

What we will see, is that the even inner product will be different from 0

and the odd inner product will be equal to 0.

For k is equal to 0, we take the inner product between the first basis vector of the DFT

and the sawtooth repeated twice.

The first basis vector of the DFT is simply the constant equal to 1 from 0 to 63.

And so, the inner product is twice the inner product on the intervals of length 32

and this we know, is equal to 0.

So, for k is equal to 0, the DFT, again, is equal to 0.

For k is equal to 1, the situation is very different.

The basis function has sines and cosine,

which have an integral period, positive and negative, as the blue function indicates.

And therefore, whatever happens on the first half from 0 to 31

is canceled by what happens in the second half.

So for k is equal to 1, the DFT coefficient is exactly equal to 0.

For k is equal to 2,

we see that the inner product on the first half of the interval, from 0 to 31,

and the second half, 32 through 63, is exactly the same inner product.

Therefore, it will be double the DFT of size 32.

So it will be nonzero and twice as big

as what we know already from the DFT of a sawtooth of length 32.

For k=3, we are again in the case of cancellation,

now, this is not so obvious as in the case of k=1.

But if you watch carefully,

you can see that the blue parts multiplied by the red signal

have, in pairs, the cancellation property

and therefore, the DFT for k=3 is again, going to be equal to 0.

Let us now prove this property.

So take the DFT, of L periods of the signal.

Call this capital X sub L of k.

This is a summation from 0 to LM-1, of the usual DFT formula here,

and k also goes from 0 to LM-1.

Now we split the sum into two parts,

one from 0 to L-1 and another one from 0 to M-1.

We do this by simply repeating the periods,

so write this as y of n plus p times M,

so these are the various, the L periods we have.

We do the same in the exponent,

then we notice that y[n+ pM] is of course, the same as y[n],

because our signal y[n] is actually periodic, so we can simplify this.

We split the exponents into the two parts,

the parts that is dependent on n, the one that is dependent on p.

This allows us to simplify the exponent of the second one to 2π over L

by simplifying the M.

Now we notice on the last line, that we can separate out the summation over p,

that's what we put between parentheses,

and the second part, which is now simply the DFT of one period,

so it's the summation from 0 to M-1.

Now comes the aha effect.

The sum between parentheses we have seen before, it is a finite geometric series.

So when k is a multiple of capital L,

then it's a sum from 0 to L-1, of the constant 1,

so it's equal to capital L, and otherwise it is exactly equal to 0.

This comes, if you remember, from the orthogonality proof we did for the DFT basis.

Therefore, we can write the DFT of XL of k:

it's equal to L times the DFT of one period, and it's equal to 0 otherwise.

With this, we are ready to talk about the Discrete Fourier Series.

So the DFT of multiple periods is uniquely determined by the DTF of a single period,

we have just proven this.

And the DFT synthesis, if we let it run forever, will generate a periodic signal.

So the Discrete Fourier Series is really very much like the DFT,

except that we explicitly periodize both time and frequency.

So we have a periodic time sequence and we have a periodic frequency sequence.

And that's the natural definition of a Discrete Fourier Series.

We will see that this is similar to the Continuous Time Fourier Series

that you might have seen in a course on mathematical analysis, on harmonic analysis.

This is a simple incarnation in the Discrete Time Domain of periodic signals

and periodic frequency domains.

The Discrete Fourier Series helps us in the case of shifts.

And remember, when we have finite-length signal, it's unclear how we should define a shift,

so we periodize the finite-length signals, that gives us x N periodic (?)

and then the DFS is X periodic,

and the Inverse Discrete Fourier Series of a shifted version,

which corresponds to a phase factor here, is exactly a shift by M.

Since it's an infinite periodic sequence,

we can easily shift without having to worry about the borders of one period.

This discussion of time shift is so important

that we are going to go through it one more time in detail.

So, assume you have an N-point finite-length signal x[n], with a DFT X[k],

how shall we define the IDFT of e to the -j, 2π over n times Mk, of this DFT X[k]?

Well, we can just calculate it, but what is the natural interpretation?

Well the natural interpretation is to build x tilde of n,

which is a periodized version of x[n], so you take x[n]

and the index is taken (?) module, capital N.////

Then, you calculate the DFT of X[k], which is equal to the DFT of x tilde.

The inverse DFT of X[k], multiplied by the shift factor, is inverse DFS, of X tilde of k,

which is, as we've just seen X tilde shifted by M,

which therefore is x of n minus M module N.

So all shifts of finite-length sequences can be seen as circular shifts,

as we have discussed in module 2.1,

but here they are implicit in the definition of the DFT and the inverse DFT.

Now, this was not really Karplus-Strong as we had introduced it,

because α was equal to 1, and we simply had a purely periodic signal.

So in general, α is smaller than 1, and so the single y[n] has a first period,

a second period that is weighted by α, a third one by α squared etcetera,

so it will have a geometric decay, so it is truly an infinite signal,

it's almost periodic, but not really.

And the question is, what would be a good spectral representation for such a signal?

What would be the natural definition of the DFT of a signal that gets longer and longer,

and what really happens when N goes to infinity?

Now the fundamental frequency in the DFT, is given by 2π/N

and it's multiplied by k, which is the frequency index.

So on the interval 0 to 2π, as N goes to infinity,

we get closer and closer frequency values of 2π over capital N.

In the limit, this will go towards a continuous frequency

and so we could define, formally a sum of x[n] multiplied by e to the jωn,

where ω is the limit of 2π over N,

when N goes to infinity multiplied by the frequency index k.

So this leads to a formal definition of what is called the Discrete Time Fourier Transform,

which is a natural Fourier Transform for infinite-length sequences.

So x[n] should belong to one of our Hilbert (?) spaces, so that's L2 of Z.

And we can define the function of ω, given formally by F of ω is equal to

the sum from minus infinity to plus infinity of x[n] times e to the -jωn.

Now that's a forward transform, so the key question is,

can we come back from that F(ω) and when it exists, and we are going to study it (?), when it doesn't,

when we have to be careful, the formal inversion would be

x[n] = 1 over 2π, the integral of 1 period of F(ω) times e jωn, dω

and n is over all integers.

Remember, F(ω) is going to be a 2π periodic function, why is that so?

Because the exponent is e to the -jωn.

If you add 2π to ω, nothing will change in the formal sum for F(ω).

And that's why, in the inversion formula,

we take the integral between -π and π.

Because of the periodicity, we typically write, not F(ω),

but the transform of x[n] as X of e to the jω.

This is not necessary, but it's really to be always conscious that X is a capital X,

a Discrete-Time Fourier Transform is indeed a 2π periodic function.

By convention, x of e to the jω is mapped to the interval, -πi to π.

Any other contiguous interval of length 2π would be fine as well,

since it's a periodic function.

Let us compute an example of a DTFT. The signal is shown here.

It's a one-sided decaying geometric series, so the definition is

α to the n with an α that is smaller than 1 in magnitude, times the step function un

So it starts at 0=1, and then decays exponentially towards 0, at infinity.

To compute the DTFT, we first write down the formal definition,

so it's the infinite some of x[n]e to the -jωn.

This sum is one-sided from 0 to infinity of α to the n, e to the -jωn.

We gather the terms α e to the -jω. raised to the nth power.

And now, we remember the magic formula,

which is a one-sided infinite sum of the geometric series,

it's 1 over 1 minus the term that is raised to the power,

which here is, αe to the -jω.

So we can see this is fairly easily to compute,

because in this example we of course know all the details and how to figure them out.

We can look at the square magnitude of this DTFT,

so that's X of e to jω, magnitude squared.

This is simply 1 over, and then we need to multiply the denominator by its complex conjugate,

which ends up being 1 plus α squared minus 2α cosω.

We would like now to plot this DTFT,

so this is slightly different from what we have done for the DFT.

We put the 0 frequency n in the middle and we plot from -πi to +π.

The positive frequencies go from 0 to π, the negative ones from 0 to -π.

Low frequencies are around the origin. High frequencies are towards π and -π.

Let us now plot the DTFT we have just calculated.

We see here the example for α is equal to 0.9,

so it has a maximum at the origin

and then decays rapidly towards π.

Now remember that the DTFT is periodic,

so here is the first period between -π and π.

We add the second period, a third period, the fourth period,

and we see now this periodic signal that will extend to infinity.

Now we are ready to really compute

the Discrete-Time Fourier Transform of a real Karplus-Strong signal.

So let's take the sawtooth wave of length 32 that we have seen before,

the equation is given here, and the graph is displayed at the bottom.

So if we look at the symbol y[n], it is built up from u[n], the step function,

so it's one-sided to the right,

then we have a repetition of the sawtooth, that's x overbar,

whereas the index is taken (?) module M.

And finally, there is a decay by α to the power of the number of periods,

this we can write as taking (?) n/M, and then taking the integer part.

To compute the DTFT, we first write formally the expression of the DTFT,

so the sum of yne to the -jωn.

Then, we split the infinite sum into two sums.

One which is over the period, that's going to be a one-sided infinite sum,

p from zero to infinity,

and a second sum, which is the sum over a period.

Then we have α to the p, because that's the decay.

Then we have x overbar multiplied by e to the -jω,

where we simply have written now,

the initial index decomposed into n+pM.

The next step is to separate these two summations because they don't interact

and we have the summation over p, which is the DTFT,

essentially of the sequence α to the p

and the DTFT of one period from 0 to capital N minus 1 of x overbar.

And so the expression is going to have two components,

one that we call A of e to the jωM, another one,

which we call X overbar, which is a DTFT of one period.

A to the e jω is easy, because that's a DTFT of the one-sided geometric series,

we had calculated it just before we show here in the picture.

This is taken to the nth power of e to the jω, so that rescales the frequency,

so the periodicity is going to be changed by this rescaling factor.

So we show here, first for M=1, then M=2, M=3,

and for example, M=12.

You can see now the repetition pattern is not a periodicity of 2π,

but the periodicity of 2 π divided by 12.

Now we need the DTFT of one period of the sawtooth, we can go through this exercise

and indeed it is left as an exercise.

You see here, the expression, it looks a little bit complicated,

but it is simple algebraic manipulation that lead to it.

So spectrum or the magnitude of the spectrum is shown at the bottom.

It has a 0 at the origins, that, of course, we know,

and then it has a very particular and decaying pattern with repetitions.

Now we can write out the total spectrum,

y of e to the jω is equal to the product A e to the jωM,

that's very important.

That changes the periodicity multiplied by the spectrum of x overbar,

and so we recognize this product, it has the repetition pattern and it has the shaping.

If we put the two together, we can see that the repetition pattern come from the periodicity,

so in this case for example, M (?) is equal to 32 and the shape is actually the spectral shape

and gives the timber of the signal.

We can now conclude what we have seen in this sub-module.

First, we considered a Fourier Transform for finite-length signals,

the so-called Discrete Fourier Transform.

We extended it to periodic sequences,

to have the Discrete Fourier Series, very closely related to the DFT.

And then we saw a Fourier Transform for infinite sequences,

that we called a Discrete Time Fourier Transform

and we introduced it as the extension or the limit of a Discrete Fourier Series

when the period goes to infinity.

At the very end, we took all this together

and we derived a DTFT for a realistic and complicated signal,

namely the Karplus-Strong, with a decay and an interesting spectrum.

This was a non trivial exercise,

but you could see by putting all the elements together that we have seen so far,

we managed to actually understand its spectrum.