4.5 - DTFT: intuition and properties

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 have seen the Discrete Time Fourier transform, DTFT,

to analyze infinite-length sequences.

The way we have done it is to look at it as a generalization of the DFT

where the frequency 2π over N goes toward smaller and smaller intervals

because N goes to infinity

and, in the limit, becomes an uncountable frequency ω.

Now the intuition is that we can still think of this as a transform

like the DFT was a transform,

and have all the intuition about expansion into basis functions

even though ω is actually an uncountable variable.

And so strictly speaking we don't have a basis.

However it helps a lot to think of the DTFT as a generalization of the DFT

so we can carry over all the intuition of finite dimensions

to this infinite dimensional transform.

Module 4.5 Discrete Time Fourier Transform - intuition and properties.

We have seen that the Discrete Time Fourier Transform, or DTFT,

and we now worry about conditions for its existence.

Then, we look at some properties of the DTFT.

And finally we give an interpretation of the DTFT as a basis expansion,

even though formally, it is not a basis.

We have here the formula of the Discrete Time Fourier Transform.

It's an infinite summation, and goes from minus infinity to plus infinity

of the sequence element x[n], multiplied by e to the -jωn.

Now this infinite sum could explode, and then we would be in trouble.

So the question is, when does it actually exist,

and how does it relate to the concept of changing the basis,

as we have seen for the DFT, for example?

Let us start with an easy case,

namely the case of sequences that are absolutely summable.

Let us look at the value,

or the maximum value of the discrete time Fourier transform.

So we look at the absolute value of x of e to the jω,

this is the absolute value of the formal sum of the DTFT.

Now, the absolute value of the sum is always smaller

or equal to the sum of the absolute values.

That's the second line.

And the absolute value of xn times e to the -jωn

is the product of the two absolute values.

Since the second term has an absolute value of 1, or a magnitude of 1,

we have simply the summation of the absolute value of xn,

which by assumption is smaller than infinity.

So what we have verified is that when a sequence is absolutely summable,

then its DTFT magnitude is always smaller than infinity.

Now that we know

that the spectrum X of e to the jω is finite,

we can look at the inversion formula, which is given by

1 over 2π, and integral of the spectrum over one period,

times e to the jωn.

We write out the spectrum as the infinite series

xk e to the -jωk

which is between parenthesis here

then we reorder summation and integral.

The integral is over one period -π to π

of e to the jω (n-k).

This integral is equal to 1 when n is equal to k

so when the exponent is 0 and it is 0 elsewhere

and therefore we have indeed that the inversion is equal to x[n].

When x[n] is absolutely summable

we can periodize without any risk xn into x tilde of N.

So that's a periodization.

We take the sum of xn and shifted versions by N.

Actually an infinite number of these guys (?),

and this will be well-defined.

Let us do this graphically here.

So we have a first signal -- so that's x[n].

It's a Gaussian and we repeat a second one,

third one, fourth one etc.

And then we take the sum.

And the sum of this is a periodic sequence, obviously.

And it's the blue line here,

which represents a sum of all these periodic extensions

of the base signal x[n].

We periodize with a capital N.

What happens if N grows larger and larger?

So first we show N = 10.

N = 15,

N = 20 -- 40 -- 80 -- and, of course,

what happens is that x tilde essentially converges to x[n]

because the periodized versions go away to infinity.

And we are back to our initial x[n],

the initial sequence that we started with for the periodization.

Now this periodized signal x tilde Capital N of small n

has a natural representation that we have seen before,

it's a Discrete Fourier Series, okay?

So we write a Discrete Fourier Series of one period,

call it capital X tilde.

Then, we can write the expression for x tilde of n

which is simply the summation of x [n + mN].

And then we add the same expression to the exponent.

Because adding a multiple of capital N

to the exponent of the complex exponential

doesn't change anything.

So we end up with this double sum at the end,

n going from minus infinity to plus infinity,

small n going from 0 to N-1,

the signal x[n] and its periodized versions, and an exponent

which has the same expression n + mN.

We use a trick that comes often,

and this is to say that an infinite sum, for example f(i),

from i going from minus infinity to plus infinity,

can be split into pieces of length N,

okay, so we can write this as a summation

over one of these pieces of length N

and then, simply sum over all these pieces.

So we get the double sum

with m going from minus infinity to plus infinity

and n going from 0 to N-1.

This formula looks a little bit forbidding

so let's explore it for a simple case:

let's pick N = 3 and let's make a table here

of what we are going to sum.

And the table is going to have n as vertical entry,

m as a horizontal entry, now n goes from 0 to 2.

Okay, so we need two lines here

and n goes from minus infinity to plus infinity:

we're just going to go from 0 to plus infinity

because otherwise --

And then we get there and so this is a table

and I list here's the indices of f's

that are going to be appearing in this table.

So the index here will be zero.

For n is equal to 1 is 1. 2, then it is 3, 4, 5, 6, 7, 8, 9, 10, etcetera.

Okay?

And when we do the double sum,

we simply sum all these terms,

which, of course, if we follow exactly this order here,

is equal to the sum on the right side.

OK: so now we are ready to use this trick.

So we had an expression for x tilde of k,

this double sum over m and small n.

And, of course,

we can now merge this double sum into a single sum.

So we sum over i for minus to infinity of

x[i] e to the -j, 2π over N, k i.

And there we recognize of course

the expression for the Discrete Time Fourier Transform

evaluated at the frequency 2π over N times k.

Okay so our Discrete Fourier Series x tilde of k

is simply the Discrete Time Fourier Transform

at equally spaced frequencies ω,

namely the spacing of 2π over N.

We are now ready to develop the intuition.

Take a x[n] that is absolutely summable.

Then we know that X (e to the jω) exists and is finite.

And we can a put meaning to it.

If we periodize xn into x tilde of n,

its Discrete Fourier Series is x of e to the jω

evaluated at 2π over N times k.

Since we know that DFS represents actually a change of basis,

has a energy conservation etc.,

we have all the right intuition for what's going to happen with the DTFT.

The only thing that is left is, as N grows,

x tilde of N goes towards x[n]

-- we have seen this, because x[n] is absolutely summable --

and the spectral representation essentially becomes

what we have seen as the DTFT,

because the spacing 2π over N becomes finer and finer

and ends up being the continuum of ω,

the frequencies of the DTFT between -π and π.

Let's develop this intuition a bit more graphically now.

So we start on the left with a vector in C N.

We go to the transform domains, the DFT domain,

by taking inner products of the vector small x[n]

with e to the j 2π/N nk,

which are the basis vectors:

that gives us the transform values, X[k].

And we can come back with the inversion formula we had seen before,

simply using 1/N

and taking the exponent with a positive sign.

So we have a orthogonal basis for the space CN,

as we had shown and proven before.

The very same thing happens with the Discrete Fourier Series.

So we've now C tilde of N, which is a periodized version

of 1 period of length N,

we take inner products,

we go to the transform domain which is X tilde.

We can come back with the same normalization 1/N

and again we have a basis for this finite dimensional space.

What about Discrete Time Fourier Transform, then?

Formally, the DTFT is an inner product

so the formal summation over infinite sequences

with e to the -jωn

is simply the inner product between e to the jωn and the sequence.

The basis now is infinite,

So it is not a basis, it's uncountable:

the ω in the exponent is a real number, therefore uncountable

So something breaks down because we start with sequences

but we go to a transform, which is a function of ω.

One more point:

we showed this for absolutely summable sequences.

It turns out that DTFT is well defined for square-summable sequences

that are our old friends from l2 of z.

The proof of this is technical and we will not go into it.

Again, a graphical display of these relationships:

so we have elements from l2 of Z, square-summable sequences.

We go into a transform domain using an inner product

to get X of e to the jω;

The "basis" is an uncountable set since the index ω is a real number,

and we can come back by an integral transform

over one period normalized by 1/2π

and we get back x[n], as we have proven before.

So we go from l2 of Z to the space L2 of -π to π,

using the Discrete Time Fourier Transform,

and we come back, using the inverse DTFT.

The advantage of the intuition we have just developed

is that if we look at the DTFT as a formal change of basis,

the following properties will be fairly obvious.

The first one is linearity.

That is very clear.

It's a linear transform.

It's an inner product actually,

so it has to be a linear transform.

The time shift follows from what we have seen for the DFT,

so if x is shifted by M,

it will be -- its DTFT is multiplied by e to the minus jωM,

and the dual of this relationship is called modulation,

so you multiply sequence by e to the jω0n,

and its spectrum X will be shifted by ω naught.

Time reversal is similar to what we would see in the DFT

so x of minus n is simply capital X of e to the -jω.

That's the formal replacement in the DTFT formula.

Conjugation, same story, easy to verify

that the conjugate of the sequence, leads to a conjugation of the DTFT,

which includes a change of sign in the exponent.

There are some particular cases of the DTFT

that are useful to know about.

So when x[n], the sequence, is symmetric,

so x[n] = x[-n]

Then its spectrum has a symmetry,

namely x of e to the jω is equal to,

is the same at -jω.

If x[n] is real, the Discrete Time Fourier Transform

is going to be hermitian-symmetric:

as we see here, X of e to the jω, will be equal to x star of e to the -jω.

So when x[n] is real,

the magnitude of DTFT is necessarily symmetric,

as you can see

by simply using the magnitude in the above equation.

Finally, if x[n] is real and symmetric,

the DTFT will automatically be real and symmetric.

All these relationships are fairly straightforward to prove.

And we don't go into the details at this point here.

We have now looked at the DTFT

in terms of a basis expansion.

It's not formally a basis expansion,

as we have emphasized,

but it can be seen as such.

And so we have to be a little bit careful,

because certain things will work, and some others will not.

So, for example, it's easy to see

that the DTFT of the δ sequence

-- so that's the sequence I equal to 1 at n is equal to 0 and is 0 everywhere else --

it's the inner product between the complex exponential

and δ = 1, just like what we know from the DFT.

Some other things don't work.

So the DFT of the constant as we have seen is equal to 1,

But the DTFT of the constant would be the infinite sum of e to the -jωn

and this we have no answer to.

So this is a bit annoying

because there are lots of sequences that we like, that we use,

that are natural, but that are not square-summable

or not absolutely summable,

which are the 2 cases where we know of the existence of the DTFT (?).

This will lead us to propose some extension

to the function classes we can work with.

In particular, we are going to use the δ function,

and this will allow us to take DTFT's, for example

of, sine waves and cosine waves

which are definitely not square-summable

or absolutely summable.

But this will come later.