Hardware Reference
In-Depth Information
Derive the full I
1
-projection M
P
of M
S
.
If the FSM M
P
has no complete submachine
f
/* any reduction of M
S
depends essentially on the alphabet I
i
*/
If there are untried input alphabets, try the next one (i
D
i
C
1)and
go to 2., otherwise set M
P
D
M
S
;M
B
D
M
S
and exit.
g
else
f
/* The FSM M
P
has a complete submachine */
If there is no complete submachine M
B
of M
P
satisfying Proposi-
tion
14.4
f
If there are untried input alphabets, try the next one (i
D
i
C
1)and
go to 2., otherwise set M
P
D
M
S
;M
B
D
M
S
and exit.
g
else
f
/*
there
is
a
complete
submachine M
B
of M
P
satisfying
Proposition
14.4
*/
Set M
S
D
M
P
.
If there are untried input alphabets, try the next one (i
D
i
C
1)and
go to 2., otherwise go to 3.
g
g
g
3. Determine a reduction M
B
(a submachine) of M
S
that satisfies Proposition
14.4
.
If there exists such FSM M
B
, then the component FSM M
X
can be replaced
by M
B
that does not depend essentially on some input alphabets, and the
corresponding communication wires can be deleted from the initial composition.
Thus, the FSM M
B
can replace the initial component FSM without changing the
behavior of the overall composition, and the communication wires corresponding
to the redundant input alphabets can be deleted from the original composition.
The correctness of Procedure
14.4.1
can be established by exploiting the following
proposition.
Proposition 14.5.
Let
M
be a solution of the equation
M
Context
M
X
Š
M
Spec
and
M
P;k
be the full
I
k
-projection of the FSM
M
.
If
M
P;k
has no completely defined submachine, then each complete reduction of
M
depends essentially on the input alphabet
I
k
.
If there exists a reduction
M
B
of the FSM
M
P;k
that satisfies the conditions
of Proposition
14.4
, then the FSM
M
B
does not depend essentially on the input
alphabet
I
k
and is a solution of the FSM equation
M
Context
M
X
Š
M
Spec
.
Example 14.6.
Consider a window containing component FSMs M
A
1
and M
A
2
(see
Fig.
14.3
) and an FSM equation M
X
M
A
2
Š
M
Spec
,whereM
A
1
, M
A
2
and M
Spec
Š
M
A
1
M
A
2
are shown in Fig.
14.4
. The goal is to compute the largest flexibility in
place of M
A
1
and then to extract a replacement that minimizes the number of input
alphabets of component M
A
1
. The largest solution M
S
of equation M
X
M
A
2
Š
M
A
1
M
A
2
has three states (see Fig.
14.5
a).
Search WWH ::
Custom Search