Hardware Reference
In-Depth Information
a
b
c
d
e
Fig. 3.1
Illustration of synchronous compositions M
A
M
B
D
M
A
B
and M
A
M
B
D
M
A
B
0
of Example
3.11
-a) and
3.11
-b). (
a
) FSM M
A
;(
b
) FSM M
B
;(
c
)FSMM
B
;(
d
)FSMM
A
M
B
D
M
A
B
;(
e
) FSM M
A
M
B
D
M
A
B
0
.0; .s1;sb/; .s2;sb/; 0/
g
defines a partial FSM (no transition from state
.s2; sb/).
Figure
3.1
shows FSMs M
A
, M
B
and M
A
M
B
.
Theorem 3.12.
Let
M
A
be a complete FSM over input alphabet
I
1
V
and output
alphabet
O
1
U
and let
M
B
be a complete Moore FSM over input alphabet
I
2
U
and output alphabet
O
2
V
. Then the composition
M
A
M
B
is a complete FSM.
Proof.
Consider a string ˛
2
L.M
A
/
"
I
2
O
2
\
L.M
B
/
"
I
1
O
1
. Suppose that from the
initial state, M
A
reaches state s under the string ˛
#
I
1
U
V
O
1
and similarly that M
B
reaches state t under the string ˛
#
I
2
U
V
O
2
. Let the external input .i
1
;i
2
/
2
I
1
I
2
be applied next. For any
u
2
U there is a transition i
2
u
;t;t
0
;o
2
v
/ in M
B
, because
M
B
is a complete FSM; similarly, for any
v
2
V there is a transition .i
1
v
;s;s
0
;o
1
u
0
/
in M
A
, because M
A
is a complete FSM. Moreover, given the input i
2
u
0
,thereis
a transition .i
2
u
0
;t;t
00
;o
2
v
/ with the same output o
2
v
of transition .i
2
u
;t;t
0
;o
2
v
/,
because M
B
is a Moore FSM. Therefore
u
0
and
v
are matching internal signals, i.e.,
the string ˛ can be extended by .i
1
;i
2
;
u
0
;
v
;o
1
;o
2
/.
t
Search WWH ::
Custom Search