Page 179 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Digital Circuits and Logic Design

Notes The number of gates needed to implement a sequential logic network is usually dependent upon
the assignments of possible state variable values to states. Unfortunately, the only way to obtain
the best possible assignment is to try every choice for encoding, which is tedious (but possible)
for small state diagrams and effectively intractable for complex state machines. Luckily, heuristics
have been developed that provide “reasonably good” state assignments “most of the time”.
10.5.1 State Maps

State maps, similar in concept to k-maps, provide a means of observing adjacencies in the state
assignments. The squares of the state maps are indexed by the binary values of the state bits; the
state given that encoding is placed in the map square. Obviously the technique is limited to the
situations in which k-maps can be used, that is, up to six variables.
Figure 10.14: State Maps

The above Figure 10.14 presents an ASM chart for the finite state machine.
Table 10.11: First State Assignment

State name Q2 Q1 Q0
S0 0 0 0
S1 1 0 1
S2 1 1 1
S3 0 1 0
S4 0 1 1

Table 10.12: Second State Assignment

State name Q2 Q1 Q0
S0 0 0 0
S1 0 0 1
S2 0 1 0
S3 0 1 1
S4 1 1 1

174 LOVELY PROFESSIONAL UNIVERSITY