Loading...

3.2.b Examples of DFT calculation

Course video 17 of 108

Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By reworking the principles of electronics, telecommunication and computer science into a unifying paradigm, DSP is a the heart of the digital revolution that brought us CDs, DVDs, MP3 players, mobile phones and countless other devices. The goal, for students of this course, will be to learn the fundamentals of Digital Signal Processing from the ground up. Starting from the basic definition of a discrete-time signal, we will work our way through Fourier analysis, filter design, sampling, interpolation and quantization to build a DSP toolset complete enough to analyze a practical communication system in detail. Hands-on examples and demonstration will be routinely used to close the gap between theory and practice. To make the best of this class, it is recommended that you are proficient in basic calculus and linear algebra; several programming examples will be provided in the form of Python notebooks but you can use your favorite programming language to test the algorithms described in the course.

查看授课大纲

您将学习的技能

Signal Processing, Discrete Fourier Transform, Data Transmission, Ipython, Fourier Analysis, Convolution, Linear Algebra, Digital Signal Processing

教学方

Paolo Prandoni
Lecturer
Martin Vetterli
Professor

脚本

So let's look at some examples.

And one property that we will use in the following which is obvious from

the definition of inner product is that the DFT,

the Discrete Fourier Transform transform is a linear operator.

So if you have the DFT of the sum of two vectors this would be equal to the sum of

the DFTs and the same goes if you have the scalar multiplication.

So the first example is a DFT of the discrete time delta.

You can see the delta here in the time domain.

It is 1 in 0, and 0 everywhere else over the support of the signal.

Now if you work out the inner product of the discrete time delta,

with the 48 basis vector you will see that the delta

will isolate the 0 component of each basis vector.

So the product will be 1 for all values of the index k.

So the Fourier transform of the discrete time delta is the constant 1.

In other words,

delta contains all frequencies over the possible range of frequencies.

The dual example of that is the Fourier transform of the unit function.

So you have 1 for all values of the time index and if you work out the inner

product, you will see that the Fourier transform corresponds to a delta.

This is quite intuitive because this is nothing else

than the orthogonality formula that we showed before.

So it will be equal to big N and 0, and 0 everywhere else.

So now let's try to compute the DFT of a sine of other function.

We take x[n] to be 3 times the cos of 2pi over 16 times n.

We are a C 64, so n the dimension of our space is 64.

And the fundamental frequency of our Fourier transform would be omega

equal to 2pi over 64.

All frequencies in the Fourier basis will be a multiple of this.

With this in mind, we can start by expressing the frequency of

our sinusoid as a multiple of the fundamental frequency of this space.

So 2pi over 16 will be equal to 2pi over 64 times 4.

With this now, we can use Euler's formula that says that cos of

omega is equal to e to the j omega plus e to the minus j omega divided by 2.

And express the original cosine as the sum of two complex exponentials.

Namely, e to the j 2pi over 64 times 4 times n

plus e to the minus j 2pi over 64 times 4 times n.

Now we don't like this minus here.

So what we're going to do is exploit the fact that we can always add

an integer multiple of 2pi to the exponent of the complex exponential.

And the point will not change on the complex plane.

So minus j 2pi over 64 times 4 times n plus j 2pi n

will be equal to e to the j 2pi over 64 times 60 times n because n is an integer.

And so now we have expressed the original signal as a sum

of two Fourier basis vectors.

So x[n] will be equal to 3 over 2 times

basis vector number 4 plus basis vector number 60.

At this point we can apply the DFT as an inner product with each vector

in the basis, and we can exploit the linearity of the operator.

So X[k], the kth Fourier coefficient Will be equal to

the inner product between basis vector number K, and our signal.

If we replace the signal with what we just computed before,

we have this formula here.

Because of linearity, we can split this into two distinct inner products.

And we have 3 over 2 times inner product of the generic basis vector

times basis vector number 4 plus 3 over 2 times the inner product

of the generic basis vector with the basis vector number 60.

But now we know that this guy here, will be none 0 only for k equal to 4.

And this guy here will be non 0 only for k = 60.

When k = 4, this will be equal to big N namely 64 and

when k = 60, this will be equal to again 64.

And so if we work out the arithmetic, we got that the DFT of original signal is

equal to 96 if k is equal to 4 or is equal to 60, and 0 otherwise.

So we can plot the DFT of our cos and it will be 0

everywhere in the real part except in 4 and in 60.

Whereas the imaginary part will be 0 everywhere.

So let's try another example.

Here we take the same cos as before, but we add an initial phase.

So we take 3 times the cos of 2pi over 16 times n plus pi over 3.

The first thing we do is to express the frequency of the cos

as a multiple of the fundamental frequency for the space, we're still in C64.

Then we use Euler's formula and

we decompose the cosine as the sum of two conjugate complex exponentials.

And we can express the phase term, we can take it out of the complex

exponential as a complex scalar multiplicative factor.

So then we can use the same trick as before to bring this negative frequency

into the 0, 63 range.

And we obtain that our signal is simply 3 over 2 times the sum of

basis vector number 4 multiplied by e to the j pi over 3 plus

basic number vector 60 multiplied e to the minus j pi over 3.

And when we compute the DFT, we take the product of that with the generic basis

vector for Fourier basis and just like before we obtain just 2 non 0 values.

When k is equal to 4, the first term will survive

given us a DFT value of 96 times e to j pi over 3.

And when k is equals to 60 we will get 96 e to the minus j pi over 3,

and 0 everywhere else.

We can plot the Fourier transform like before and

we will have in this case non 0 values both in the real and the imaginary part.

Probably a clear way of plotting this Fourier transform,

however is to plot both the magnitude and the phase of the Fourier coefficients.

If you remember what we just computed, the magnitude will be equal to 96,

both for k = 4 and for k = 60.

And the phase will be equal to pi over 3 for

k = 4 and minus pi over 3 for k = 60.

This way of plotting the data shows that we can use the fully transformed

to separate the amplitude of a sinusoid from its phase.

So I'm sure that by now most of you will be saying okay, but what about sinusoid

whose frequency is not a multiple of the fundamental frequency for the space?

What do we do there?

And indeed let's say, we take a sinusoid with frequency 2pi over 10, so

3 times the cosine of 2pi over 10 n.

Well this cannot be reduced to a multiple of 2pi over 64.

It is a frequency that actually falls between 2pi over 64 times 6,

and 2pi over 64 times 7.

So what do we do there?

Well we simply compute DFT numerically.

Remember the DFT is an algorithm that requires a finite number of operations and

that can be computed with the desired level of precision

in numerical packages such as MATLAB.

Where you can even write your own C code routine to do so.

We will see later in module 4.9 that very,

very efficient algorithms exist to compute the DFT, so this is not a problem.

So we run the DFT in a numerical package and we obtain the magnitude and the face.

Now if you see high level of magnitude indicates a similarity of the input

with the corresponding basis vector, it's a definition of inter product.

So here unsurprisingly, the input is particularly close to

basis vectors number 6 and number 7 as we showed before.

And by extension to 64-6 and 64-7.

But in order to obtain the exact 2pi over 10 frequency,

we need contributions from all the DFT coefficients in the 0 to 63 range.

And similarly the phase is non 0 for the whole range as well.

This is actually a general result unless you have an input that is a linear

combination of basis vectors, most of your DFT coefficients will be now 0.

Let's go for instance an example that we can compute exactly.

Let's consider the DFT of the step vector in CN.

We're in CN, and we have a signal that is 1 for

n equal to 0 to m-1 and then 0 everywhere else.

If we compute the DFT, we can just write the inner product explicitly

and replace the values for the input signal.

So now x of n will be equal to 1 for

small n goes from 0 to big N minus 1, and 0 everywhere else.

So this simply reduces the sum, that originally went from 0 to big N-1,

to 0 to M-1, and the coefficient for each term will be 1.

So this is a geometric sum, we have seen that before.

So sum for n that goes from 0 to big M-1 of a to the power

of n is equal to 1-a to the power of big N divided by 1-a.

So we apply that, we obtain this ratio and now,

we're going to perform a little trick.

So let me write it here on the side.

If we have an expression of the form 1 minus e to the minus j alpha,

we can always collect half the phase of this complex exponential.

And write e to the minus j alpha over 2, then multiplies

e to the j alpha over 2, minus e to the minus j alpha over 2.

Why do we do this?

Well because this guy here is nothing else than 2j sine of alpha over 2.

So we can separate this element into a real

valued component and into a phase term.

So we do this for this expression and

we collect half the phase here and half the phase here.

And if we work out the algebra, we get that the DFT coefficients are equal to

the ratio of two sin functions times a pure phase term here.

Now I'm not going to read out loud this formula, but we're going to try and

plot it.

So we're going to try and get intuition about how this is going to look.

So first of all,

if we think about the magnitude of this coefficient, note that this

phrase term we will always be equal to magnitude because it's a pure face term.

So the magnitude will be determined

by the ratio of these two trigonometric functions.

In 0, this ratio is ill defined, but if you go back to the expression for

the DFT sum.

You can see that if you put k = 0,

it becomes simply the sum of big N 1s, so the DFT of 0 = M.

Another point to notice is that if k is a multiple of N over M, then

the numerator here will be equal to 0 and so the DFT coefficient will be equal to 0.

Finally the phase, which depends only on this complex exponential here,

is linear in k as you can see from the formula.

Except sin changes for the real part where we will have a jump of pi.

So if we plug this in magnitude and face, we have that the shape looks like so.

We are using a length 4 step in C64, so N over M will be equal to 16.

And indeed the DFT coefficient will be 0 and

16, 32 and 48, and all multiples of 16.

The phase is indeed linear, and whenever there is a discontinuity

in the sine of the real part, we will have a jump of pi.

So discontinuity, you can see it here.

Here we're plotting the magnitude of the real part.

But in reality, if we were to plot the part with the sine,

this would become negative here.

Go back to positive here, and then go negative here.

Notice that here the phase extends from 0 to minus 4 pi,

this is a little bit unusual.

We said that 0 to 2 pi or minus pi to pi is the only interval that we're

interested in at this current time because everything maps back to that interval.

It's very common to see plots where the phase is wrapped over the minus pi,

pi interval.

What that means simply is for every value of the phase we add or

subtract to pi until we fall back into the minus pi, pi interval.

So here's the same plot as before but with the phase wrapped.

关于 Coursera

课程、专项课程和在线学位均由全世界一流大学和教育机构的顶尖授课教师教授。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取