Page 757 - Engineering Digital Design

14.12 SINGLE-TRANSITION-TIME MACHINES 723

Seed sets are useful as a aid in establishing the TT-partitions and may be disregarded for
simple FSMs. Notice that the branching paths within a given seed set contain just one
holding condition state identifier and that all branching paths within the set share a common
branching condition. This is easily seen by comparing each seed set with the state diagram
in Fig. 14.33a. Normally a single state identifier representing a holding condition will not
appear singly within a seed set unless it is not otherwise associated with another state
identifier within the same seed set.
Seed Set IQ = {ab, be, de]
Seed Set I\ = {ae, bd, c}
Seed sets (14.26)
Seed Set 7 3 = {a, be, cd, e]
Seed Set /2 = {a, be, ce, de}
Seed Set /o —>• TZ\ = abc, de
Seed Set I\ —> Jti = ae, bd
Seed Set I\ —>• TT?, = ae, c
Seed Set I\ -^ n 4 = bd, c . . _
\ ^-partitions. (14.27)
Seed Set Ij -> TTS = a, bed
Seed Set /3 —>n( ) = a,e
Seed Set IT, —>• iti — bed, e
Seed Set /2 -> TTg = a, bcde

The TT-partitions are derived from the seed sets in Eqs. (14.26) and are given by Eqs.
(14.27), where state a is taken to be the initialization state in agreement with the state
diagram in Fig. 14.33a. Observe that when present in a given TT-partition, state a always
appears on the left side of the partition (the comma). If it is decided to assign • • • 000 to
state a, then all state identifiers grouped with a on the left side of the partition must also
be assigned logic 0. Accordingly, this requires that all state identifiers on the right side
of the partition be assigned a logic 1. For example, from seed set /o, the TT-partition is
7T] = abc, de for which state identifiers a, b and c all take logic 0 while state identifiers d
and e take logic 1. Notice in particular that the partitions are formed in such a manner that
no state variable appears on both sides of the partition, a requirement for discreteness of the
partition.
Having completed step 3 of the procedure given previously, it is now required by step 4
that the n -partition be collected into r-partitions, each of which must contain all the state
identifiers. This is done and the results are presented in Eqs. (14.28). Observe that there are
eight T-partitions of which five are shown, but only four are necessary to cover all eight
TT-partitions. The choice of the first four T-partitions is made, which constitutes a minimum
set thereby completing step 5. Hence, four state variables are required.
TI = abc, de = n(l, 6)
T 2 = ae, bed = n(2, 3, 5, 7)
13 = ace, bd = n(2,4) n -partitions. (14.28)
T 4 = a, bcde = n(5, 6, 8)
T 5 = abde, c = ?r(3, 4)

The state matrix S can now be established according to step 6 assuming that the initial-
ization state a is assigned all zeros, 0000. If an ascending order of T-partitions is chosen,