Hardware Reference
In-Depth Information
respect to GSP is the fact that each symbol in the players' alphabet has two parts:
the observed (˙
obs
) and the hidden one (˙
hid
). A player only sees the observed
part of the opponent's play: e.g., if player-0 selects
0
D
.
ob
0
;
hi
0
/, player-1 can
only see
obs
0
; similarly, player-0 observes only the ˙
ob
1
part of player-1's moves.
Each player instead knows both the observed and hidden part of the own move.
An interpretation of the synthesis of the unknown component as solving a GSI
game between a context player-0 M (with language L.M/
.I
V
U
O/
!
),
an unknown player-1 C (with language L.C/
.V
U/
!
), and a specification
S
.I
O/
!
has been offered in [74]. It is shown that the set of winning strategies
for player-1 is the set of solutions for the Watanabe-Brayton rectification problem.
A similar statement has been made for the controller's topology.
We are indebted for the exposition in this Section to the Ph.D. Dissertation by
Krishnan [74].
Problems
5.1. Hierarchical Optimization vs. Global Optimization
Rho and Somenzi observed in [121] that there are cases when M
A
is optimal with
respect to M
B
and vice-versa (i.e., there is no flexibility in the series composition
of M
A
with respect to M
B
nor vice versa of M
B
with respect to M
A
), yet their
cascade interconnection (M
A
feeding M
B
) is not the smallest implementation of the
product FSM. To prove their point they exhibited two FSMs M
A
and M
B
reported
respectively in Figs.
5.5
and
5.6
.
(a) Minimize the states of M
A
and M
B
in isolation.
(b) Are there input sequential don't cares of M
A
to optimize M
B
?
(c) Are there output sequential don't cares of M
B
to optimize M
A
?
(d) Merge the two FSMs M
A
and M
B
and minimize the collapsed FSM so obtained.
(e) Comment the previous results. What are the features of these two machines that
explain their behavior in composition ?
5.2. Optimization of a Head Component in a Series Topology
Figure
5.7
shows a series topology M
A
!
M
B
, with no input don't care sequences
of M
B
(since the output sequences of M
A
coincide with
?
), where M
B
is
f
0;1
g
Present
Next
Input
state
state
Output
0
A
B
1
1
A
C
0
0
B
A
0
1
B
D1
0
C
D0
1
C
B
1
Fig. 5.5
Machine M
A
for Problem
5.1
0
DC
1
1
DB
0
Search WWH ::
Custom Search