Hardware Reference
In-Depth Information
Definition 13.2.1.
Let
P
and
S
be two automata over the same alphabet
˙
.
P
sim
S
Automaton
P
simulates automaton
S
,
, if there exists a (simulation)
relation
R Q
P
Q
S
such that
! s
0
P
/ )9
s
S
.s
S
! s
0
S
/ ^ .s
0
P
;s
0
S
/ 2 R:
8
.s
P
;s
S
/2R
8
8
s
0
P
Œ.s
P
In other words, any move that
P
makes can be imitated by a similar move of
S
,
s
0
S
s
0
P
ending up in a state
that can be paired with
continuing to satisfy the relation.
(as long as there are no
combinational loops created between
u
and
v
), it is simpler to describe the relation
R
Although, in general,
u
can be any set of signals of
F
if the variables
u
are the outputs of the latches of
F
and thus are also latches
of
S
. Denote the other latches of
S
as
w
. In the application considered, assume that
S
(a
nd
hence
F
) is deterministic, then the complement of
S
is determinist
ic
and so
F S
is deterministic. Since the only variables t
hat are
hidden are
o
,
.F S/
#.i;
u
;
v
/
is still deterministic. Hence, every state of
X D F S
can be identified with state
combinations coming from
F
and
S
. Thus, a state of
X
has the form
.
u
;.
u
;
w
//
.The
simulation relation
R Q
F X
Q
S
consists of all tuples of the form
Œs
F X
;s
S
D
Œ.
u
. Note that the two instances of minterms in
w
are different
in general, but the minterms in the
u
positions must be the same.
In essence, we solve the language equation
;.
u
;.
u
;
w
///;.
u
;
w
/
F X
sim
S
simply by exposing
u
as an output of
and then using the language solving machinery already developed.
Solving a problem as a simulation relation rather than language containment
creates many don't cares in its solution
S
is
the solution provided by language solving. However, it is better understood how to
use don't cares in the minimization process. We miss some solutions due to the fact
that in general
u
does not need to be preserved.
As an example of how don't cares are created in
X
sim
, although
X
sim
X
,where
X
X
sim
, suppose that
S
is in the
state
.
u
;
w
/
and
F
is in the state
u
. As notational matter, we remind that
n
F
is the
non-accepting don't care state of
F
,
n
S
is the non-accepting don't care state of
S
,
s
F
is any accepting state of
F
,
s
S
is any accepting state of
S
. Suppose that under
.
Q
i; o;
u
.
u
0
;
w
0
/
input
; /
,
S
makes a transition to the state
. Consider the transition
..
Q
i; o;
u
that state
u
of
F
makes under the same input
; //
.If
u
¤
u
, then this
transition in
F
is undefined and hence will transit to
its non-acc
epting don't care
state,
n
F
. Thus, in the product machine
F.i;o;
u
;
v
/ S.i;;
u
;
v
/
, the current state
.n
F
;.
u
0
;
w
0
//
will transit to
. This is a non-accepting state of the product machine
because a stat
e is acceptin
g in a product only if both states are accepting
2
.Thus,in
F.i;o;
u
;
v
/ S.i;;
u
;
v
/
, the only
accept
ing states would be
.s
F
;n
S
/
where
n
S
is
the don't care state of
S
. Finally in
F S
, the accepting states are all states except
.s
F
;n
S
/
. In particular, states
.n
F
;s
S
/
are accepting. Such states can never transition
to a non-accepting state because
n
F
has a universal self-loop, i.e., the non-accepting
2
In the pair
.n
F
;.
u
0
;
w
0
//
n
F
is non-accepting in
F
.
u
0
;
w
0
/
, neither state is an accepting state (
,and
S
S
is non-accepting in
, the complement of
).
Search WWH ::
Custom Search