Hardware Reference
In-Depth Information
Theorem 5.3.
[112]
M
C
!
M
B
D
M
A
!
M
B
iff
M
C
is a reduction of the
product of
M
A
and
M
D
.
The contribution described in [111] builds directly the NDFSM capturing all the
flexibility.
2
Example 5.2.
Figure
5.3
a,b show the head and tail components of a series topology
M
A
!
M
B
to illustrate the computation of the output don't care sequences with
the procedure by Yevtushenko and Petrenko in [111], providing the full flexibility
at M
A
. Figure
5.3
c portrays the NDFSM M
D
representing all classes of input
sequences equivalent with respect to M
B
(M
B
produces the same output sequence
under these input sequences, which are the don't care output sequences of M
A
).
Then the product M
A
M
D
contains all the behaviors that can replace the given head
componentM
A
. One such behavior, corresponding to a submachine M
A
of M
A
M
D
is shown in Fig.
5.3
d, and it can be reduced to two states by state minimization as in
Fig.
5.3
e (states a
1
;c
2
;c
4
are merged into one state, and states b
1
;b
4
into another),
whereas the original head machine M
A
had three states.
5.1.4
Computation of the Permissible Behaviors
with the E-Machine
The attempts to characterize with input and output don't care sequences the
complete flexibility of a component in a composition with loops failed, because
modifying a component affects in a circular way the input and output don't care
sequences computed so far.
The first description of the complete flexibility in a two-way synchronous
composition for the rectification topology is due to Y. Watanabe and R. Brayton.
Given the network topology shown in Fig. 1.1d, they introduced in [142] a fixed-
point computation to compute a PNDFSM that contains
all
behaviors M
B
(DFSMs)
whose composition with the given machine M
A
is contained in the specification
M
C
. The PNDFSM so obtained has been called the
E-machine
, where the prefix
E
stands for environment. An alternative computation, credited to A. Saldanha, builds
an equivalent NDFSM (see [66] for a detailed exposition). The authors have also
investigated the issue of logical implementability of the DFSMs contained in the
E-machine, i.e., the problem of finding those contained DFSMs M
B
such that there
2
Consider a series composition M
A
!
M
B
of two FSMs M
A
D
.S
A
;I;U;ı
A
;
A
;r
A
/ and
M
B
D
.S
B
;U;O;ı
B
;
B
;r
B
/. The FSM representing all behaviors that can be realized at the
head component is given by the NDFSM M
D
D
.S
A
S
B
S
B
;I;U;T;.r
A
;r
B
;r
B
//,where
..s
A
; s
B
; s
B
/;i;
u
;.s
0
A
; s
0
B
; s
0
B
//
2
T iff the output of M
A
!
M
B
at state .s
A
; s
B
/ under input i
is equal to the output of M
B
at state
s
B
under input
u
,and.s
0
A
; s
0
B
; s
0
B
/ are the successor states
respectively in M
A
!
M
B
and M
B
.
Theorem 5.4.
[111]
M
C
!
M
B
D
M
A
!
M
B
iff
M
C
is a reduction of
M
D
.
.
Search WWH ::
Custom Search