Page 177 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Digital Circuits and Logic Design

Notes state diagram that the number of states used is the minimum possible (FSMs for counters are
good examples). For more complex FSMs, it is likely that an initial state diagram may have more
states than are necessary to perform a required function.
10.4.1 State Equivalence

Definition: Two states Si and Sj are equivalent if and only if for every possible input sequence,
the same output sequence will be produced regardless of whether Si or Sj is the initial state. If an
input w = 0 is applied to an FSM in state Si and the FSM transitions to state Su, then Su is termed
a 0-successor of Si. Similarly, if w = 1 and the FSM transitions to Sy, then Sy is a 1-successor of
Si. The successors of Si are its k-successors. With one input, k can only be 0 or 1, but if there are
multiple inputs then k represents all the valuations of the inputs.
10.4.2 Partitioning Minimization

Definition: A partition consists of one or more blocks, where each block comprises a subset of states
that may be equivalent, but the states in one block are definitely not equivalent to the states in
other blocks. From the equivalence definition, if Si and Sj are equivalent then their corresponding
k-successors are also equivalent. Using this, we can construct a minimization procedure that
involves considering the states of the machine as a set and then breaking that set into partitions
that comprise subsets that are definitely not equivalent.
of Partition minimization.
Consider the following state Table 10.9.

Table 10.9: State Table of Partition Minimization

Next state Output
Present state
w = 0, w = 1 Z
A B C 1
B D F 1
C F E 0
D B G 1
E F C 0
F E D 0
G F G 0
An initial partition contains all the states in a single block P = (ABCDEFG)
1
• The next partition separates the states that have different outputs P = (ABD)(CEFG).
2
• Now, consider all 0- and 1-successors of the states in each block.

 For (ABD), the 0-successors are (BDB).
Since, these are all in the same block we must still consider A, B, and D equivalent.
 The 1-successors of (ABD) are (CFG).
We must still consider A, B, and D equivalent.
 Now consider the (CEFG) block.
• P = (ABD)(CEFG).
2
• For (CEFG), the 0-successors are (FEFF) which are all in the same block in P .
2
 C, E, F, and G must still be considered equivalent.
• The 1-successors of (CEFG) are (ECDG).

172 LOVELY PROFESSIONAL UNIVERSITY