Hardware Reference
In-Depth Information
is a finite set of FSM equations where the unknown
M
X
is specified over the same
input and output alphabets. An FSM
M
S
is a solution of the system of equations iff
it is a solution of each equation of the system.
Going back to the topology in Fig.
12.4
, let us define the system of equations
M
X
M
A
1j
Š M
A
j
M
A
1j
;:::;M
X
M
A
pj
Š M
A
j
M
A
pj
, where in each equation
M
X
M
A
kj
Š M
A
j
M
A
kj
the FSM
M
A
j
M
A
kj
is the sequential composition
of FSMs
M
A
j
and
M
A
kj
,with no external access granted to the output alphabet
V
is kept as an internal alphabet of
the composition. In that case, the component FSM
of the component
M
A
j
, i.e., the alphabet
V
M
A
j
may still be reducible,
because its output
V
is not visible externally and its effect is “masked” by the series
compositions with
M
A
1j
;:::;M
A
pj
.
In fact, given an FSM
M
B
that is a solution of the system of equations
M
X
M
A
1j
Š M
A
j
M
A
1j
;:::;M
X
M
A
pj
Š M
A
j
M
A
pj
and an input sequence
˛ 2 I
?
, the output response of the composition
M
A
j
M
A
1j
M
A
pj
to
˛
is
the output response of
M
A
1j
;:::;M
A
pj
, together with the output response of
M
A
j
,
when the FSMs
M
A
j
;M
A
1j
;:::;M
A
pj
are composed synchronously. Therefore,
M
B
is a solution of the equation
M
X
.M
A
1j
M
A
pj
/ Š M
A
j
M
A
1j
M
A
pj
,
and the converse holds too. So, one proves the following statement.
Proposition 12.2.2
For the topology given in Fig.
12.4
, the composition
M
B
M
A
1j
M
A
pj
is equivalent to
M
A
j
M
A
1j
M
A
pj
, i.e., the FSM
M
B
is a solution of
the equation
M
X
.M
A
1j
M
A
pj
/ Š M
A
j
M
A
1j
M
A
pj
, if and only if it is
a solution of the system of equations
M
X
M
A
1j
Š M
A
j
M
A
1j
;:::;M
X
M
A
pj
Š
M
A
j
M
A
pj
.
Proof.
(Sketch)
(a)
M
X
.M
A
1j
M
A
pj
/ Š M
A
j
M
A
1j
M
A
pj
implies
M
X
M
A
1j
Š M
A
j
M
A
1j
;:::;M
X
M
A
pj
Š M
A
j
M
A
pj
.
Given that
M
A
j
M
A
j
Š M
A
j
, in the previous equality
we can compose the left side with
M
X
M
X
Š M
X
and
p 1
copies of
M
X
, and the right side with
p 1
M
X
M
X
M
X
.M
A
1j
M
A
pj
/ Š
M
A
j
M
A
j
M
A
j
M
A
1j
M
A
pj
. By commutativity and associativity,
we can restructure the previous equality and get
copies of
M
A
j
, to obtain:
.M
X
M
A
1j
/ .M
X
M
A
pj
/ Š .M
A
j
M
A
1j
/ .M
A
j
M
A
pj
/
. From the latter we get finally
M
X
M
A
1j
Š M
A
j
M
A
1j
;:::;M
X
M
A
pj
Š M
A
j
M
A
pj
(notice that
M
X
M
A
1j
and
M
A
j
M
A
1j
are defined over
.I; Z
1
/
, ...,
M
X
M
A
pj
and
M
A
j
M
A
pj
are
defined over
.I; Z
p
/
).
(b)
M
X
M
A
1j
Š M
A
j
M
A
1j
;:::;M
X
M
A
pj
Š M
A
j
M
A
pj
implies
M
X
.M
A
1j
M
A
pj
/ Š M
A
j
M
A
1j
M
A
pj
.
From
M
X
M
A
1j
Š M
A
j
M
A
1j
;:::;M
X
M
A
pj
Š M
A
j
M
A
pj
, we obtain by
composition
.M
X
M
A
1j
/.M
X
M
A
pj
/ Š .M
A
j
M
A
1j
/.M
A
j
M
A
pj
/
,
and then by commutativity and associativity
M
X
.M
A
1j
M
A
pj
/ Š M
A
j
M
A
1j
M
A
pj
.
t
Example 12.5.
Consider the composition in Fig.
12.5
and the instances of the FSMs
M
F
,
M
D
and
M
E
in Fig.
12.6
a-c.
Search WWH ::
Custom Search