Polyphase Decomposition - Electrical Engineering Video Lecture - Electrical Engineering (EE)

Today, we shall be taking up a very important topic Polyphase Decomposition. Now, those
who have the electrical engineering background,
they know, in electrical engineering, polyphase
means or say three phase systems, we have
in the phase circuit. Polyphase means, each
of the phases will be having lead or lag over
the other, lead or lag of angle. So, here
it is a little different, but will see the
principle is more or less identical, it is
the response of a particular channel which
will be having a different phase from the
other channels. So, there is a kind of a phase
shift that we give in the response will see
how it is done.
FIR Filters you have studied in the DSP course,
FIR filters when you synthesize, we can have
a direct form
we can have a cascaded form. What is the advantage
of cascaded form, why do you cascade filters,
direct form, it is like this, h 0 plus h 1
z inverse plus h 2 z to the power minus 2
and so on. Say, h n minus 1 z to the power
minus n minus 1. Suppose this is an end point
sequence FIR filter. So, you take multipliers,
this is x n, then you multiply by h 0 take
derivatives multiply by, take the difference
operators z inverse multiplied by h 2 and
so on. And then add them together. This is
the direct form
and so on, if I factorize it, in the form
of h 1 z into h 2 z and so on. Then, I can
have, say quadratic factors, then I will have
just structures like this, coming again
in this form, this is z inverse, this is again
z inverse, added together and so on. So, such
blocks will be coming in the h 1, h 2, h 3,
the advantage is, whenever there are some
drifts in the parameter values, only the roots
associated with this block, with this quadratic,
only will be affected.
Whereas here, if there is a shift in the value
of h 2, it will be affecting all the n minus
1 roots, all the zeros will be shifting, whereas
here, that this zero is corresponding to this
particular block, is quadratic will be affected,
it will not be affecting others. So, you are
going to restrict the moment of zeros, due
to the drifts in the parameter values, parameter
values change because of truncation. You know
you have a finite register length, you have
an 8 bit or 16 bit register. So, all this
coefficients will be truncated, either you
round off or you truncate, so there will be
some error, so these errors will have some
effect on the location of zeros. So, anyway,
this is the direct form and the cascaded form,
there is also another form.
You must have studied it, that is the lattice
structure, we are not going to discuss about
the lattice structures right now. And there
is a fourth form, that is the one, that we
are going to discuss today, the polyphase
structure, a polyphase form. It is like this,
H z we can write as h 0 plus h 1 z inverse.
Say, I have up to h 10 z to the power minus
10, I can pick up the alternate terms; that
means, even terms and odd terms, I call it
H 0 z, H 1 z , I may write like this, h 9
z to the power minus 8.
Now, this is a function of z to the power
minus 2, so H 0 z, I can write this as, some
E 0 z square, is a function of z square, where
e 0 z will be h 0 plus h 2 z inverse plus,
Finally, h 10 z to the power minus 5. Similarly,
H 1 z can be written as, e 1 z square, where
e 1 z is h 1 plus h 3 z inverse and so on,
h 9 z to the power minus 4. Do you agree,
it is a polynomial in z to the power minus
1, both of them e 0 and e 1. So, that polynomial,
z if you replace by z squared will get h 0
and h 1 z, if I take out z inverse, this is
H 1, this is e 1, e 1 z square, so e 1 z means
this.
So, H z can be written as E 0 z squared, plus
z inverse E 1 z square, if we have instead
of taking up alternate terms, every third
term we pick up, then H z can be written as
E 0, what should I write, z cubed, do you
agree, plus z inverse plus. So, generalizing
this, if I have M such groups, H z can be
written as E 0 z to the power M, plus z inverse
E 1 z to the power M, last term will be M
minus 1, minus. See, for every third term,
if we pick up, that is, if it is having three
polynomials, then z to the power minus 2 and
if it is, the index here is 3.
So, here it will be 2, it will be ending at
E M minus 1, z and z to the power, the same
number, M minus 1, so we can write the polynomial,
any polynomial, we can have any number of
such groups. So, suppose L is the number of
polynomial groups, what will be the terms
of this? Any general term, say E k or E m,
z, what will be this polynomial, h, if you
have an infinitely long sequence.
Let us consider a non causal system, that
is, n extends also, up to minus infinity,
then and we choose the terms like this, say
every Lth term, then it will be L n plus m.
Is it not, if you have taken say the every
third term, so this will be 0 plus 1, 2 into
0 plus or 2 into 1, plus 1 like that, if you
have taken 3, three terms. Then the coefficients
of this or any of this, any E Mth term will
be appearing like this, can put them in this
manner.
So, the realization for this first one is
E 0, as it is E 0, suppose we take this one,
every third term, so E 0 z cubed, next, there
is a delay element, E 1 z cube, next E 2 z
cube, this is y n. You can try, a few more
structures, it is very simple, you can have
fourth order or higher order realization,
for a 3 branch, this is a 3 branch polynomial
realization. So, we have got, E 0 as h 0 plus
h 3 z to the power minus 3 plus h 6, z to
the power minus 6. E 1 was h 1 plus h 4, z
to the power minus 3 plus h 7, z to the power
minus 6, whole thing into z to the power minus
1.
I mean, you want gets multiplied by z to the
power minus 1, that is what I meant. And E
2 similarly, will be h 2 plus h 5 z to the
power minus 3 plus h 8 z to the power minus
7 sorry, 8. And then z to the power minus
6, sorry minus 6, z to the power minus 2.
So, all of them are having the same order,
of course, if you have 9 points, then only
it will be 3 each, if you have 10 points,
then this will have 4 element set, others
will be 3. So, the highest will be the 4 element
set. Now, if you realize it, if you try to
realize this filter, it will be like this.
x n, suppose we have a multiplier here h 0,
then I can put, z to the power minus 3, then
h 1, h 2, you can put another z to the power
minus 3, then from here, I can have a multiplier
h 6. Now you see, h 6 is multiplied by z to
the power minus 6, added with h 0 and h 3
z to the power minus 3, so z to the power
minus 3 is here, so I will take multiplier
here, h 3 and add them here. This is the output,
corresponding to the first phase.
h 1, similarly will have h 3, h 3, I can take
from here, h 4 and h 5, h 4 is added with
h 4 z to the power minus 3, added with h 7
z to the power minus 6 and added with h 1,
after that, the total sum is multiplied by
z inverse. So, from here I can take h, let
me
multiplied this by h 7, this by h 8, so h
7, h 4, this is h 7 into z to the power minus
6, h 4 into z to the power minus 3 and h 1,
this will be an output, which finally, if
I multiplied by z to the power minus 1, I
will get the second output.
And lastly, h 2 plus h 5 into z to the power
minus 3 and h 8, these three will give me
h 2 plus h 5 z to the power minus 3 plus h
8 z to the power minus 6, whole thing will
be multiplied by z to the power minus 2. I
will, I could have made use of this before
addition, so I will put, z to the power minus
1 block here and then
add with this and then this product is finally
multiplied by z to the power minus 1. So,
these are all getting multiplied by z to the
power minus 1, this is getting this set, this
sum is getting multiplied by, z to the power
minus 1 and again z to the power minus 1.
So, this is the final output, this plus this,
y n, now, if you have a linear phase filter,
what is the advantage of linear phase filter,
h 0 suppose there, there has to be a symmetry
from the 2 ns. Suppose, it is symmetric filter,
then h 0, h 8, h 1, h 7 like that, you have
symmetry of elements. So, you need not have
different values, h 0 is same as h 8, so you
will have same multiplying element and you
see, the total number of elements will be
much reduced, you can try for an anti symmetric
filter also. So, you try at home, the final
structure for an anti symmetric filter and
a symmetric filter, having three or may be
four levels of decomposition.
So, we can have, if it is an FIR linear phase,
I will take up a simple example, you can try
a little more complex structures. Suppose
we have, h 0 plus h 6 z to the power minus
6, I have coupled a seven element linear filter,
I have coupled the terms h 1 plus h 5 z to
the power minus 4 into z to the power minus
1 plus h 2 plus h 4 z to the power minus 2,
into z to the power minus 2 plus h 3 z to
the power minus 3.
I can write like this and h 6 is h 0, so it
is basically h 0 into 1 plus z to the power
minus 6, plus h 1 z to the power minus 1 into
1 plus z to the power minus 4, plus h 2, 1
plus z to the power minus 2, z to the power
minus 2, plus h 3, z to the power minus 3.
So, this one can be realized in a very interesting
way, you have each rectangular block is a
delay element z inverse, z inverse, z inverse,
again z inverse. I have just put the delay
elements in chain.
Now, see what I am doing, you take h 0, it
has to be added with, I say 1 plus z to the
power minus 6, so there are six delay elements,
so I will take the output here, add them together,
I have done this addition, take this out,
multiplied by h naught. So, can I suggest,
what should you do next, it is z to the power
minus 1, and z to the power minus 5. So z
to the power minus 1 has already been taken
and this is z to the power minus 5, so add
them here and then this output, you take here,
what should be the multiplier, h 1.
In signal flow, we use just the arrow for
the multiplying constant, so I need not always
write a constant with any block. Similarly,
this one, I add with this output, this is
to be multiplied by h 2 then it is better
to show the direction, by an arrow like this
and a constant by a little bigger arrow, in
analog gains you show, multiplier like this,
so it is like this. In many books, they use
a small arrow, both for direction z inverse
or any multiplier that is all allowed.
So h z, any signal X z, I can write therefore,
in the decomposed form as sigma z to the power
minus k, x k, z to the power M, k equal to
0 to M minus 1, is it not. If there are, M
such sub groups, then k will have maximum
M minus 1, the polyphase components, this
is the polyphase components, x k z will be,
say x k n, z to the power minus n, n tending
to infinity. And what is this, in terms of
the original sequence x n, from the original
sequence, we are picking out say, either every
third term or every fourth term or every Mth
term. So, it will be x, M n plus k z to the
power minus n.
Mind you, this is the polynomial, when I am
writing in terms of z to the power minus 1,
polynomial of z to the power minus 1 and this
will be expressed, in terms of polynomial
of z to the power n. So, in a matrix form,
I can write this as 1, z to the power minus
1, z to the power minus 2, z to the power
minus, M minus 1, into X naught z to the power
M, X 1 z to the power M. Similarly, the last
one X M minus 1, z to the power M, this summation
I have written in this form.
So, for the M band, polyphase decomposition
will look like this, I give a signal x n,
I have a down sampler M, down sampler does
what, you are picking up only the Mth terms
in the given sequence. So, we are down sampling
by M, this will give me the terms x M n, every
Mth term, again down sample by M, this will
give me x M n plus 1, mind you, this is plus
1, we are generating the next set, that is
why this is, z not z inverse, again down sample
by M, x M n plus 2 and so on.
Lastly, it will be x M n plus, M minus 1,
n is any number varying from minus infinity
to plus infinity, integers, is this structure,
it is like any of our previous forms. So,
like this this series is h 1, h 4, h 7, this
series is h 2 h 5 h 8. So, the general term
is 2 plus 3 into n, 1 plus 3 into n. So, the
starting value is 1 2 3 etcetera and this
is M n.
For an IIR filter, Polyphase decomposition
is rather difficult, for IIR filter it is
not straight forward, a simple example will
give you, so 1 minus 3 z inverse, divided
by 1 plus 4 z to the power minus 1. Suppose,
this is an IIR filter, how do you decompose
into such terms, say in terms of z square,
say if we take a polynomials of z square,
so I reduce this, if I multiply by 1 minus
4 z inverse, multiply both sides by the same
factor. So, the denominator becomes 1 minus
16 z to the power minus 2.
So, I have got a polynomial in, z to the power
minus 2, this one, 1 minus 7 z inverse, plus
12 z to the power minus 2. So I can write
this as, 1 plus 12 z to the power minus 2,
by 1 minus 16 z to the power minus 2, minus
z inverse into 7 by 1 minus 16 z to the power
minus 2. So, it is like our first, E 0, z
square plus z inverse into E 1, z square,
this is z inverse multiplied by this function
E 1. It was so simple, because we have taken
a very simple polynomial, reducing a polynomial,
to a polynomial of quadratic terms, will not
be so simple, had it been a little more involve,
then it will be difficult.
So, earlier we saw x n, if I down sample x
n and if I have a filter here H z, giving
me an output y n, this is equivalent to x
n, H z to the power M. That means, if I have
a down sampler followed by a filter H z, I
can interchange their positions, but then
the filter has to be changed, z has to be
modified to z to the power M, then we will
get identical output, this we had discussed
earlier. Now, when you are going for a decimeter,
you require a low pass filter, this we saw
earlier, why do you need a low pass filter,
that is an anti aliasing filter, for down
sampling you require, a low pass filter.
Let this be some H z, mind you, this H z has
got nothing to do with this, this was only
an equivalent solution, now we are talking
about, a decimeter, whenever we want to decimate
the sequence, by a factor M, we must check
whether aliasing takes place or not. So, we
have a band limited filters, so this is a
low pass filter H z, this H z, suppose we
write in a polyphase structure of z to the
power M, then what we get and then we will
be using this relation, to be more specific.
To avoid confusion, let this be, written as
H dashed z, to avoid any confusion in this
H z, so this is a relation that we have established
earlier. Now, we are going to make use of
it, at a later stage, suppose you have to
design this H z, now we decompose it, in a
poly phase form. So, if we decompose H z,
it will look like this, just now we have seen
the decomposition, the earlier one, anyway,
we will have it here.
E 1, z to the power M, E 0, z to the power
M, again a delay element E 2, z to the power
M and so on, is it not. E M minus 1, z to
the power M and this is H z, the center block
is H z and then we put the down sampler. Now,
each one of them can be treated separately,
is it not and if I put a down sampler, that
means, I can put the down samplers here and
then I can interchange, by this solution.
So, if a down sampler is having previous to
this, H z to the power M then I can put H
z only. So, this will be equal to, I will
take this page, this will be equal to, what
was the frequency here F t and this is also
F t, the frequency here is, F t by M.
And now we are having F t, I can put the down
sampler first, then this will be, what will
be this one, E 0 z, z to the power minus 1,
E 1 z and so on. And keep on adding them,
I will get the same output y n, what about
the frequencies, now, it is here F t by M
and here also F t by M, down sampler has change
the frequency, so will be at these points
also. This is computationally more efficient,
why can you justify, this is computationally
more efficient, see if you have a single H
z.
Suppose there are ten coefficients or say
nine coefficients and there will be, nine
multiplications and then eight additions,
it will take time, unless the entire cycle
of…. For each stage, I too have the input
sequence, computing all these multiplications
and additions will be taking place here and
from here. We will be picking up only a few
of them, all of them are not required, but
when the chain comes, all the computations
will continue, is it not
And from here, you are selecting only the
Mth terms, when you are picking up Mth terms,
so first term you are picked up, you are waiting,
the computations are going and you are not
interested in it. So, there is a lot of ideal
time for many of the elements and unless the
entire cycle of computation is over, the next
set of data cannot be taken. Now, what happens
here, you are down sampling the data right,
in the beginning, you are choosing the data,
you are making a shorter length and the computations
are going on simultaneously in parallel channels.
So, all the arithmetic operations are going
on, nobody is sitting ideal, so all these
elements will keep on computing and they are
having selected coefficients. Now, out of
nine coefficients, here only three computations
will, three terms are there, so three multiplications
and two additions. Only a few additional,
addition terms will be coming here, but in
each of this blocks, the number of computations
will be drastically reduced and all of them
will be done in a parallel mode.
So, this is computationally more effective,
very efficient, so we have got x n, H z M,
M and y n, this structure, we have reduced
to this form. So, if there are say, N points
and N k points, per parallel branch, so the
number of computations per branch will be,
N k multiplications and N k minus 1 additions,
is it not. So, summation of N k will be equal
to N, these are number of additions in each
block, number of multiplications, either it
was totally N and here, in each section it
will be N k and sigma N k is equal to N. Because
number of coefficients you are not reducing,
if there are nine points, you are picking
up alternatively three, I mean every third
one and you are making three groups, so number
of coefficients will be same.
Now, let us see
an up sampler, if we have E 0 z, L, E 1 z,
L, and so on
and you put a, z inverse term here, a multiplier
here. And you have one such parallel blocks,
last one will be L minus 1, L and this will
be the output, so you can feed to E 0 z, E
1 z, etcetera. If you remember, for a decimeter,
we had what was the relation for a decimeter,
we have seen, if it is decimated first and
then if it is H z to the H z.
If we interchange the position of the decimeter
and the filter, then the filter will have
to be, you know, z inverse will be replaced
by z to the power minus M, reverse will be
the case, in case of
frequency multiplier, what is it called, up
sampler. So, for an up sampler, it will be
E 0 1, E 1 z etcetera and then it will be
up sampled later, if you put in this fashion,
so mind you, this is z, index of z. So, this
will be put, for a down sampler it will be
put on this side, for an up sampler you just
will put on this side, now will go to digital
filter banks.
What you mean by digital filter banks, this
is a bank of band pass filters, we have a
common input and we have a large number of
filters, say H 0, H 1, that means H 1, H 0
z inverse, similarly all these are there,
H 1, H 2 and so on. Corresponding outputs
you get in different bands, that means you
have different bands of frequency, you have
a band pass filter with varying bands and
uniformly distributed in the range 0 to 2
pi.
So, for example, we normally talk about low
pass filter like this, or a high pass filter
like this, or a band pass filter like this,
or a band gap or a band pass band pass filter
like this, band gap like this. Now, same is
the type of filter, instead of this kind of
a rectangular characteristics. Suppose, we
have a filter like this, this is one band,
next we take another filter like this, next
we take another filter like this. Obviously,
you cannot have all the filters put together,
so the first filter will be filtering frequencies
from, say 0 to omega 1, next one will be,
from omega 1 to omega 2. So, it is like this.
I have a channel H 0, which gives me a filter
gain of say, say a characteristic like this,
then I have H 1, this is mind you, in terms
of omega, so this is say some omega 1, will
see later on, it need not be symmetric on
this side, need not be symmetric on this side.
Why, when do you have absence of symmetry,
when the terms or the coefficients are complex,
for a real coefficient H 0, H 1, H 2, if you
have real quantities then for plus, e to the
power j, plus j omega e to the power minus
j omega, the magnitude will be symmetrical.
So H1, anyway, for the time being I am taking
as symmetrical structure, it will be, say
from like this, so this is my band, the third
one would be like this and so on. So, how
do you design such a filter, all of them are
basically this gain, having a shift of a particular
angle. And what is that angle, what is that
angular shift, if I have an M band, equal
band, equal band width filter, then 2 pi by
M, e to the power minus j 2 pi by M is the
shift, it is shifting delayed by e to the
power minus j 2 pi by m.
So, whatever is the filter function here,
multiply by e to the power minus j 2 pi by
M, you will get successive once. This is for
analysis, given an input, we are trying to
get what will be the outputs, these outputs
will be corresponding to different band pass
filters, this is what we do sometimes in mfcc,
basically this is the type of filter bank
you use.
And when you synthesize, you take different
signals, say V 0 n, V 1 n and so on, and then
you have this filters, say F 0, F 1, F 2.
F 1, F 2, F 0 these are all similar filters
and add them together, finally you get the
output, from various inputs we get the output.
So, when you want to filter out a signal,
you have it is response in different bands,
take these and then moderate them, modify
each band, whatever you want and then again
add them, do you get my point.
In different bands, you are having different
responses, so you moderate them. Suppose I
want to suppress or I want to modulate certain
ranges of frequencies, so that has been done
and then after that you again add them. So,
this is a synthesis filter, we will stop here
for today, we will take it up in the next
class how do you get the terms, for this kind of output of the filters. Thank you very much.