Synthesis of Finite State Machines: Functional Optimization is one of
two monographs devoted to the synthesis of Finite State Machines (FSMs).
This volume addresses functional optimization, whereas the second
addresses logic optimization. By functional optimization here we mean
the body of techniques that:
-
compute all permissible sequential functions for a given topology of
interconnected FSMs, and
-
select a `best' sequential function out of the permissible ones.
The result is a symbolic description of the FSM representing the chosen
sequential function. By logic optimization here we mean the steps that
convert a symbolic description of an FSM into a hardware implementation,
with the goal to optimize objectives like area, testability, performance
and so on.
Synthesis of Finite State Machines: Functional Optimization is divided
into three parts. The first part presents some preliminary definitions,
theories and techniques related to the exploration of behaviors of FSMs.
The second part presents an implicit algorithm for exact state
minimization of incompletely specified finite state machines (ISFSMs),
and an exhaustive presentation of explicit and implicit algorithms for
the binate covering problem. The third part addresses the computation of
permissible behaviors at a node of a network of FSMs and the related
minimization problems of non-deterministic finite state machines
(NDFSMs).
Key themes running through the book are the exploration of behaviors
contained in a non-deterministic FSM (NDFSM), and the representation of
combinatorial problems arising in FSM synthesis by means of Binary
Decision Diagrams (BDDs).
Synthesis of Finite State Machines: Functional Optimization will be of
interest to researchers and designers in logic synthesis, CAD and design
automation.
