Hardware Reference
In-Depth Information
7.1.1
Monolithic Representation of Relations
The monolithic representations of the transition and output relations of the automa-
ton can be obtained from the next-state and output functions:
T.i;cs;ns/ D ˘
k
Œns
k
T
k
.i; cs/;
O.i; o; cs/ D ˘
k
Œo
k
O
k
.i; cs/:
The monolithic representation of the complete transition-output relation of the
automaton is:
TO.i;o;cs;ns/ D T.i;cs;ns/:O.i;o;cs/:
TO
specifies what the next state is for each current state and each input/output
combination. A relation is not well-defined if there exists an input/output/current-
state combination for which the behavior of the automaton is not specified, i.e., the
automaton is incomplete. As an example of the use of the monolithic representation
TO
, consider the operation of completion of an incomplete automaton. The
transition-output relation of the completed automaton is
TO
0
.i;o;cs;ns/ D TO.i;o;cs;ns/C A.i; o; cs/:DC.ns/ C DC.cs/:DC.ns/
where
A.i; o; cs/ D 9
ns
TO.i;o;cs;ns/
is the sub-domain of input/output/current-state variables for which the original
automaton is not defined, and
DC
is the code (in terms of latch variables) of the
“don't-care” state added during completion. Note that we cannot use the code of
an unreachable state to represent the
DC
because the unreachable states have next
states. To encode
DC
we need to add an additional state variable. Thus the resulting
relation is derived from the original one by simply directing all undefined transitions
to
DC
and then adding a universal self-loop to
DC
.
7.1.2
Partitioned Representation of Relations
The disadvantage of monolithic representations is that they include all variables and
hence their BDDs may be huge. Even if these can be computed, the operations, such
as completion, product, determinization, become very inefficient, if not impossible,
to complete. If the set of reachable states is much smaller than the set of all
states, re-encoding the monolithic relations using fewer state bits may alleviate
this problem. However, re-encoding can be very slow and, in our experience, this
tends to increase the BDD sizes of the relations. We will show how partitioned
Search WWH ::
Custom Search