Hardware Reference
In-Depth Information
a
b
i
1
v
2
/u
2
o
1
i
2
v
1
/u
1
o
2
i
2
v
2
/u
1
o
1
u
1
/v
1
u
3
/v
1
b
0
b
1
a
0
a
1
u
1
/v
2
u
3
/v
2
i
2
v
1
/u
2
o
1
i
2
v
2
/u
3
o
2
i
1
v
1
/u
3
o
2
i
1
v
2
/u
2
o
2
i
1
v
1
/u
2
o
1
u
2
/v
2
u
2
/v
2
u
2
/v
2
b
2
u
1
/v
1
u
3
/v
2
c
d
u
1
/v
1
i
2
v
1
/u
1
o
2
b
0
b
1
a
0
b
0
a
1
b
1
u
3
/v
2
i
2
v
2
/u
3
o
2
i
1
v
2
/u
2
o
2
u
2
/v
2
i
1
v
2
/u
2
o
1
i
1
v
2
/u
2
o
1
u
3
/−
u
1
/−
u
2
/v
2
u
2
/v
2
i
1
v
2
/u
2
o
2
b
2
DNC
i
2
v
2
/u
3
o
2
u
1
/v
1
u
3
/v
2
a
1
b
2
a
0
b
2
−/−
i
2
v
1
/u
1
o
2
e
b
0
u
1
/v
1
u
2
/v
2
u
3
/v
2
Fig. 10.10
FSMs with reference to the topology in Fig.
10.9
.(
a
) FSM
M
A
;(
b
)FSM
M
B
;(
c
)
Intersection
M
A
\M
B
"I O
;(
d
) Incompletely specified FSM
M
B
;(
e
)FSM
M
B
R
that is a reduction
of
M
B
Example 10.2.
Consider the transition diagrams of FSMs
M
A
and
M
B
in
Fig.
10.10
a,b. Derive the intersection
M
A
\M
B
"I O
, which is shown in Fig.
10.10
c;
the states of the intersection are the pairs
fa
0
b
0
;a
1
b
1
;a
0
b
2
;a
1
b
2
g
.
For each state of the FSM
M
A
, determine the don't care inputs over alphabet
U
.
The don't care input of state
a
0
is given by the set
DC
a
0
Df
u
3
g
,since
f
u
3
g
cannot
be produced at state
a
0
. In the same way, we obtain
DC
a
1
Df
u
1
g
.
Now check all the states of the FSM
M
B
. In the intersection, state
b
0
is combined
only with state
a
0
.Since
DC
a
0
Df
u
3
g
, the transition in
M
B
from state
b
0
under
input
u
3
can be replaced by a don't care transition. State
b
1
is combined only with
state
a
1
; thus, the transition from state
b
1
under input
u
1
can be replaced by a don't
care transition. Finally, state
b
2
is combined with state
a
0
as well as with state
a
1
,
Search WWH ::
Custom Search