Hardware Reference
In-Depth Information
representation, a fact reflected in that the number of BDD variables is proportional
to the number of states (the advantage of using ISM is that sets of states, e.g., sets
of compatible states, are represented implicitly and so they may be described more
compactly than an explicit enumeration would do).
As an alternative to exact methods, we may turn to heuristic procedures for state
minimization, one of which will be presented in the next section.
14.3
DCMIN: Immediate Equivalence Using Don't Cares
Command
dcmin
in BALM implements a minimization procedure. It works
particularly well when there are many transitions to an accepting “don't care” state,
usually named
DC1
in the BALM system. A don't care state is by definition a sink
with a self-loop, and can be made equivalent to any other state (if it is accepting) by
using its don't cares. For example, suppose two states, a and b are almost the same
except that on transition i , a transits to c and b transits to DC. Then we can make
acopyofDC,sayDC
0
, and moreover DC
0
and c can be made equivalent, and
hence a and b will be equivalent. Thus each transition into a don't care state can be
redirected to any other state of similar type
f
accepting, non-accepting
g
(the steps
are shown in Fig.
14.6
a-c).
a
b
−/−
−/−
i/o
b
DC
b
DC
i/o
i/o
−/−
−/−
DC
DC
i/o
i/o
a
c
a
c
c
−/−
b
DC
i/o
i/o
c
a
Fig. 14.1
(
a
) Original transition diagram; (
b
) Transition diagram with added don't care state DC
0
that is a copy of DC;(
c
) Transformed transition diagram where c is equivalent to DC
0
and a is
equivalent to b
Search WWH ::
Custom Search