數位信號處理器_林顯易_第五單元 離散傅立葉轉換_Part3 離散傅立葉轉換之環形旋積

. DeltaMOOCx
50粉絲
4 次觀看·2023年12月4日
DeltaMOOCx 台達磨課師是大學及高中/高工的免費公益磨課師(MOOCs)平臺。練習題、討論、教師輔導及更多數位課程資源,請至https://univ.deltamoocx.net 註冊。本影片採用「創用CC-姓名標示-非商業性-禁止改作4.0」臺灣授權條款,相關授權作業依「創用CC-姓名標示-非商業性-禁止改作4.0」規範辦理。
Hi everyone. In this part,
we will introduce circular convolution for DFT.
This circular convolution
when compared to the linear convolution we have mentioned earlier
has some basic differences.
In circular convolution,
the signal we see
basically takes on an appearance
of a continuous circle.
This is different compared to what we've described earlier on linear methods
which show the entire time axis along a line.
However, the calculations are basically
quite similar.
I believe that everyone has learned from Unit 3
or Unit 2 a number of basic techniques.
I believe that in this Unit
and in this part,
these techniques will become quite handy
and make things really easy for us.
Now let's see what circular convolution is all about.
First, in this part, we will introduce circular shifting.
This circular shifting is
quite different compared to the shifting we have talked about earlier.
Let's go back
and remember about xp(n) we have talked about,
which is basically expressed in this formula.
In other words, we need to go from the DFT points
inverse them,
to restore xp.
So xp is basically x(n) that have been shifted
and then added up together.
We then find that if we take this xp
and perform a time shift,
which is xp(n-k).
So signal xp undergoes a time shift
and when shifted,
we can get this formula.
From this formula we can see that
if we take this,
if we define this shifted formula
as x'(n)
x'(n)
this x'(n) series is also x'p(n).
So after shifting,
what happens?
Since we know that xp is originally depicted in this formula,
when we take x(n)
and sum the series x(n-ln)
So what would we get after shifting?
This will be the so-called circular shift.
Let's then take a look at the properties of circular shift.
The graph at the top shows the original x(n)
While the second graph shows xp(n)
What does xp(n) do to x(n)?
Basically it was shifted by n, 2n, and 3n
And then add them all up to together to obtain the graph below.
Suppose you take xp(n) and perform a shift of 2 time units,
which is basically xp(n-2),
you'll find that if you take the time
take the time points from 0 to 3
you'll get the parts shown in the boxes on the graphs.
So when you perform a time shift on xp for 2 time units,
you'll find that the values in the box,
which would correspond to the time units 0 to 3,
the signals within this range
would be composed of
1, 2, 3, and 4.
You can further find out that
originally,
when the original xp(n) has been shifted by 2 time units to the back,
this would mean that two signal values at the back, 3 and 4,
would be pushed out
and transferred to the front.
This would mean that
the values 3 and 4 at the back of xp(n-2) are moved to the front.
So we would obtain x'(n)
and new results.
In other words, when you perform shifting,
the points pushed out at the back will be placed at the front.
This concept
is somewhat cyclical.
So the original signal 1, 2, 3, and 4.
For these signals, no matter how it is shifted
along the time axis
will always been turning around in this cycle.
Whatever is pushed out comes back to the front.
So we will be revolving around these 4 points,
giving rise to the concept of circular shifting
where the shift turns around in this circle.
So next we'll see
how this concept of circular shift
can be used to define a modulo.
For modulo N, we have defined it as
x'(n), which is then
basically defined as x((n-k))N. That will be our modulo N.
Take for example,
when k = 2 and N = 4, x'(0)
is basically the same as (n-k).
Now that given n = 0,
0 - k, where k = 2,
that gives us 0 - 2, which is -2, so basically we have x(-2).
So what will this be?
This will be modulo 4.
So what would modulo 4 be?
The meaning of modulo,
which we will mention here,
modulo means that
we take this value and add one capital N.
In other words, x(-2) modulo 4
would be x(-2 + 4) = x(2)
The same goes for x'(1), which is
equal to x(-1) modulo 4
which is basically -1 + 4 to give x(3).
So here we can see that
x'(2) is equal to the original x(0)
and that x'(3) is equal to x(1).
So x'(0) is equal to x(2)
x'(1) is equal to x(3),
and so on in this circular shift.
So now let's review circular functions with even symmetry.
A circular and even symmetric function is where x(N-n)=x(n),
which has the same concept with the even function
and odd function we mentioned earlier.
In other words, x(4-1) = x(1),
x(4-2) = x(2),
and x(4-3)=x(3), and so on. That's the gist of it.
What about the circular function with odd symmetry?
This is where x(N-n) = -x(n)
with an extra negative sign.
Let's take a look at circular convolution
So this is circular convolution.
When compared with linear convolution,
what would be the differences?
First, we know that
if we have 2 signals,
namely x1(n) and x2(n), which gives us X1(k) and X2(k) respectively after DFT.
We know that we will perform a convolution for x1 and x2
and take the results
and subject it to DFT for n points
To obtain X1(k) multiplied by X2(k).
This will be our results.
Now let's take a look why this is the case.
So basically we need to see for the time domain,
what would be the calculations that we need to do.
Since we need to get these properties,
we would need to determine how to calculate our circular convolution.
We first define x3(m)
So what is x3(m)? It's basically what we've seen in the previous page.
When we multiply X2 and X1,
the result on the frequency spectrum is X3(k).
So when we take X3(k) and subject it to IDFT,
we would get x3(n).
So now we would use IDFT x3(n) to deduce that,
on the time domain,
the exact relationship between x1(n), x2(n), and x3(n).
So here we replace X3(k)
with X1(k) multiplied by X2(k).
So we make the substitution here.
Then we would take X1(k) and X2(k)
and substitute them with the DFT formulas.
Once the formulas have been substituted into the equation,
we would find out
x3(n), x1(n), and x2(n)
as well as the relationships between these functions.
So by this concept,
we can then deduce
how this x3(n)
relates to x1(n) and x2(n).
So we continue our deductions from this formula.
So we replace X3(k) with X1(k) and X2(k).
Where X1(k) and X2(k) can both be expressed using the DFT formula
to get the formula we see on the screen.
So we would re-organize the exponential terms in the formula,
group them together to obtain this formula.
Here we need to pay attention to
to this Σ notation.
This one here
and try to solve it.
So for its solution,
We know that for a Σ of a to k-th power for k from 0 to N-1
we would basically have these two results.
When a = 1, we would get N.
When a ≠ 1, we would get this other expression instead.
So in this example, we have used a
to denote this exponential function. In other words,
if we want to ensure that Σ
is equal to N,
then a must be equal to 1,
which means that the exponential function must be equal to 1.
For the exponential function to be equal to 1,
it would mean that the term (m-n-l) must be
a whole number multiple of N, because the denominator is N
and we need a multiple of N to cancel it. Once we do that,
our exponential term would be equal to 1.
So where (m-n-l) is a whole number multiple of N,
we could see that l is equal to
m-n±PN
In other words, l is equal to
((m+n))N,
because ±PN is the same meaning as a modulo.
Modulo means that
when you have a negative figure, you add an N.
When you exceed 1N,
you would subtract 1N.
So this means that
l is equal to ((m+n))N.
OK, so from the original summation formula,
we can derive from the Σ formula that
the relationship is this.
If there is no modulo,
if l is something else,
then it that case,
if we have 0,
then we would find out that the nominator of 1 - a to the N-th power
where a is this exponential term
the exponential to the N-th power would be equal to 1.
So this is why we would get 0.
In other words, we can see that
x3(m) is equal to
this, since we have previously mentioned
that the solution for the entire Σ is N,
this N can cancel out the 1/N at the front,
to derive this formula for x3(m).
Because we see that l,
l must be ((m-n))N,
((m-n))N.
So basically, we have obtained a circular convolution,
where x1 and x2
basically produces this result on the time domain.
So using this convolution formula
allows us to obtain the results for x3(n).
This formula provides a proof for our circular convolution.
OK, so we have an example here
where I have two signals, x1 and x2.
So x1 and x2
undergoes DFT with n points
to obtain new results.
Here we can see that
our circular convolution
can also be denoted using this symbol.
This is also possible.
How do we go about doing this?
We use the same approach.
x1 has a signal 2, 1, 2, 1
while x2 has a signal of 1, 2, 3, 4.
First we must perform a circular convolution
where we
first subject x2 to folding
to obtain x2((-n))4.
Next, we would take this time axis
and replace 4 with 2,
1 and 3 are basically symmetrical.
So we replace 4 with 2
to get this x2((-n))4.
Next, we would multiply 2 with 1
to get 2 * 1,
1 * 4,
and 2 * 3,
and 1 * 2.
We add these all up to get x3(0).
So how do we calculate x3(1)?
Basically we take x2((-n))4
and shift it by a single unit.
which is equal to x2((1-n))4.
So what happens when we shift modulo 4 by a single unit?
This means that the original signal
is turned counterclockwise.
Remember, a counterclockwise rotation,
to get 2, 1, 4, 3.
So using similar concepts,
when these x(n) are multiplied with each other,
the product
is what we see on the right.
So finally,
we add all these together
and see that x3(1) is 16.
So by using this approach, we can get
all the circular convolution results
which are shown in this list.
So everyone,
in this part we have talked about
circular convolution.
I believe that you have
compared it with linear convolution we talked about previously
and found certain similarities.
The only difference is that
when we perform circular convolution,
we would use a circular approach,
where the signal continuously
revolve in a circle.
At the same time, we have also described
convolutions introduced in the previous parts.
But when we are doing DFT,
we will have to use circular convolution.
So we have introduced its basic principles
and why x1 and x2(n).
OK, so in other words, DFT
is basically achieved by performing circular convolutions.
In the next unit we will introduce
certain properties of DFT.
In addition to these properties, we shall also talk about
the properties of linearity and periodicity.
So let's go and take a look.
