Page 172 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Unit 10: Clocked Sequential Circuits

Table 10.4: State Table After Reduction Notes

Next state Output
Present state
x = 0 x = 1 x = 0 x = 1
a a b 1 1
b c d 1 1
c a d 1 1
d e f d 1 0
e a f d 1 0
f g e f 1 0
g a f 1 0
10.2.2 States Assignment

When constructing a state diagram, variable names are used for states as the final number of
states is not known a priori. Once the state diagram is constructed, prior to implementation (using
gates and flip-flops), we need to perform the step of ‘state reduction’. The step that follows state
reduction is state assignment. In state assignment, binary patterns are assigned to state variables.

Table 10.5: Possible State Assignments
State Assignment 1 Assignment 2 Assignment 3
a 001 000 000
b 010 010 100
c 011 011 010
d 100 101 101
e 101 111 011
For a given machine, there are several state assignments possible. Different state assignments
may result in different combinational circuits of varying complexities.
State assignment procedures try to assign binary values to states such that the cost (complexity)
of the combinational circuit is reduced. There are several heuristics that attempt to choose good
state assignments (also known as state encoding) that try to reduce the required combinational
logic complexity, and hence cost.
As mentioned earlier, for the reduced state machine obtained in the previous example, there can
be a number of possible assignments. As an example, three different state assignments are shown
in the Table 10.5 for the same machine.
We use ad-hoc state assignments in this lesson.
10.2.3 Design with Unused States

There are occasions when a sequential circuit, implemented using ‘m’ flip-flops, may not utilize
all the possible 2 states.
m
Table 10.6: Reduced Table with Binary Assignments

Next state Output
Present state
x = 0 x = 1 x = 0 x = 1
a a b 1 1
b c d 1 1
c a d 1 1
d e d 1 0
e a d 1 0

LOVELY PROFESSIONAL UNIVERSITY 167