State Machine Design - Computer Science & Engineering Video Lecture - Computer Science Engineering (CSE)

[Music]
[Applause]
[Music]
[Applause]
[Music]
to speed of us to love each other
[Music]
[Music]
towards the end of the previous lecture
we considered the design of JK flip-flop
specifically master/slave JK flip-flop
we just started that why did we take up
this particular design mainly because
this particular design will involve a
few states a couple of inputs and a
couple of outputs to deal with and hence
only a few states to deal with and then
the whole design can be explained both
from the hard-wired control point of
view as well as from the micro
programmed control point of shoot okay
otherwise if you just start discussing
the CPU design then there are too many
states and too many issues too many
inputs and outputs to be considered so
as an example we are considering this
the belt is in mind but in fact we had
worked out the table that particular
table is called a truth table or
excitation table specifically with
reference to flip-flop with J and K as
the inputs
I'm the present state what's the next
state and in any state we know a system
develops an output right good but though
we talk about states where this in mind
that essentially in any system design we
are concerned with the inputs to be
handled and the outputs to be generated
nothing more the state the system goes
through we recall the state as a
necessary evil that's what it is okay so
stage is only means to achieve precisely
the ends we want we are not really
bothered about the state but this
digital system goes through States
in accepting the inputs and in
generating the outputs so really
speaking the input and the output the
relationship between this this is what
precisely we are interested in and
states come in between good now we said
in the previous lecture itself that the
inputs we may call them as YJ YK and YC
that is the J and K as the input and C
is the clock input because in any system
if you have a clock then we can
synchronize the generation of the output
with reference to that croc that's why
you have a clock and that is one reason
why a system having a clock will be
called a synchronous system okay it's
also possible to have instead of a
synchronous flip-flop you can also have
the other one called an asynchronous
flip-flop okay now systems though I say
here what we are talking about is just
this component flip-flop as this instead
one can also have an asynchronous one in
that if you have that asynchronous
system the clock will be absent what it
means is as soon as the inputs change
the output will change in a synchronous
system okay they sink in a system as
soon as the inputs change the output
will change and internally there may be
state changes all right whereas in the
synchronous system the just because the
inputs change the output may not change
it will be synchronized with reference
to the clock okay and while discussing
this flip-flop and its behavior we had
not considered the clock yesterday
remember now let's go to the chart and
take a review at that particular
excitation table now you must be
familiar with this JK flip-flop and
specifically I'm going to talk a little
more for those who have not yet been
initiated into switching theory and
logic
circuits okay those who have done a
course on switching theory and logic
circuits this may be a repetition well
look see here you can see this these are
pairs okay
zero zero that's one path then you have
a zero one pair then I 1 0 pair and a 1
1 pair now because we are considering
these for the given present state what
is a next state so for in one the state
may be 0 and we are considering the
second case state as 1
that's why we are having the pairs of
inputs here okay
that is for a given input J and K let us
say 0 and 0 as here for the present
state 0 what is the next state and for
the present state 1 what is the next
year that's what we are saying here good
now see here that as long as K is 1 that
is in in this particular pair 0 1 J is 0
this as long as K is 1 we find that
whatever may be the present state the
next state is 0 that's why I said K can
be considered as a reset input which
means which causes the output to go 0
that is the next state to go 0 and
similarly look at this pair J is 1 in
both these now water may be the present
state the next state is 1 so we say J is
equivalent to an input sorry set input
now what about this pair in this J and K
both are 1 and we are already said that
whenever you have J and K both are 1 it
doesn't mean sets as well as research
basically it means it toggles whatever
be the present state it just goes to the
other state if we do a 0 the next state
will be 1 if the present state is 1 the
next state will be 0 so this in fact is
a toggle input good so now you can see
that
if J is zero okay then when K is 1 the
next state will be 0 if K is 0 when J is
1 the next state will be 1 and if both J
and K are 1 then then a the next state
will be complement of the present state
if it is 0 the next state will be 1
first one next it will be 0 that's what
it is now
one more thing you may notice here see
here the K input okay take a look at
this K input here 1 ok yeah
few points ok maybe I will explain this
further as we proceed along right now in
this excitation table which actually
gives the relationship between the
present state and the next state for a
given inputs ok for a given input it
basically gives the relationship between
present state and next it in other words
what we say is how this flip-flop gets
excited okay by its inputs to assume the
new extreme that is why it's called
excitation table fine but in our case we
not only have these two inputs J and K
but we also have the clock right we are
not yet considered that we have to
consider this clock also now the if I
include the clock in the particular
excitation table then the table will
become unwieldy so I will just explain
there is a reason for that
what is that it is meet the two inputs J
and K and the present state so actually
there are three variables considered
let's say we had in the particular chart
okay take a look at the chart there are
eight states
alright there are eight states that's
because J and K and the present state
three variables are considered so 2 to
the power 3 8 you have now if you
include YC clock also then it become 2
to the power 4 16 right so the size of
the table will become double and it's
not really necessary okay to take a look
at it and there's one other thing we
have at least talked about that JK 4 we
are not talking about they master/slave
pot that particular thing is linked with
the clock now what is that it's like
this whenever the clock changes now
clock we can just take as a sequence of
inputs you remember what we were talking
about earlier the clock is the one in
the processor which will be defining the
state and so really speaking a clock is
a state defining input right whereas you
can consider in this case J and K as
possibly data inputs the clock is in
fact the state defining input okay right
now in a master slave flip-flop is
what's happening in the racing edge that
is this particular one the racing edge
of the clock the inputs namely J and K
will be sensed and internally the
flip-flop will go through some state
change it will not immediately affect
the output and in the falling edge of
that clock the output will be generated
in other words or the racing edge okay
all right here and the racing edge
inputs are sensed
the inputs are sensed here on the racing
edge and and the falling edge of the
talk okay output generated now if more
than one output okay outputs generators
this in fact is the principle of the
master slave well what is the idea
behind this
it basically says whatever may be the
state of input after this edge it's not
going to affect the output subsequently
the behavior of this flip-flop
subsequently this is quite useful
especially in the case of some noisy
situations where there may be some noise
on the inputs J and K okay and by the
time the clock this thing the falling
edge comes the state of the input may
have change it can affect the behavior
of the system okay but will not go too
much into it it's in fact the electrical
engineering conservation output it okay
from comfort science point of view it is
the logic we will take a look at right
so the inputs are sensed during let us
say the rising edge of the clock what I
mean is when o'clock then let us say Y C
becomes 1 that is let's save this way
logic 0 this is the logic 1 so when
clock becomes 1 what is input that is
sensed and when the clock falls back to
0 okay the clock falls back to 0 that so
one level this is the zero level
okay the two levels are here let's the
logic levels to say whatever may be the
voltage or current levels that may be
okay so the outputs will be generated
during the falling edge inputs or sense
during the racing edge it can be the
other way also meaning for instance the
input can be sensed during
falling it the other one it doesn't
matter what it is then in which case we
will be considering this as the prop
duration that's all okay instead of this
we'll be considering the other one
hardly matters what it is good
now you can see the master/slave what
exactly is happen so it says during the
raising edge of the clock sense the
inputs and prepare the systems outputs
it only says prepare the systems outputs
it does not change output immediately
and actually effect the change in the
output during the falling edge this is
the master slave principle now with the
reference we will keep referring to the
chart okay as and when required now
whatever I have said about J and K and
now about the clock which is this YC
same as this okay instead of drawing
another table with 16 entries and
straightaway go and create the s and
chart for this particular flip-flop okay
because s and chart is going to give me
the whole behavior of the system what is
the system here it is monstrous read JK
flip-flop remember that good now we know
that it goes the the system goes through
states so I will or bitterly talk of
starting state some state okay call that
state a okay
and it's orbitally quite arbitrary in
state a I'll just say I assume the
output generated is h0 remember we talk
always talking about you're always
talking about the state box and we are
always recording the output being record
generated in that box okay you stake a
output generated is zero good now
shall we take a look at the chart again
and see what it's what we are talking
about here now let's say we are
somewhere here okay
that is a present state is 0 the output
generated is 0 that's whatever in the
present state 0 the output generated is
being h0 that's what we are talking
about now when the present state is 0
that is these are all the various
possible things ok let's now take a look
if J and K both are 0 the next state is
going to be 0 no change take the next
case in the present state is 0 if you
have J as 0 KS 1 what is your next state
anyway K is a reset input so the next
state continues to be 0 no change so in
other words as long as J is 0 as there
is we are talking about these two cases
as long as J is 0 the state of K does
not matter it does not do anything right
now come to this this present state is 0
okay
now the what is the next rate for the
deed is one and for this one the person
says zero next state is 1 now take a
look at the J and K level for this to
present state 0 when J is 1 right as
long as J is 1 that is here and here
irrespective of whether K is 0 or 1 the
present state changes to 1 agree so
actually it does not matter what the
value of K is it only depends on J now
let us combine this let's get back to
the a-sun charge and combine that
information whatever I have said and
include it as the input condition right
in this state a in which 0 is the output
I am assuming h0 is the output which is
generated in present state 0 ok whatever
I have given in the chart earlier so in
this it only matters what the value of
J's K need not be checked and now
combine that with whatever I have said
earlier about the clock if the clock
where 0 nothing right
so as long as J is 0 and the clock is
also 0 so that's the symbol for and as
long as J is 0 and the clock is 0
okay they didn't continue to generate
continued to be in state 0 that is
generate output head 0 right because K
doesn't matter what it is we already
seen it only depends on J okay
and now as long as J is 0 YJ and YC will
also be 0 how will also take we see is 0
now when will this n combination be 0 it
means YJ and YC 0 really means what
either J or C or both are 0 for any one
of them being 0 this will be 0 so as
long as crock is since 0 level or as
long as wage a is 0 or both being 0 so
this is the condition so for the present
state a in which I have orbitally
assumed the output generated is hit 0
which is equivalent to my assuming the
present state of the flip-flop being 0
right okay as per the chart as well as
so AJ is 0 fine it will remain
now when wage a + YC becomes 1 okay
actually you can see we are not talking
about this kind of a combination earlier
this is the logical and combination of
two inputs this means both YJ and YC
both or 1 so somewhere along well I'll
explain that those who would like to see
that see
suppose this is the zero level this is
the one level now what we are talking
about is this okay see here this is zero
level this is the one level now it just
take a specific instant here wage a we
see both are 0 so that responds to the
ASM chart to this now take this instant
okay in this instant so let me call this
as T 1 T 2
now during T 1 YJ we see both are 0 now
during t2 YJ is 1 we see is still 0 then
again this holds Good now check this
instant t3 now I am seeing YJ we see
both 1 okay so for ensure there's no one
way J and we see both or 1 now when it
is what did we say earlier when it is 1
the input alone is sensed the output
should not change output will change
only for the falling edge so they said
an internal change in the state but
output will how to be we have to
continuously be generated eye state 0
itself that is there is a state let us
say state change from a and let us call
this as B there is a state change from A
to B but the output continues to be H 0
that's mainly because of what we had
said earlier
now the input sense only in the racing
thing right
so now Oh AJ input need not be checked
YC is all that has to be checked next
many because as long as YC is one the
days let's come to this as long as we
see is one that is this duration okay
now we don't know about YJ we'll come to
that later and fill in as long as YC is
one this will continue to be in the same
state because the output should change
only for when we see Falls to zero
now when I say Falls to zero that is
when we see becomes 0 then we say there
is a straight chain and now there'll be
an output change also mainly because we
are said when YJ becomes 1 the present
state 0 should become next state 1 right
let's go back to the chart and take a
look confirm that again see present
state 0 the next state is 0 in this
present state is 0 next state 0 is in
this case the present state is 1 the
next state is 1 only for J being 1 so
really here to present state is 0 the
next state is 1 only for J being 1 and
we have considered the case of J being 1
right
Oh AJ right way J is that particular one
so that is we are cut from this state to
this state mainly because YJ was 1 so
you should cause a change in the output
but not until the clock
Falls from 1 to 0 let us say there is a
delay now then it's 0 when that is in
the forecast 0 but there is a change in
state see change in the state to see
from B to C and now the output that is
generated is h1 which corresponds let us
see to D that's the difference with the
chart letter C that corresponds to the
next state being 1 just see here J is 1
ok the next state is 1 so J is 1 the
next state is 1 ok correct so actually
we are constantly from present state 0
to 1 so all the 0 to 1 transition see
here here you have here also you have
right
okay so ghost is that means basically
when the crock Falls then at this
instant okay we are saying at this
instant we have said the output earlier
was 0 now it becomes 1 suppose I have
another waveform okay for indicating the
H 0 and H 1 it will look somewhat like
this okay it is
that falls that's what it is that is
until this time h0 was generated at this
instant have zero Bo's and H one is
generated that's what it means
okay now pay some attention to this
because you're dying with H one hit zero
and we are also talking about level one
less zero okay basically it's nothing
but its complement of the other one zero
is complement of one and so here also
you will find the waveforms is
complement okay can work it out now
let's see I said during this transition
edge the input sensed so internally at
this instant itself there was a change
in the state but the output as far as
the output is concerned no change it
continued to be generated as hit zero
now we may even say that this duration
corresponds to up to this it corresponds
to state eh up to this from here to here
it cuz monster state B that is this
right that's what it is okay now what
about do i J
suppose if it continues and falls on the
other hand suppose after this instant
okay
it's after this instant that when
actually the inputs would have been
sensed suppose it had gone but fallen
here now there are two situations in
follow this wait continues for some more
time whereas here YJ false now the
change in the input really does not
affect that in fact is the principle of
the master slave okay component that's
the main thing so the inputs are sense
at a particular instant and outputs are
generated at a different intent but of
course the instant nerves related by the
clock okay it's not arbitrarily
different
so if whether J had changed as shown
here all as shown here it does not
affect the output look now continuing
now we are in a state the present state
in which we have okay we as we see we
are in a state si in which the output
one is generated so this corresponds in
the chart for the present state being
one so like we worked out for the
present state 0 now take a look at it
the present state is 1 the next state is
1 in this present state is 1 the next
state is 0 okay now you can just see
there is some way in other words we say
there is a transition from present state
1 to next state which is also 1 which
means the state continues really right
now 1 to 0 there is a transition now you
can see K is 1 because of K
being one there is a transition from one
to zero when K was one as in this case
there is no transition we know that K is
reset input right good now what about
this case again one to one so K is zero
now come compare this particular one
with this they here we have one-to-one
transition and here also we are
one-to-one translation now in both K is
0 J is 0 in one case one that is talking
about this one in the other case so
whether J is 0 or 1 that is irrespective
of J when K becomes when K is 0 okay 1 2
1 that is it continues J it does not
depend on J now see this 1 to 0
transition K is 1 J is 0 now here again
1 to 0 transition now in both the case
you can see that is 1 to 0 transition
here 1 to 0 transition here in this 1 to
0 transition you have K is 1 in this 1
to 0 transition also is case 1 now in
this okay for this transition J is 0
whereas for this transition J is 1 that
means it does not depend on G agreed so
and 1 to 0 transition that is in a state
when we have the output h 1 when it has
to go to another state in which it has
to generate output 0 it's not going to
depend on J like what we had earlier
similar okay let's see it's something
like what you might call a symmetrical
so now I can sort of complete these a
some charts by adding this condition say
English YK is the only one that must be
sensed and now for master slave
flip-flop master slave principle
I also add this signal we see right as
long as it is zero the present state in
which one is generated continues when it
becomes one that is when K becomes one
then shall I check the chart again when
K becomes one what's happening when K
that is we are talking about the present
state one in this fiscal state when K is
zero now in the present state 1 K is 1
so this is 1 now we see that 1 to 0 it
may transit now in this present state 1
K is 0 so output is still 1 now on the
other hand in this present state 1 there
is transition to 0 because K is 1 right
so 1 to 0 transition takes place again
let's see the chart 1 to 0 transition
takes place when K is 1 so in case 1 the
straight transition must take place but
as per the master/slave thing only
internal change may take place output
should not change so again similar to
the previous one we have a state change
safe of C to D but the output will
continue to be 1 H 1 well as before
check
for this change of C because the input K
was sensed in the racing edge now the
corresponding output change will take
place when it falls to zero
so as long as the clock is 1 sorry as
long as the clock is 1 it continues in
the same state generating that output is
what it means when the cloud falls to 0
then we have a state transition from
state D to yay when D output also
changes over now you can see that ASM
chart describes the behavior of the
entire machine want to take a look at in
the present state 0 in the present state
in which the output is 0 J when it
becomes 1 ultimately to lead to a state
transition so that output generator will
be 1 but that depends on the condition
of the clock when the flip-flop is in
state so there it generates an output 1
depending on K when it becomes 1 there
will be change in the output to 0 again
that depends on the clock so actually
combining this short information
whatever we have in which only the J and
K had been given plastic clock which I
had given you we have worked out the ASM
chart of this master slave flip-flop
right
so everything that you find in this
chart you can verify sorry everything
that you find in this table that is
excitation table okay you can verify
that that particular thing is satisfied
when you follow the various paths in the
ASM chart instantly when you go from one
state to another state that particular
thing is called a path it's also called
a link path ok yeah link path for
instance let's work it out for the
present state yay
there are two link pots right there are
two link posts what are they for the
present state a you have one link path
that is which takes it back to a another
link path which takes it to which takes
the system to state B in other words we
say 40% state a there is one state
transition that is possible which is H
VA itself now that is one link path the
other link path is state transition ei
to be there are two parts here
right a to a this is one possible
transition a to B is another transition
there are two possible transitions in
this good and whatever they change in
whichever path you follow it so happens
in this the output doesn't change that
doesn't matter okay so that's because of
the master sleep and support we had
introduced now like this in present
state a now let us describe the behavior
of the system now this is an example we
took right I'll completely explain now
in percent state a generate output head
zero and look for the inputs YJ and YC
if YJ and YC is zero note state
transition if YJ we see where one there
is a state transition from A to B so one
for this present state a there are two
possible next States in one case it's a
in another case it is B and output
generated in both the cases happen to be
hit zero okay that's as far as the
output part of it so here you have this
link shots which in fact give you or the
link was actually talking about the next
state this is your present state we are
talking about right
there's the present state in system to
some state from this present state we
are talking about - next stage
and as if as I was telling you yesterday
or the previous lecture we have your
false next state and the true next state
right we have arranged it that there are
only two paths to but so it so happens
that the false next state is a and the
true next state is be fine and that is
as far as the next state is concerned as
far as the output is concerned is
nothing much you can see that in state a
right or in state B whatever with that
the output that is generated is h0 right
that's what we had but here that's what
you have written there well there is
another thing that is the input or the
conditions which must be tested right
that is given the present state a the
inputs that must be tested or the
conditions of YJ and YC these are the
two inputs even though the system has
three inputs in state a two of the three
inputs must be tested that's what it
says Kate doesn't matter because that's
how the behavior of the system is good
now we almost got say I think I'll
create one field sorry one what we may
call as micro instruction word right
because that's what it is basically that
is for a given present state e then test
okay check the conditions of YJ and we
see now the next state just because
there are two truenicks sorry - next
case no it is one is true next stage and
the other is selfs false next state so I
have to record that here so the true
next state is this false next state is
this so the true next state for the
present state a it is B and the false
next state is a and the output that must
be gently stir in this particular one it
must generate hits zero
right the same thing again put in a
slightly different form that is I can
say the system has three inputs wage a
YC + y.k
what I'll do it for the present state a
ok for the present state a the system
has YJ YC + YK off h YJ and YC must be
tested in present state a YK need not be
tested the next state the two next
States of a is B I'm just writing the
same thing down and the false next state
of the present state is a and among the
outputs that must be generated we have
to H 0 and H 1 of H in present state a
h0 must be generated and H 1 is not to
be generated
agreed now what did we start with we
started with a flip-flop and started
saying it hurts two states essentially
and then depending on the state in which
it is it generates a 0 or 1 output right
for generating a 0 or a 1 essentially
you need your two state machine just two
states but what is it that we are having
you are having a four state machine why
is it mainly because we are introduced
the master slave team because of that we
have four states now here we have a four
state machine and we have three inputs
to be checked and two output to be
generated so with this we will try to
see what is a micro program control and
watch the hardware control okay easy for
us to
discuss and deal with good now because
there are four states I can now
implement okay the memory a memory
element in the state machine okay
remember what is it we are talking about
the state memory right go back to the
and recall this general a state machine
model we had a state memory right which
is the one which holds all the states
and here we have four strips so that
particular memory element must be either
in a or B or C or indeed that's what it
means at any time the machine is only
one of the states so for representing
four states you need at least two memory
elements right to memory cells that's
why so if I call this memory elements as
a and B then this these two memory
elements can be either in 0 0 or 0 1 or
1 0 or 1 1 States so there are four
possibilities memory any specific memory
element will be either in 0 or 1 so in
two memory elements we can represent the
whole thing right so since this is a
four state machine we need two memory
elements and I'll have them in so
calling them a B and C D ok that's using
the lower case now I'll be having two
memory elements and call these as state
variables okay these are two variables
capital A and capital B which represent
the states of the mission our arbiterly
I Willis assume zero zero at the port
for state a and zero one for the state B
I said arbitrary okay one one for state
C and one zero for state D so I just
arbitrarily as you there are four
possibilities so 0 0 0 1 1 1 and 1 0
game though I said arbitrary there is
some reason for this will not go into it
at this stage so now here I can rewrite
I can go back to this instead of yay
what is it we have instead of yay I can
write the code 0 0 that is my blissful
state instead of a I am writing 0 0
instead of be alright 0 1 good now here
okay
here how they enter information for the
present states a the code of which is
zero zero right so what it says is in
state zero zero look for input so AG and
we see that's what this one says look
for input so AG and we see and depending
on the input test result being true the
next state is 0 1 if it is false the
next state is 0 0 and in the present
state 0 0 generate the output at 0 so
this word okay
this word the entire thing is giving me
information about all the linked paths
there are only two though all the link
paths for the present state right so
exchange go to state B or code similarly
go to state C or code similarly go to
state B or code similarly and we have
talked about the entire system so with 4
such words we have the whole behavior of
this master slave JK flip-flop system
completely defined and that information
then it's given to the controller we are
actually implementing the flip-flop
itself set a particular element itself
agree so we'll continue further on with
this in the next lecture
[Music]
[Music]
[Music]
[Music]
[Music]
[Applause]
[Music]
you