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