Page 574 - Engineering Digital Design

544 CHAPTER 11 /SYNCHRONOUS FSM DESIGN CONSIDERATIONS

take logic 1. For K-map evaluations, the don't cares are treated as don't cares. However
evaluated, the results for the six state adjacency sets in the function matrix are

de = m(4, 5,6, 7) = A, bd = m(l, 5) = BC, e = ^m(4, 6) = AC,

(2,3,6,7) = B
abc = m(0, 1,2,3) = A, bed = ^m(l, 3, 5, 7) = C,

bcde = m(l, 3, 4, 5, 6, 7) = A + C,

all of which must be substituted into Eq. (11.12) before proceeding. Again, to use the Q-M
algorithm in evaluating the six adjacency sets just presented, care must be taken to include
the three don't cares 0(2, 6, 7) as minterms ra(2, 6, 7) in each set, if they are not already
included. Thus, for use with the Q-M algorithm, the adjacency sets become

2,4, 5, 6, 7), bd = m(l, 2, 5, 6, 7), e = m(2,4, 6, 7),
c = ^m(2, 3,6,7)

= ]Tm(0, 1, 2, 3, 6, 7), fccrf = £m(l, 2, 3, 5, 6, 7),

which will yield the same results as given previously. Because of the simplicity of the
adjacency set minimization process, the Q-M algorithm is quite suitable for CAD purposes
even for relatively complex state machines. However, most any minimization algorithm is
suitable for this purpose as, for example, BOOZER bundled with this text.
After making the appropriate substitutions into Eq. (11.12), the next-state functions can
be evaluated. This is done by multiplying the function matrix F Ns by the input matrix I to
yield the following next-state function matrix NS:

A BC AC (A + C)' D A
NS = F NSI = 0 B C 0 D B (11.13)
A C C 0
/, ° C

By carrying out the indicated matrix multiplication, there result the NS equations

D A = A/o + BCh + AC/3 + (A + C)/ 2
= AST + BCST + ACST + AST + CST

D B = £/i + C/ 3
= BST + CST
D c = A/o + C/] + C/3