

CS302 
Digital Logic & Design
Lesson
No. 33
STATE
ASSIGNMENT
Each
state in a sequential circuit is
identified by a unique combination of
binary bits.
Unless
the output of the sequential
is directly taken form the
flipflop outputs such as
counters,
the
states can be selected to
allow minimum bit changes
when changing from one
state to the
other.
Keeping the bits changes to
minimum when changing from
one state to the next,
results
in simpler
combinational circuits that
determine the next state.
Consider the example
discussed
earlier having states a, b, c, d
and f. Since we are
interested in only the input
and
output
sequence, therefore it is immaterial
how states a, b, c, d and f
are uniquely
identified.
Three
possible state assignments
are shown. Table 33.1.
The NextState, flipflop
input tables
for
the three state assignments
are shown. Table 33.2,
33.3 and33.4.
State
State
State
State
Assignment
1
Assignment
2
Assignment
3
a
000
001
000
b
001
010
001
c
010
011
011
d
011
100
010
f
100
110
110
Table
33.1 Three possible state
assignments for states a, b, c, d
and f
Present
Next
State
D flipflop
Inputs
Output
State
X=0
X=1
X=0
X=1
X=0
X=1
000
100
001
1000010
0
001
001
010
0010101
1
010
000
100
0001000
1
011
010
011
0100111
0
100
011
010
0110100
0
Table
33.2a Next State
flipflop input table for
first State
Assignment
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
0
1
0
00
1
0
0
0
01
0
0
1
1
01
0
1
0
0
11
x
x
x
x
11
x
x
x
x
10
1
1
x
x
10
0
0
x
x
D 2 = Q 2 Q1 Q 0 x + Q1 Q 0 X
D1 = Q 2 + Q 0 X + Q1Q 0
Q2Q1/Q0X
00
01
11
10
00
0
1
0
1
01
0
0
1
0
11
x
x
x
x
10
1
0
x
x
D0 = Q 2 Q 0 X + Q1Q 0 X + Q1Q 0 X + Q 2 Q1 Q 0 X
Table
33.2b
Karnaugh
Maps and D flipflop input
Boolean expressions for the
first State
Assignment
335
CS302 
Digital Logic & Design
Present
Next
State
D flipflop
Inputs
Output
State
X=0
X=1
X=0
X=1
X=0
X=1
001
110
010
11
0
01
0
0
0
010
010
011
01
0
01
1
1
1
011
001
110
00
1
11
0
0
1
100
011
100
01
1
10
0
1
0
110
100
011
10
0
01
1
0
0
Table
33.3a
Next
State flipflop input table
for second State
Assignment
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
x
x
1
1
00
x
x
0
1
01
1
1
1
0
01
0
0
1
0
11
0
1
x
x
11
1
0
x
x
10
1
0
x
x
10
0
1
x
x
D 2 = Q 2 Q1 x + Q1Q 0 X + Q 2Q1 X + Q 2 Q1 X
D1 = Q 2 Q 0 + Q1Q 0 + Q1 X + Q1 X
Q2Q1/Q0X
00
01
11
10
00
x
x
0
0
01
0
1
0
1
11
0
1
x
x
10
1
0
x
x
D0 = Q 2 Q1 X + Q1 Q 0 X + Q1Q 0 X
Table
33.3b
Karnaugh
Maps and D flipflop input
Boolean expressions for the
second State
Assignment
Present
Next
State
D flipflop
Inputs
Output
State
X=0
X=1
X=0
X=1
X=0
X=1
000
110
001
11
0
00
1
0
0
001
001
011
00
1
01
1
1
1
011
000
110
00
0
11
0
0
1
010
011
010
01
1
01
0
1
0
110
010
011
01
0
01
1
0
0
Table
33.4a
Next
State flipflop input table
for third State
Assignment
336
CS302 
Digital Logic & Design
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
1
0
1
0
00
1
0
0
0
01
1
1
1
0
01
0
0
1
0
11
1
1
x
x
11
0
0
x
x
10
x
x
x
x
10
x
x
x
x
D 2 = Q1 Q 0 x + Q1Q 0 X
D1 = Q 0 x + Q 0 X + Q1 Q 0
Q2Q1/Q0X
00
01
11
10
00
0
1
1
1
01
1
0
0
0
11
0
1
x
x
10
x
x
x
x
D0 = Q 2Q1 Q 0 x + Q 2 X + Q1Q 0 + Q1 X
Table
33.4b
Karnaugh
Maps and D flipflop input
Boolean expressions for the
third State
Assignment
The
third State Assignment is
shown to have simpler input
Boolean expressions
leading to a
simpler combinational circuit.
Generally, the selection of
State Assignment is
based on
the following
guidelines.
· Choose an
initial coded state into
which the state machine
(sequential circuit) can
easily be
forced to
reset (000 or 111)
· Minimize
the State Variables that
change on each
transition
· Maximize
the number of state
variables that don't change
in a group of related
states
· If there
are unused states, then
choose the best state
variable combinations to achieve
the
first
three goals.
Moore
Machine
State
Diagram
The
state diagram of a Moore
Machine is shown. Figure
33.1. The Clocked
Synchronous
Sequential Circuit has six
states. On each clock
transition the
machine
sequences
through the states 011,
111, 001, 010, 100
and 110. The outputs of
the flipflops
represent
the sequential circuit
output.
337
CS302 
Digital Logic & Design
Figure
33.1
State
diagram of a Moore
Machine
NextState
Table
The
NextState table is derived
from the State diagram.
The present and
the
corresponding
next states to which the
sequential circuit changes at
each clock transition
are
shown.
Table 33.5
Karnaugh
Maps
The
flipflop input table based
on JK flipflops is shown.
Table 33.6. JK
flipflop
transition
table is used to determine
the JK flipflop inputs.
The Karnaugh maps for
each of
the
three J and K inputs of the
three JK flipflops are
shown along with the
Boolean
expressions.
Table 33.7
Present
State
Next
State
Q2
Q1
Q0
Q2
Q1
Q0
0
1
1
1
1
1
1
1
1
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
0
0
1
1
Table
33.5
NextState
table of the Moore
Machine
Present
State
Next
State
JK
flipflop inputs
Q2
Q1
Q0
Q2
Q1
Q0
J2
K2
J1
K1
J0
K0
0
1
1
1
1
1
1
x
x
0
x
0
1
1
1
0
0
1
x
1
x
1
x
0
0
0
1
0
1
0
0
x
1
x
x
1
0
1
0
1
0
0
1
x
x
1
0
x
1
0
0
1
1
0
x
0
1
x
0
x
1
1
0
0
1
1
x
1
x
0
1
x
Table
33.6
JK
flipflop input table for
the Moore Machine
338
CS302 
Digital Logic & Design
Q2Q1/Q0
0
1
Q2Q1/Q0
0
1
00
x
0
00
x
x
01
1
1
01
x
x
11
x
x
11
1
1
10
x
x
10
0
x
J2 = Q1
K 2 = Q1
Table
33.7a
Karnaugh Map
for J2 and K2 inputs
Q2Q1/Q0
0
1
Q2Q1/Q0
0
1
00
x
1
00
x
x
01
x
x
01
1
0
11
x
x
11
0
1
10
1
x
10
x
x
J1 = 1
K1 = Q 2 Q 0 + Q 2Q0
Table
33.7b
Karnaugh Map
for J1 and K1 inputs
Q2Q1/Q0
0
1
Q2Q1/Q0
0
1
00
x
1
00
x
x
01
x
0
01
0
x
11
x
0
11
1
x
10
x
x
10
0
x
J0 = Q 2Q1
K 0 = Q1
Table
33.7c
Karnaugh Map
for J0 and K0 inputs
Implementation
The
circuit and timing diagram
of the State Machine is
shown. Figure 33.2.
The
sequential
circuit is assumed to be reset to
state 011. At interval t1, JK input of the
first flipflop
is set at 0
and 0 respectively; therefore at
the clock transition the
output of the first
flipflop
remains
unchanged. The J input of
the second flipflop is
permanently connected to logic
1,
the K
input is set at logic 0,
therefore the output of the
second flipflop is set to
logic 1 at the
clock
transition t1.
The JK input of the
third flipflop is set to
logic 1, at clock transition
t1 the
output of
the flipflop changes to
logic 1. The operation of
the sequential circuit can
be similarly
verified
for intervals t2 to t7.
339
CS302 
Digital Logic & Design
Figure
33.2a Implementation of the
Moore Machine
Figure
33.2b Timing diagram of the
Moore Machine
Mealy
Machine
State
Diagram
The
sequential circuit represented
earlier as a Moore Machine is
described as a Mealy
Machine.
Figure 33.3. The output of a
Mealy machine depends upon
the present state at
the
inputs.
The state diagram shows
the six states. When
the input is 1, the machine
switches
from
its present state to the
next. If the input is 0, the
machine remains in its
present state. The
outputs of
the machine when it switches
to the next state or it
remains the present state
are
shown
with the directed arrows.
For, example at state `a',
when the input is 1 the
machine
changes to
the next state and
the output is set to 111.
When the input is set at 0,
the machine
remains in
its current state with
outputs 011.
340
CS302 
Digital Logic & Design
Figure
33.3
State
diagram of a Mealy
Machine
NextState
Table
The
NextState table for the
Mealy Machine is shown.
Table 33.8. The NextState
table
is directly
derived from the State
diagram. The present state,
and the corresponding next
state
when
the input X=0 and
X=1 are shown in separate
columns respectively. Similarly,
the Moore
Machine
outputs are also shown
for each present state
when the inputs are
X=0 and X=1
respectively.
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
a
a
b
011
111
b
b
c
111
001
c
c
d
001
010
d
d
e
010
100
e
e
f
100
110
f
f
a
110
011
Table
33.8
NextState
table of a Mealy
Machine
State
Assignments
Based on
the guidelines for State
Assignment, States are
assigned keeping the
bit
changes to
minimum. The corresponding
next states for input
X=0 and X=1 are
also shown.
Table
33.9.
Present
Next
State
State
X=0
X=1
000
000
001
001
001
011
011
011
010
010
010
110
110
110
100
100
100
000
Table
33.9
State
Assignments for the Mealy
Machine
341
CS302 
Digital Logic & Design
Karnaugh
Maps
The
JK flipflop input tables
for the Mealy Machine
are shown. Table 33.10.
The JK
inputs
for the three flipflops
are based on the JK
flipflop transition
tables.
Present
Next
State
JK
flipflop inputs
Output
State
X=0
X=0
X=0
Q2 Q1
Q0 Q2 Q1 Q0
J2
K2
J1
K1
J0
K0
O2
O1
O0
0
0
0
0
0
0
0
x
0
x
0
x
0
1
1
0
0
1
0
0
1
0
x
0
x
x
0
1
1
1
0
1
1
0
1
1
0
x
x
0
x
0
0
0
1
0
1
0
0
1
0
0
x
x
0
0
x
0
1
0
1
1
0
1
1
0
x
0
x
0
0
x
1
0
0
1
0
0
1
0
0
x
0
0
x
0
x
1
1
0
Table
33.10a JK flipflop input
table for the Moore
Machine (X=0)
Present
Next
State
JK
flipflop inputs
Output
State
X=1
X=1
X=1
Q2 Q1
Q0
Q2 Q1
Q0
J2
K2
J1
K1
J0
K0
O2
O1
O0
0
0
0
0
0
1
0
x
0
x
1
x
1
1
1
0
0
1
0
1
1
0
x
1
x
x
0
0
0
1
0
1
1
0
1
0
0
x
x
0
x
1
0
1
0
0
1
0
1
1
0
1
x
x
0
0
x
1
0
0
1
1
0
1
0
0
x
0
x
1
0
x
1
1
0
1
0
0
0
0
0
x
1
0
x
0
x
0
1
1
Table
33.10b JK flipflop input
table for the Moore
Machine (X=1)
The
Karnaugh maps for the
three sets of JK inputs
and the three outputs
are shown.
The
Boolean expressions are
written along with the
Karnuagh maps. Table
33.11
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
0
0
0
00
x
x
x
x
01
0
1
0
0
01
x
x
x
x
11
x
x
x
x
11
0
0
x
x
10
x
x
x
x
10
0
1
x
x
J2 = Q1 Q 0 X
K 2 = Q1 X
Table
33.11a Karnaugh Map for J2 and K2
inputs
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
0
1
0
00
x
x
x
x
01
x
x
x
x
01
0
0
0
0
11
x
x
x
x
11
0
1
x
x
10
0
0
x
x
10
x
x
x
x
K1 = Q 2 X
J1 = Q 0 X
Table
33.11b Karnaugh Map for J1 and K1
inputs
342
CS302 
Digital Logic & Design
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
1
x
x
00
x
x
0
0
01
0
0
x
x
01
x
x
1
0
11
0
0
x
x
11
x
x
x
x
10
0
0
x
x
10
x
x
x
x
J0 = Q 2 Q1 X
K 0 = Q1 X
Table
33.11c Karnaugh Map for J0 and K0
inputs
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
1
1
0
1
00
0
1
0
1
01
1
0
1
0
01
0
1
0
0
11
0
1
x
x
11
1
1
x
x
10
1
1
x
x
10
1
0
x
x
O 2 = Q 2 X + Q 2Q1 + Q 2 Q 0 X + Q1Q 0 X
O1 = Q1Q 0 X + Q 2 Q 0 X + Q 2 X + Q1 Q 0 + Q1 X
Q2Q1/Q0X
00
01
11
10
00
1
1
1
1
01
0
0
0
1
11
0
0
x
x
10
0
1
x
x
O 0 = Q1 X + Q 2 Q1 + Q 0 X
Table
33.11d Karnaugh Map for O2, O1 and O0 outputs
Implementation
The
implementation of the Mealy
Machine is shown. Figure
33.4. The circuit
shows
only
the part of the circuit
that allows the Mealy
Machine to switch from its
current state to the
next
state. The operation of the
machine can be verified with
the help of the timing
diagram.
343
CS302 
Digital Logic & Design
X
Q0
Q1
Q2
SET
SET
SET
Q
Q
Q
flipflop
1
flipflop
2
flipflop
3
Q
Q
Q
CLR
CLR
CLR
CLK
Figure
33.4a Implementation of the
Mealy Machine
The
machine is assumed to be reset to
state `a' 000. At interval
t1, JK inputs of
the first
flipflop
are set at logic 1 and 0
respectively, therefore at the
clock transition the output
of the
first
flipflop switches from 0 to 1.
The JK inputs of the
second flipflop are set at
logic at logic
0 and 0
respectively, thus the
output state of the second
flipflop remains unchanged at
the
clock
transition. The JK inputs
of the third flipflop are
set to logic 0 and 1
respectively, thus at
clock
transition t1
the
flipflop is reset to logic 0.
Transition at intervals t2 to t7 can similarly
be
verified.
CLOCK
Input
Q0
Output
Q1
Output
Q2
Output
t2
t3
t4
t5
t6
t7
t8
t1
Figure
33.4b Timing diagram of the
Mealy Machine
The
circuit which implements the
Mealy Machine outputs has
not been shown.
The
machine
outputs are implemented
through the three Boolean
expressions for outputs O2, O1
and
O0 respectively. At
interval t1,
before the clock transition,
Q0, Q1 and Q2 outputs are set
at
logic 0, 0
and 0 respectively. When the
X input is logic 0, the
output of Boolean expression
for
344
CS302 
Digital Logic & Design
O2, O1 and O0 is 0, 1 and 1 respectively. At
the clock transition t1 when the X input is
set to 1,
the
output O2, O1 and O0
is set to 1, 1
and 1. The outputs for
all six states `a',
`b', `c', `d', `e'
and
`f' can
similarly be verified.
345
Table of Contents:

