Hardware Reference
In-Depth Information
I
V
O
M
A
2
M
A
1
Spec
Z
Fig. 14.3
Topology from Example
14.6
; the problem is to resynthesize FSM M
A
1
with a minimal
number of input alphabets
a
i
2
/v
1
b
a
0
a
1
i
1
v
2
z
1
/o
2
i
2
v
1
z
1
/o
1
i
2
v
1
z
2
/o
2
i
2
v
2
z
2
/o
2
i
1
/v
2
i
2
/v
1
i
1
/v
1
b
0
b
1
c
i
1
v
1
z
2
/o
2
i
1
v
2
z
2
/o
2
i
2
v
1
z
1
/o
1
i
2
v
1
z
2
/o
2
i
2
z
1
/v
1
o
1
i
2
z
2
/v
1
o
2
i
1
v
2
z
1
/o
1
i
1
v
1
z
1
/o
2
i
1
v
1
z
1
/o
1
i
1
v
1
z
2
/o
2
i
1
v
2
z
2
/o
2
i
2
v
2
z
1
/o
1
i
2
v
2
z
1
/o
2
c
0
c
1
i
2
v
2
z
2
/o
1
i
1
z
1
/v
2
o
1
i
1
z
2
/v
2
o
2
i
2
z
1
/v
1
o
1
i
2
z
2
/v
1
o
2
i
1
z
1
/v
1
o
1
i
1
z
2
/v
1
o
2
Fig. 14.4
Components for Example
14.6
.(
a
) FSM M
A
2
;(
b
)FSMM
A
1
;(
c
) Specification FSM
M
Spe c
Š
M
A
1
M
A
2
Let us check whether the largest solution M
S
depends essentially on input
alphabet I . At each state s
q
of FSM M
S
for each pair of input symbols .
v
j
;
z
k
/
2
V
Z we find the set of permissible transitions, i.e., we look for the output symbols
o
t
2
O such that
8
i
2
I;
9
s
0
2
S for which ..i;
v
j
;
z
k
/; s
q
;s
0
;o
t
/
2
T . For each
output symbols o
t
2
O with such a property, we keep all transitions from state s
q
whose input symbol is .i;
v
j
;
z
k
/,
8
i
2
I , and whose output symbol is o
t
2
O,
whereas all other transitions from state s
q
with input symbol .i;
v
j
;
z
k
/ are deleted.
If an output symbol with such a property does not exist then state s
q
is I -forbidden
and we delete state s
q
and all transitions to this state.
FSM M
S
has no I -forbidden states; we just delete the transitions that are not
permissible, namely, i
1
v
1
z
1
=o
2
;i
1
v
1
z
2
=o
1
;i
2
v
2
z
1
=o
2
;i
2
v
2
z
2
=o
1
(see Fig.
14.5
b), and
we project over the input alphabets V
Z and output alphabet O (see Fig.
14.5
c).
The determinization of the previous projection, denoted by
M
S
.M
S
/
d
D
#
V
Z
O
,
has 5 states and it is shown in Fig.
14.5
d.
Search WWH ::
Custom Search