Page 576 - Engineering Digital Design

546 CHAPTER 11 / SYNCHRONOUS FSM DESIGN CONSIDERATIONS

output expressions of Eqs. (11.14) are covered by the DA expression. In fact, it is char-
acteristic of the array algebraic approach that most, if not all, of the p-terms in the output
functions will be shared Pis. This is so because the output functions are obtained by using
the same form of the function equation F = Z* • D, where Z is any output function matrix
and D is the destination matrix used in obtaining the NS functions. Notice that reducing
the expression for D A by factoring the terms AST + AST = AT results in a gate/input
tally of 14/41, only a very minor improvement. Generally, in using the array algebraic ap-
proach to design, significant savings in hardware can result by considering all of the factor-
ing/reduction possibilities that exist, particularly within the NS logic expressions. However,
account must also be taken of the shared Pis that might be lost in the factoring/reduction
process.
An inspection of the Q output function in Eqs. (11.14) reveals an externally initiated
static hazard in the coupled terms ACST+AST. This s-hazard can occur on a 1 ->• Ochange
in input T while in state 100 under holding condition S (see Fig. 11.43b). As indicated in
Section 11.3, this hazard can be eliminated either by adding the hazard cover ACS or by
filtering. Note that the p-term ACST can be replaced by AC S in the expression for Q,
thereby requiring no hazard cover. This results from the simplification ACST + AST =
ACS + AST after applying the absorptive law. Note that no hazards exist in the output
functions P or Q of Eqs. (11.11). In any case, since ORGs are possible in both outputs,
they should be filtered thereby eliminating all logic noise — hence no hazard analysis is
needed.
In attempting to automate the design of state machines by the array algebraic method,
the most difficult part, the "bottleneck," is to obtain the state adjacency sets of function
matrix F in terms of the state variables. Fortunately, these problems break up into single-
output minimization problems, as is indicated by the example given earlier, and often can
be easily handled by tabular minimization algorithms such as that of Q-M. But a given
minimization problem can be cyclical in the sense that more than one minimum is possible.
Petrick's algorithm (see Further Reading) can be used to solve simple to moderately complex
problems. On the other hand, an optimum solution may not be necessary, and one of the
minimum solutions for an adjacency set can be arbitrarily chosen on the basis of some
criterion built into the CAD algorithm. Full-blown heuristic-type minimization algorithms
are usually not required for this purpose. However, if needed, none are better for very
large minimization problems than the Espresso-II algorithm briefly discussed in Section
4.8. Included on the CD-ROM bundled with this text is the CAD software called ADAM
(for Automated Design of Asynchronous Machines). This software can also automate the
design of synchronous FSMs with D flip-slops. For more information see Appendix B.
Before leaving this subject, one final thought is worth mentioning. The array algebraic
approach is perfectly general. It can be applied to any FSM, synchronous or asynchronous
that meet the minimum requirements mentioned at the beginning, and to any set of state code
assignments that is used. The results may or may not be optimum, but will be at least near
optimum depending, of course, on the choice of state code assignments. In this section,
the array algebraic method is used to design a synchronous state machine, of moderate
complexity, whose state assignments are obtained by applying state assignment rules 1 and
2 given previously. However, applications of rules 1 and 2 do not eliminate ORGs.
In Section 14.12 the array algebraic method is again used, but to design the fastest
asynchronous FSMs possible, called single-transition-time (STT) machines. For these FSMs