Hardware Reference
In-Depth Information
submachine which is implementable in an efficient way. The minimize algorithm
does not find such a reduction or submachine; it just minimizes the number of states
to find a smaller machine that is equivalent to the original. In contrast, the desired
implementation is just contained in the original.
In this chapter we discuss some criteria to select a behavior or a submachine out
of the flexibility computed by one of the global or local techniques studied in the
previous chapters.
We examine two cost functions: the minimum number of states and the minimum
input support. Minimizing the number of states of an FSM is a classical problem,
studied for incompletely specified FSMs first and for observable FSMs later on.
We review some basic notions of state minimization of ISFSMs and observable
FSMs in Sect.
14.2
. Since exact state minimization may be infeasible in some
practical examples, Sect.
14.3
presents a practical heuristic that is supported by good
experimental results. Finally Sect.
14.4
describes an algorithm to select a behavior
that minimizes the number of inputs on which the FSM under synthesis depends
essentially.
14.2
State Minimization
State minimization of FSMs is a well-known problem [72]. State minimization
of completely specified FSMs has a complexity subquadratic in the number of
states [51, 62]. This makes it an easy problem when the starting point is a two-
level description of an FSM, because the number of states is usually less than a few
hundred. The problem becomes difficult to manage when the starting point is an
encoded sequential circuit with a large number of latches (in the hundreds). In that
case one should extract first a state transition graph from the encoded network and
then apply state minimization to it. But when latches are more than a dozen, the
number of reachable states may be so large as to make state extraction and/or state
minimization infeasible. However, it has been shown [85, 86, 116] how to bypass
the extraction step and compute equivalent state pairs and equivalence classes of
states implicitly. Equivalence classes are basically all that is needed to minimize a
completely specified state machine. A compatible projection operator [85] uniquely
encodes each equivalence class by selecting a unique representative of the class to
which a given state belongs. This implicit technique allows state minimization of
sequential networks outside the domain of standard state minimization.
State minimization of incompletely specified FSMs described by state-based
representations has been studied since the beginning of sequential synthesis and
a classical exact algorithm has been formulated by Grasselli and Luccio. Later on,
this algorithm has been extended to complete observable FSMs by various authors.
Now we review the basics of the procedure for exact state minimization of complete
observable FSMs described by state-based representations. For a thorough treatment
of the topic we refer to the specialized monograph [66].
Search WWH ::
Custom Search