4.6 - DTFT formalism

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

In the preceding sub module, we saw conditions under which

a sequence actually has a finite-magnitude Fourier Transform,

namely, the sequence has to be absolutely summable.

We also saw that it can be extended

to square-summable sequences.

However in real life,

many sequences are neither absolutely nor square-summable.

For example, cosine of ω naught, times n

is an infinite-length sequence

that is neither absolutely nor square-summable.

Therefore it doesn't have, in the strict sense, a DTFT,

as we have seen before.

To be able to deal with sequences like this,

we need to introduce a new character in support.(?)

This is the δ function or δ distribution,

or also called the δ generalized function.

As you can see, this is a more subtle object

than what we are used too.

It's actually a function that this zero everywhere,

except at the origin where it's infinity.

Doesn't sound like a nice function,

but is actually is a very useful mathematical abstraction

and a very powerful object to have in the toolbox.

So we're going to introduce this δ function

and then, once we understand it intuitively,

we can use it to calculate, for example,

the DTFT of this cosine of ω naught times n

which will have the spectrum that contains Dirac δ's.

So the good news is that

now we have this subtle Dirac δ function that will allow us

to take Discrete Time Fourier Transforms

off a whole set of new functions and sequences

that we didn't know how to handle before,

and to look at their spectrum.

Module 4.6: Discrete Time Fourier Transform formalism.

The overview is simply that we are going to introduce

the Dirac δ functional, or generalized function.

And we can use this Dirac δ to study the spectras of sequences

for which we didn't know so far how to compute a DTFT.

We'll do this through a number of examples.

The tricky thing with the δ functional

is that we cannot describe the function itself,

we can only describe it indirectly,

through what's called the sifting property.

So for example here we have the integral between δ of t-s.

With the function f of t,

the result of the integral is that it takes out,

it weeds out (?) the value of f of t, at location s.

And this will be true for all functions -- or for all well-behaved functions --

of t belonging to the set of real numbers.

The intuition for this Dirac δ function

is really through thinking about a family of functions.

We index them by k here, or k of t.

And k is a positive integer, t is a real number,

and the support of these functions is inversely proportional to k

and have a constant area.

We're going to specifically look at an example.

The example is the rect function.

We have seen this before.

It's a function that is piecewise constant.

It's zero inside an interval minus a half to one half

where it is actually equal to 1.

From the rect function, we can derive a localizing family,

r k of t, by simply scaling the rect function

both in its height and its width.

So it will be nonzero over an interval going from -1/2k to 1/2k.

So the support is of width 1/ k.

Since it's of height k,

the area is exactly equal to 1, independently of k.

So let's look at the few instantiations of this rect function,

scaled in height and in width.

So k is equal to 1,

k is equal to 5,

k is equal to 15,

k is equal to 40.

You can see it becomes higher and higher, obviously,

but it's narrower and narrower,

and its integral is always exactly equal to 1.

Now, let's see these localizing functions at work.

So remember, there are rk of t.

We take an integral of rk of t times f of t.

And this is equal to k times the integral

over an interval of length 1/k,

and the mean value theorem says that on this interval,

there is a value of f, namely f of γ,

there exists at least one value f of γ

which is equal to this integral.

And so, as k goes to infinity,

the interval becomes narrower and narrower,

and therefore, the limit of the integral is equal to f of 0.

Okay, so we have seen how taking the limit of the localizing functions,

extracts the value of f of t at the origin f0.

Now, in this case we have assumed that a function is continuous.

Otherwise, it's obviously more technical.

So, in the end, the Dirac δ functional is simply a shorthand,

instead of always writing the limiting process

-- so, for example, our integral on the previous page here, which is limit as k goes to infinity --

we simply write the integral between δ of t minus s times f of t.

This integral is going to be equal to f of s,

as if we have taken the limit:

so it's a shorthand of this limiting process

that we have seen on the previous slide.

If we have one Dirac,

we can also look at a sequence of Dirac:

there is one, in particular,

that is used very often in signal processing.

It's δ of ω tilde.

This is equal to 2π times an infinite sum of Diracs,

located at multiples of 2π.

Let's look at the graphical representation.

So you have Diracs at zero, at plus minus 2π,

at plus minus 4π, etcetera.

Now this function, δ tilde of ω,

this sequence of Diracs, spaced 2πi apart,

is actually very useful.

So let's put it to good use.

So take the inverse DTFT of δ tilde.

So it's the integral over one period, minus π to π,

of δ tilde against (?) e to the j ω n.

This, of course, involves only a single Dirac at the origin,

because that's the only Dirac in the sequence that is inside the interval.

This is equal to the evaluation of e to the jωn:

at ω = 0, this is exactly equal to 1.

Therefore the inverse DTFT of δ tilde

is equal to the sequence x(n)O is equal to 1.

But that's a miracle because we didn't know

how to take the forward DTFT

of the constant signal x(n) is equal to 1,

so now we actually know what it is.

In conclusion,

the Discrete Time Fourier Transform of the constant sequence

is δ tilde of ω,

the sequence of Diracs spaced 2π apart.

Now this looks like we played a trick on you

because we started with a constant sequence,

we looked at the DTFT,

and we were confused what the result would be.

So let us do a sanity check.

Let's just calculate the partial sums of the DTFT.

So sk of ω is the sum between minus k and k, of e to the -jωn.

We plot the magnitude of sk of ω

for k is equal to 5,

k is equal to 10, 15, 30, 40,

and we start to see a Dirac emerging:

one spike at the origin.

The partial sum DTFT looks like a family of localizing functions.

So sk of ω will, as k grows, converge to δ tilde of ω.

Now we can do the exact same exercise

on δ tilde of ω minus ω naught

by the same argument as before.

We will sift out the Dirac that is inside the interval, minus π to π.

And this one will lead to a complex exponential,

e to the jω naught times n.

From this, we have DTFT pairs.

The DTFT of 1 is, as we have seen, δ tilde of ω,

the DTFT of e to the jω naught times n

is equal to δ tilde, ω minus ω naught.

More interestingly is the DTFT of cos ω naught times n:

Well, using Euler's formulas, we know that the cosine

is a combination of 2 complex exponential.

Each one will generate a δ tilde,

one shifted to ω naught,

the other one shifted to minus ω naught.

Finally, the DTFT of sine ω naught n

is equal to something very similar,

there is a scaling factor and multiplication by minus j

and then two δ tildes again

shifted to ω naught and minus ω naught.

It is time to summarize, and to see the parallels

between the DFT, which acts on CN,

and the DTFT that acts on C infinity.

Please note before starting

that the δ over sequences has square brackets,

as we have seen.

And the δ over the real line has round brackets.

So these are very different elements.

δ in discrete time is a very simple sequence

with a single nonzero element,

δ over the continuous line is a distribution

or a generalized function:

as we have seen, it's a Dirac δ function.

With this preliminaries,

let's look now at the left side, and properties on C N.

So we had verified that complex exponential, of length N,

with frequencies that are multiples of 2π/N,

are orthogonal to each other:

that's formula A,

this is written as also DFT of the complex exponential

of a frequency 2π/N times h,

gives a transform that is equal to N times a δ at the location h.

The inverse discrete Fourier transform of a δ at location h

is equal to a complex exponential at frequency 2π/n times h.

And this is written under d as explicitly

as a summation of the δ with respect to the complex exponential.

Same result

Now let's more to the right hand side.

There the inversion formula we have seen of Dirac tilde

which is a sequence of Diracs,

is integral over one period

and if the Dirac sequence is shifted to σ,

it will generate a complex exponential e to the jσn.

So that's under C', it's the IDTFT of δ tilde.

Then under B', the DTFT of e to the jσn

is δ tilde shifted by σ,

and this leads to A',

where we simply write that the inner product

-- so that's the expression the DTFT between two complex exponentials --

leads to δ tilde shifted to σ.

So now we see these formal parallels between these two transforms:

one on CN as a DFT, which is very simple,

it's elementary linear algebra,

and the other one, the DTFT

which acts on infinite sequences, which is more subtle,

and which leads, in the cases we have seen here,

to generalized functions (?), sequences of Diracs.

Yet they act very similarly: the same intuitions about frequencies,

about complex exponentials, about Diracs appear in both cases.

And that's really the message we want to convey here.

Let us now conclude.

The final result we have seen shows

a formal orthogonality of the "basis" of e to the jωn,

the sequence of infinite-length complex exponentials.

So if you're careful enough, everything works just nice.

But remember the δ notation presumes that you took a limiting operation.

And it's just a lazy shorthand to express something

that always implies a limit. A δ in the spectrum,

so if we have an x of e to the jω, and there is a δ function there,

indicates that the signal has infinite energy,

So we are not within our comfortable Hilbert space framework of l2 of Z.

But the δ notation proves to be very useful

in derivation of certain results,

for example, the modulation theorems

that we are going to see later in this module.

Yet, there is a word of care.

As a friend of mine says,

when you use δ's it's like walking on the edge of a precipice.

If you put the foot on the wrong side

you might actually die.

With this word of caution, let's move on.