Learn the fundamentals of digital signal processing theory and discover the myriad ways DSP makes everyday life more productive and fun.
3.2.b Examples of DFT calculation
Loading...
来自 École Polytechnique Fédérale de Lausanne 的课程
数字信号处理
286 个评分
从本节课中
Module 3: Part 1 - Basics of Fourier Analysis
与讲师见面
Paolo PrandoniLecturer
School of Computer and Communication Science
Martin VetterliProfessor
School of Computer and Communication Sciences
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.
