Synthesis of Finite State Machines: Logic Optimization is the second
in a set of two monographs devoted to the synthesis of Finite State
Machines (FSMs). The first volume, Synthesis of Finite State Machines:
Functional Optimization, addresses functional optimization, whereas
this one addresses logic optimization. The result of functional
optimization is a symbolic description of an FSM which represents a
sequential function chosen from a collection of permissible candidates.
Logic optimization is the body of techniques for converting a symbolic
description of an FSM into a hardware implementation. The mapping of a
given symbolic representation into a two-valued logic implementation is
called state encoding (or state assignment) and it impacts heavily area,
speed, testability and power consumption of the realized circuit.
The first part of the book introduces the relevant background, presents
results previously scattered in the literature on the computational
complexity of encoding problems, and surveys in depth old and new
approaches to encoding in logic synthesis.
The second part of the book presents two main results about symbolic
minimization; a new procedure to find minimal two-level symbolic covers,
under face, dominance and disjunctive constraints, and a unified frame
to check encodability of encoding constraints and find codes of minimum
length that satisfy them.
The third part of the book introduces generalized prime implicants
(GPIs), which are the counterpart, in symbolic minimization of two-level
logic, to prime implicants in two-valued two-level minimization. GPIs
enable the design of an exact procedure for two-level symbolic
minimization, based on a covering step which is complicated by the need
to guarantee encodability of the final cover. A new efficient algorithm
to verify encodability of a selected cover is presented. If a cover is
not encodable, it is shown how to augment it minimally until an
encodable superset of GPIs is determined. To handle encodability the
authors have extended the frame to satisfy encoding constraints
presented in the second part.
The covering problems generated in the minimization of GPIs tend to be
very large. Recently large covering problems have been attacked
successfully by representing the covering table with binary decision
diagrams (BDD). In the fourth part of the book the authors introduce
such techniques and extend them to the case of the implicit minimization
of GPIs, where the encodability and augmentation steps are also
performed implicitly.
Synthesis of Finite State Machines: Logic Optimization will be of
interest to researchers and professional engineers who work in the area
of computer-aided design of integrated circuits
