ID.
Jtequential Circuits (Finite State Machines)
~ lilfJ'.R; l,11ut!lf-•BmEJ
ll§11 •■;;[Link]•Sl 1NBWWw
. .
nre•ra•,w•
. k, I flip
-• --.. -·- - ---
flop~ arc u-;ed
• In synchronous or clocked st•qut•nl1i1 1 circt11b, c 1lll < t
. . . . , in synchronism with th
memor) elements, which ch,1ngl' lht'IJ' mdl\ 1d1w 1 st,1lt s
penodic clock signal.
· ·t \le of the entire c
• Therefore, the change in states of flip-flops and ch,1ng<' tn ~ ' u1t
occurs at the transition of the clock signal.
• The states of the output of the flip-flop in the sequential circuit gives th e st at f
the sequential circui_!,...,....
Present state : The stah1s of all state variables, at some time t, before th e next cock
edge, represents condition called present state.
Next state : The status of all state variables, at some time, t + 1, represents a condition
called next state.
The synchronous or clocked sequential circuits are represented by tvvo models.
• Moore model : The output depends only on the _Eresent state of the flip-flops.
• Mealy model : The output depends on both the present state of the flip-flop(s)
and on the input(s).
-----------
1:111 Moore Model
• When the output of
the sequential X
circuit depends only
on the present state
of the flip-flop, the
CP----l'II
0
0
sequential circuit is
y
referred to as
Moore model. Fig. 8.1.1 Example of Moore model
• Let_ us see one example of Moore model. Fi . 8.1 1 r . • •
which consists of two JI< flip-fl d g · sho¼ s a sequential c1rcmt
one output Y. ops an AND gate Th · · h as one input
· e circtut X and
• ~s shown in the Fig. 8.1.1, input X is used to .
flip-flops. It is not used to determi th deternune the inputs o
ne e output The tp .
present states of the flip-flops or b. . . ·. ou ut 1s dern ed us n
com mation ot it (in this c y
• In general form the Moore model can be ase Q \Q
hown m Fig. 8.1.2. represented with its blo<. k
1neviJ ,.,,.. - ~•" ~'!I" 8-3
~ - -- ----------=---------~S~e~q~ue~n~tia!l~C ~irc~u'!!:_lts~-!!_11
Egttaiiiiiillition Variables
. - - -........
~ - - ~...........-&'.~
[
1nrut
vanables l-·-.... .._
• "'1lt
decoder
Output
variables
State variables
Fig. 8.1.2 Moore circuit model with an output decoder
llfl Mealy Model
, ·when the output of the sequential circuit depends on both the present state of
flip-flop(s) and on the input(s), the sequential circuit is referred to as Mealy
model.
, Fig. 8.1.3 shows the sample Mealy model. As shown in the Fig. 8.1.3, the output of
the circuit is derived from the combination of present state of flip-flops and
input(s) of the circuit.
'
)(
X JA QA
CP
0
1 KA 'Ci'A 0 Ks
y
Fig. 8.1.3 Example of Me,'Y model
• Looking at Fig. 8.1.3, we can easily realize that, changes in the input · •
-
clock pulses can not affect the state of the flip-flop. However, they c
output of the circuit.
• Due to this, · · ut variations are not synchronized
derived output will also n .......,;i;,,__ wt
QUtput (as it is a synchrono •
The false outputs can be • - -- · in
transition of the clock
8•4
itching Theory and Logic Design
Excitation
1111'!■.!..,""'I variables ---- ...- ---~ •
Inpu t~
variabl~ Memo ry
----,& elernents
State variables
Fig. 8.1.4 Mealy circu it mode l
1y circuit Mod8l9
resentalon of Sequential 8lrcUla
State Diagram
..,1...,c1rcult
• State ciiagram is a pictorial RIO.a•
behaviour ef a sequatial,
shows a state dia~
• D.e state is repasented by tbe
tmaeitien between states• ·
l i n e s ~ the drdea.
. .ameied line connectiDg I 111ld._,~•
.~.lliClltes that next state 18
adal,le .
input
..-i11e during the present
ThOO!Y nnd Logic Design
,51\ /I g - - - - - - -=---- ---1J. __._5 Soq11ent1sl Clrcwls II
Moore circuit
for f M
, In case o oore cirt uit, the di rec d lmc
nre labelled with only one binary
nun1lwr
rcprc,cnting the state of the mput th
t C<lllSt.'S
the c;tate trnns1hon.
, The (nttput stnt(;• 1s mdk,1tcd w·l tiW
circle, belClw tlw prt•scnt stt1tc becaus output
t·
)tn
(l
state depl·nds cmly on present state nd not
t)l1 thl' rnput.
, F•~· S.1.6 ~hows the state diagram fo Moore
circuit.
~eTa ble Fig. 8.1.6 State diagram for Moore
circuit
, Representation of state machine usinij·
relationship between input(s) , preseni· Pasent state Next state 0atput
state, next state and the output(s ) iri
the tabular form is known as X=O X=l
table. AB AB
, Table 8.1.2 (a) shows the state table a a C
for the state diagram shown in,
b b a
Fig. 8.1.5.
C d C
, It represents relation ship between
input, output and flip-flop states. d b d
• It consists of three sections labeled! Table 8.1.2 (a)
present state, next state and output. Next state
• The present state designat es the state
X=O X=l
of flip-flops before the occurren ce of a
clock pulse. AB AB
• The next state is state of the flip-flop a C
after the application of a clock pulse, b a
and the output section gives the
d C
values of the output variable s
Table 8.1.2 (b)
during the present state.
• B0th the next state
and output sec ;ions have two columns representing two
possible input conditio ns : X = 0 and X ~ 1.
• In case of Moore circuit the output se tion has only one column since output does
not depend on input. The Table 8.1.2 (b) shows the state table for Moore circuit
Who,e st t d'
a e 1agram is shown in Fig. .1.6.
TECHNICAL PUBLICATIONS An up thrust for l<nowfedg•
l;j(Q Transition Table
• A transitilm table• l,1kes the sl,1lt' l11l 1 h~ ,nw Pr('SC'lll Nt•xt [Link]
Stl'f" fm tlwr. nw statl' di,1g1 ,11\\ ,\l lll s l,ll(' stnt~ I
X o X
i I X 0
tt1hlC' n·prl'Scnt state using ,. , , 1n lHlls or
Hdfilt'S. Al3 y
A B AB
• Tn the transition tabk'
spl'ctfk stale JO 0
() l)
0
variable values arc ,1ssigncd to c,1eh Slalc.
I l 00 0
• Assignment of valul's lo sla te variables is 0 1
called State assignment. I 0 () 1 1
• Like state table transition table also 10 1
represents relationship between input, L.. 1- ~1----=--_o_(_J.,_,1,_ _
output and flip-flop states. Th~ Fig. 8.1.7 Fig. 8.1.7
shows the transition table.
Here, AB arc the state variables. The AB = 00
represents one state, AB = 01 represents second state and so on.
■:l&J Mathematical Representation of Synchronous Sequential Machine
We know that next state of sequential machine depends upon present state s(t) and
present input x(t). The relation between present state, present input and next state can
be given as
s(t+l) = 8{s(t), x(t)}
where s (t +1) is next state and
8 is the state transition function.
The value of output z(t) can be derived as
z(t) = AI s(t), x(t)} ... for Mealy machine and
z(t) = AI s(t)} ... for Moore machine
Because in Mealy machine output depends on both the pre sent state and the input
whereas in Moore machine output depends only on present state.
Review Questions
1. Draw and explain the block diagram of Moore model.
2. Draw and explain the block diagram of Mealy model.
3. Whal ic; a Mealy machine ? Give an example.
. .-... machmes.
4. Wnlt' /hr differenc11s between Mealy and Moon• typ ·
01:c t
-
[Link] IIM GlllflMm .W-,, ,_ -·,,,. ,.,,.. .
•MIi• l't:.-12, May-t:s, [Link]"§ I
MIIIWltypeFSM .JNTU : Mny-09 , Mark.!i
■
...,,. M•ly machin, ,md Moore maLhine.
.IN l l I May-11 , Marlui S
M•ly machtn, with mmple. ,JNllJ M,1y-12 , Marks 8
lffllfNIIIW? bmuten tr1mS1tton table and ot11tc tahle ? ,JNTll April-1 2, Mark1, 6
bllltlea and Limitations ,JNTU: April-1 1, 12. Mr1y-t:i . Nov.-09
. Periodic seque nce of finite states : With n-state machine we can. generate periodic
sequen ce of n states or smalle r than n states. F~r example, in, 5 state machine
we
can have maxim um period ic sequence ~s o, i 2, 3,. 4, 0 1 ... .. ·
1
2. No infinite sequen ce : Consid er an infinite sequence sud:t that an outpu t is 1
when
and only whe~ the numbe r of inputs received so far is equal to. K(K + 1) / 2, for
K = 1, 2, 3., ····· i.e., the desire d input outpu t ·sequence has the ferm.
Input : . X X X ~ X X X X X X. X X X X X X X X X X X
Outpu t : lO.. 1 0 0. 1. O .0 O 1 ooo o 1 o oooo 1 .....
Such infinite sequen ce can not be produ ced by finite state machine.
3. Limited memory. : The finite-state machine has a limited memo ry ~d due
to
limited memo ry _it can not produ ce certain output s. Consid er a binary multip lier
circuit. for multip lying two arl,itrarily large binary numbe rs. If we implem ent this
' ~
with a finite - state machi ne capabl e of perfor ming serial multiplication, we
can
find th~t it is not possib le to multip ly certain numbe rs. Such limitat ion does
occur
due to the limited "memory" available to the mach in~ This memo ry is not
sufficient to store arbitra rily large partial produ cts resulte d. during multiplication.
Review Questi ons
1. Discuss on the capabilities and limitations of finite state machines.
JNTlJ : April-1 1. M.H. 1 :~ l\L., ·,
2. What are the limitations and capabilities of an FSM.
3. Explain the capabilities and limitations of finite state machines.
ID Mealy to Moore Conversion and Vice-Versa
JNTU : Nov.-03, May-05, 13, April-11
Rules to Convert Meaty to Moore Model
1. Ifal] the transitions in a Mealy model to a particular state are associated with only
one type of output (either O or 1) then in corresponding Moore model that output
becomes state output. This is illustrated in Fig. 8.6.l. Here, T1 , T2 and T 3 are the
TECHNICAi. Pl IQ/ /C:AT/QNfs.,. An [Link].£nc-1,...,.,..1, -1
b leads to common state c when inp
·~
not
0~
(a)Moorecil\':fllt
corres nds ·
d
8 87 Soquent,al c,rcu,t fl
RNt fined NS
tat
X 0 X 1
(
Bo
A Do
Do
( B1 A
Do o, (_
o, o, C
- .mple 8.6.2
Table 8.6.1 (a) Table 8.6.1 (b)
nvert the following Moore machine into a corresponding Mealy machine.
JNTU : Nov.-03, May-05, Marks 8
Present Next state Output Z
state
X=O X=l
A D B 0
B B C 1
C C D 0
D D B 0
Solution : Here, states A and D leads to common states when input is same, i.e. when
input is 0, the next state is D and when input
is 1, the next state is B. Thus states A and D Next state / Output Z
are equivalent and we can eliminate either Present
state X=O X=l
state A or state D. For remaining states, next
states are not same for same input. A A/0 Bil
Eliminating state D and writing associated B B/1 C/0
output with each state separated by slash we
C/0 A0
get the Mealy machine equivalent for given
Moore machineI as shown in the Table 8.6.2.
Note that states A and D are equivalent so we Table 8.6.2
can write A in place of D in the next state
column.
TECHNICAL PIJBL/OATIONS AA up thrWt for
sequential Circuits - II
Switching Theory and Logic Design 8- 88
. . .. 'spomiin~ Moore machine.
Example 8.6.3 Convert the following Mealy mach111e 111/0 n collt. ,
PS !
I
NS,Z
X=O X=l
A B, 0 E, 0
B E, 0 D, 0
C D, 1 A, 0
D C, 1 E, 0
E B,O D, 0
JNTU : May-13, Marks 8
Solution : In the given Mealy machine, states A, B, C and E are assosciated wi th only
one type of output.
State A = Output 0
State B = Output 0
State C = Output 1
State E = Output 0
Whereas state D is associated with Therefore, Moore equivalent of given Mealy
output O and 1. machine is given as :
Redefined Output PS NS
state X=O X=l
A 0 A B E
B E Do
C
Di A
Do C E
C ll
E
B Di
Review Question
1. Explain the rules for converting Mealy to Moore model with the h l ,,
e P 01 example and vie,-