Transcript + y

Structure of Sequential Machines
1
Zvi Kohavi and Niraj K. Jha
Structure
Structure: manner in which a machine can be realized from a set of smaller
component machines, as well as the functional dependencies of
its state and output variables
Example: Machine M1
Excitation and output tables
2
Example (Cont.)
Logic equations corresponding to state assignment 
Y1 = x’y1 + xy1’ = f1(x,y1)
Y2 = x’y1 + xy2 = f2(x,y1,y2)
z = xy2’ = f0(x,y2)
x
Y1
y1
z
Y2 y
2
(a) Circuit diagram.
x
f1(x,y1)
Y1
y1
f2(x,y1,y2)
Y2
y2
f0(x,y2)
z
(b) Block diagram.
3
Example (Cont.)
Logic equations corresponding to state assignment 
Y1 = x’y1 + xy1’ = f1(x,y1)
Y2 = xy2’ = f2(x,y2)
z = xy1’y2’ + xy1y2 = f0(x,y1,y2)
x
Y1
y1
x
x
x
Y2
z
y2
(a) Circuit diagram.
f1(x,y1)
Y1
y1
f0(x,y1,y2)
x
f2(x,y2)
Y2
z
y2
4
(b) Block diagram.
State Assignments Using Partitions
Let machine M have a set of n states S = {S1,S2,…,Sn} and a set of p input
symbols I = {I1,I2,…,Ip}
• k = log2n state variables and l = log2p input variables are needed for a
complete assignment
• In general: Yi = fi(y1,y2,…,yk,x1,x2,…,xl) i = 1,2,…,k
• Objective: obtain assignments
Yi = fi(y1,y2,…,yr,x1,x2,…,xl) i = 1,2,…,r
• Subset {Y1,Y2,…,Yr} of state variables, whose values are independent of
the values of yr+1,yr+2,…,yk: self-dependent subset
– Both assignments  and  have this property
State assignment problem:
• Viewed as a coding problem: distinct code assigned to each state
• Viewed as a partitioning problem: each state variable yi induces a partition i
on the set of states such that two states are in the same block of i if and
only if they are assigned the same value of yi
5
Partitioning Example
Example: y1 induces partition  1= {A,B;C,D} and y2 induces  2 = {A,D;B,C}
• Clearly, to assign a unique code to each state:
–  1. 2 . … .k =  (0)
6
Inverse Process
Assigning values to state variables to distinguish blocks of a set of partitions:
• Given a partition with #( ) blocks on the set of states of M, to distinguish
among these blocks, it is necessary to select log2#( ) state variables and
assign a distinct combination of these variables to each block of  :
all the states in each block are assigned the same values of y1, y2, …, yr
• Each partition on the states of M provides some information regarding M’s
state
• If M possesses two partitions,  1 and 2, such that 1 > 2, then 2 provides
more information than 1
• Clearly, the zero partition provides all the necessary information, since the
knowledge of the block of (0), in which the machine is, is sufficient to
uniquely determine the state of M
• Thus, to obtain a state assignment: we need to assign values to state
variables such that they distinguish the blocks of a set of partitions whose
product is the zero partition
7
Assignment Example
Example: For machine M1, the product of partitions  1= {A,B;C,D} and
 2= {A,C;B,D} is zero, i.e., 1. 2 =  (0)
• Hence, if we assign y1 to distinguish block (A,B) from block (C,D), and y2
to distinguish the blocks of  2 , each state of M1 will have a distinct code,
as in assignment 
Machine M1
Assignment 
8
Closed Partition
A partition  on the set of states of a sequential machine M is said to be
closed if, for every two states Si and Sj which are in the same
block of  and any input symbol Ik in I, states IkSi and IkSj are in a
common block of 
• IkSi: Ik-successor of Si
Example: For machine M1, partitions 1= {A,B;C,D} and  2 = {A,C;B,D} are
closed
• 0- and 1-successors of (A,C): (A,C) and (B,D), respectively
• If we denote the blocks of  2 , (A,C) and (B,D), by P and Q, respectively:
the successor relationship can be described by the graph below
• Clearly, knowledge of the present block of M1 and the input symbol:
sufficient to uniquely determine the next block
1
0
P
Q
0,1
Machine M1
9
Reduction of Functional Dependency of
State Variables
Theorem: Let M be a sequential machine with k state variables, y1, y2, …,
yk. If there exists a closed partition  on the states of M and if r state
variables, where r = log2#( ), are assigned to the blocks of  , such that all
the states contained in each block are assigned the same values of y1, y2,
…, yr, then the next-state variables, Y1, Y2, …, Yr, are independent of the
remaining k-r variables.
Conversely, if the first r next-state variables, Y1, Y2, …, Yr
(1 <= r < k), can be determined from the values of the inputs and the first r
state variables, independently of the values of the remaining k-r variables,
then there exists a closed partition  on the states of M such that two
states, Si and Sj, are in the same block of  if and only if they are assigned
the same values of the first r variables.
10
Proof of Theorem
Proof: Since each block of  is assigned the same values of variables y1,
y2, …, yr, and since  is closed, the knowledge of the present block of 
and present input values is sufficient to determine the next block of  .
In other words, the knowledge of the present values of y1, y2, …, yr and
present input values is sufficient to determine the values of Y1, Y2, …, Yr,
regardless of the values of the remaining variables.
To prove the converse: form a partition  on the set of states of M s.t. all the
states with the same assigned values of y1, y2, …, yr are in the same block

of . To 
prove that is closed,
consider two states, Si and Sj, which belong
to the same block of . Eachof these states has the same assigned values
of the first r variables, and since these variables are independent of the
values of the remaining ones, an application of the same input sequence to
both Si and Sj causes the same change in the values of the first r variables
for these two states. Hence, for each value of Ik, successors IkSi and IkSj
have the same assignment of values for the first r variables and,
consequently, are contained in the same block of . Thus, is closed.


11
Example
Example: For machine M1, partitions 1= {A,B;C,D} and  2 = {A,C;B,D} are
closed.
• Since y1 in assignment  has been assigned to distinguish the blocks of
1: it is independent of y2
• Similarly, since y2 has been assigned to distinguish the blocks of  2: it is
independent of y1
Machine M1
Assignment 
12
Series Decomposition
The theorem provides a necessary and sufficient condition for machine
decomposition:
• Existence of a partition  and a closed partition  on the set of states of
machine M, such that  .  =  (0), guarantees that M can be composed of
two component machines in series
– The first component consists of log2#() memory elements (and their
excitation circuitry): corresponding to state variables assigned to
distinguish the blocks of 
» Since these variables are independent of the remaining variables:
the first component is referred to as the independent component
– The second dependent component contains log2#( ) memory
elements: corresponding to the state variables assigned to distinguish
the blocks of 
– Independent component: predecessor machine – distinguishes
between the blocks of 
– Dependent component: successor machine – distinguishes between
the states within the blocks of 
13
Parallel Decomposition
Existence of two closed partitions on the states of M such that their product
is zero, i.e., 1. 2 =  (0), implies that: M can be composed of two
components, operating in parallel, independently of each other
• One component consists of log2#( 1) memory elements: corresponding to
state variables assigned to distinguish the blocks of  1
• The second component contains log2#( 2 ) memory elements:
corresponding to the state variables assigned to distinguish the blocks of  2
An n-state machine M can be decomposed into two independent
components operating in parallel if and only if there exist two nontrivial closed partitions  1and 2 on the states of M such that
 1. 2 =  (0)
• This decomposition requires a minimal number (log2n) of state variables if
and only if log2#( 1) + log2#( 2) = log2n
14
Example
Example: Machine M2 has seven closed partitions
• Existence of  5 suggests that M2 can be realized as two component
machines connected in series
– Predecessor component: has two state variables, y1 and y2, assigned
to distinguish the blocks of  5 -- hence are independent of y3
– Successor component: has a single variable y3, which distinguishes
the states in the blocks of  5
Machine M2
Closed partitions
15
Example (Contd.)
Example (contd.): Maximal reduction in dependency of state variables
would be achieved if we could find three two-block closed
partitions whose product is zero
• However, only two two-block partitions can be found: 1 and  2
• Hence, we must select  s.t. 1. 2 . =  (0)
–
 = {A,D,G,H; C,D,E,F}
Machine M2
Closed partitions
16
Example (Contd.)
Example (contd.): Assigning y1 to distinguish the blocks of 1, y2 for  2,
and y3 for 
Machine M2
Logic
Excitation and output table
Y1
x
Logic
Logic
Y3
Logic
Y2
z
Y1 = x’y1’
Y2 = x’y2 + xy2’
Y3 = xy3 + x’y1’y2y3’ + y1’y2’y3
+ y1y2y3 + x’y1y2’y3’
z = y1’y2’y3
17
Schematic diagram
Lattice of Closed Partitions
Theorem: Product 1. 2 and sum 1+  2 of two closed partitions on the set
of states of M are also closed
Proof: Let B be an arbitrary block of 1. 2. Since B is the intersection of
some block B1 of 1and B2 of  2, then B is contained in both B1 and B2.
Since 1 and  2 are closed, the Ik-successor of B is also contained within
some block IkB1 of1and some block IkB2 of  2, where IkBi is the
Ik-successor of Bi. Hence, IkB is contained within intersection IkB1.IkB2.
However, IkB1.IkB2 is contained in a block of 1. 2. Hence, IkB is contained
1  2
1  2
in a block of . . Therefore,
. is closed.
This theorem implies that, to each pair of closed partitions 1and  2, there
corresponds a least upper bound, 1+  2 , and a greatest lower bound,
1.  2
18
Construction of -lattice
Example: Machine M3
Basic partitions
B
AB; C;
D; E; F
C
ABCF;
DE
ABCF;
DE
D
(I)
(I)
(I)
E
(I)
(I)
(I)
ABCF;
DE
F
ABCF;
DE
ABCF;
DE
ABCF;
DE
(I)
A
B
C
(I)
4
0
=
1
=
=
=
=
=
2
2
3
3
4
1
5
(0)
 -lattice
D
A; EF;
B; C; D
E
(0)
{ A,B; C; D; E; F }
{ A,B,C,F; D,E }
{ A; B; C; D; E,F }
{ A,B; C; D; E,F }
(I)
19
Reduction of the Output Dependency
Example: Machine M4
Closed partition  = {A,B;C,D}
• Looking for a partition
s.t. .  = (0)
• a = {A,C;B,D}
• b = {A,D;B,C}
Two possible assignments
Y1 = x’y1 + xy1’
Y2 = x’y2’ + y1’y2’
+ xy1y2
z = x’y1’y2’ + x’y1y2
+ xy1’y2 + xy1y2’
NAND-NAND CMOS:
64 transistors
Y1 = x’y1 + xy1’
Y2 = x’y2’ + xy1’y2
+ y1y2’
z = x’y2’ + xy2
NAND-NAND CMOS:
40 transistors
20
Output-consistent Partition
A partition o on the states of a machine M is said to be output-consistent
if, for every block of o and every input symbol, all the states
contained in the block have the same output symbols
Example: o = b = {A,D;B,C} is an output consistent partition of machine
M4
Machine M4
21
Output-consistent Partition (Contd.)
Let M have n states to which we assign k variables, where k = log2n. Let
r = log2#(o) variables be assigned to the blocks of M’s outputconsistent partition o. Because o is output-consistent, the output
symbols associated with the blocks of ocan be computed from
these r variables, independently of the remaining k-r variables
which are assigned to the states in the blocks of o.
• The existence of an output-consistent partition o on the states of a
sequential machine M implies that there exists an assignment for M such
that the outputs depend, at most, on the external inputs and on the
variables assigned to the blocks of o
• Generalization: Let  = { 1, 2 , …,k } be the set consisting of partitions
induced by state variables y1, y2, …, yk. Let o1, o2, …, om be outputconsistent partitions induced by outputs z1, z2, …, zm. If, for some subset
Q of  ,
then zi is a function of external input x and the variables assigned to the
partitions contained in Q
22
Example
Example: In machine M4, o =o1= {A,D;B,C}
• Since y2 in assignment  has been assigned to o : output z depends
only on this variable and is independent of y1
• In assignment  , we obtained a reduction in the dependency of y1 and
(simultaneously) of output z: possible since  . o = (0)
• However, if  . o = (0), but log2#( ) + log2#(o) > log2n : the assignment
is not a minimal one
– E.g., if  = {A,B;C,D;E,F;G,H} while o = {A,C;B,E;D,G;F,H}: then
 .o= (0), but log24 + log24 = 4 instead of the minimal 3
Machine M4
23
Input Dependence and Autonomous
Clocks
A partition i on the states of a machine M is said to be input-consistent if,
for every state Si of M and all input symbols, I1, I2, …, Ip, the next
states, I1Si, I2Si, …, IpSi, are in the same block of i
Example: Consider machine M5
• State A implies the identification of states C and D
• Similarly, C implies the identification of E and F and E implies the
identification of A and B
• Thus, smallest input-consistent partition: i = {A,B;C,D;E,F}
• Clearly, any partition that contains i is also input-consistent
Machine M5
24
Input Independence (Contd.)
Since the successor relationships among the blocks of i are independent:
the log2#(i) variables assigned to distinguish the blocks of i
are input-independent
• If, in addition to i, machine M possesses a closed partition  such that
 >= i, then: for a given state Sj and every input symbol I1, I2, …, Ip in I,
the next states I1Sj, I2Sj, …, IpSj, must be in the same block of i and,
hence, in the same block of  as well
– Consequently, for a given initial state, the block of  in which the state
of M is contained after any finite input sequence: depends only on the
initial block and on the length of the sequence
• The existence of a closed partition  and a nontrivial input-consistent
partition i on the states of M, where  >= i : necessary and sufficient
condition for the existence of an assignment for M such that the log2#( )
variables assigned to the blocks of  are independent of the input and of
the remaining state variables
Autonomous clock: a component machine whose output at any time is
independent of the input
• Maximal autonomous clock: smallest closed partition when M possesses
an input-consistent partition i and several closed partitions, each greater
than or equal to i
25
Example
Example: For machine M5, input-consistent partition i = {A,B;C,D;E,F} is
closed
• Output-consistent partition o= {A,C,E;B,D,F}
• Since  = i and  .o=  (0): the following assignment and equations
result
Machine M5
26
Example (Contd.)
Realization of machine M5:
Y1
Autonomous
clock
Y2
Y3
x
27
z
Autonomous Clock
If M is a strongly connected machine, then any component induced by a
closed partition on the states of M is also strongly connected
• Hence, the autonomous clock of a strongly connected machine is also
strongly connected: furthermore, it is a periodic machine.
• To find period p of the autonomous clock: suppose that machine M
possesses a closed partition  such that  ≥ i
• The clock has #( ) states and, therefore, during #( )+1 time units: it must
pass at least twice through one of the states
• Thus, period p is equal to or smaller than #( )
Example: Maximal autonomous clock of machine M5 is determined from
partition  = i
 ={A,B;C,D;E,F} = { ;  ; }
Autonomous clock with p = 3
28
Covers, and Generating Closed Partitions
through State Splitting
Covers: Consider machine M6
• No closed partition exists for this machine: it appears that it cannot be
decomposed in any manner
• Consider next machine M6’: it is reducible to machine M6 since states C′
and C′′ are equivalent
• Machine M6’ possesses closed partition  = {A,C′;B,C′′}: if we choose
partition = {A,B;C′,C′′} such that  . = (0), and if we assign y1 and y2 to
the blocks of  and , respectively, the following equations result:
• Corresponding cover: {A,C;B,C}
Y1 = x
Y2 = xy2 + x’y1y2’
z = xy1’y2’
Machine M6
Machine M6’
29
Cover
A collection  of subsets, whose set union is S, such that no subset is
included in another subset in the collection, is referred to as a cover on set S
• The subsets are called the blocks of 
• Cover on the set of states of a machine M is said to be closed if,
for every two states Si and Sj which are in the same block of and
any input symbol Ik in I, states IkSi and IkSj are in a common block of 
• #() and  () denote, respectively, the number of blocks in and
the number of elements in the largest block of 
Example: Covers {A,C;B,C} and {A,B;A,C;B,C} on the set of states of M6 are
closed
• If P = (AC) and Q = (BC): we get the table below
• Since the predecessor machine in the serial
connection of M6 distinguishes the blocks of :
the successor relationships of the table define
the state transitions of the predecessor
component
30
Implication Graph
Implication graph: a directed graph with vertices representing subsets of
the set of states of machine M
• Each subset consists of states to be identified in the state table: or which
are implied by previously identified subsets of states
• Closed implication graph: subgraph of an implication graph s.t. (1) for
every vertex in the subgraph, all outgoing arcs and their terminating
vertices also belong to the subgraph, and (2) every state of M is
represented by at least one vertex
• Closed graph: constitutes a closed cover
Example: Implication graph of M6
0
(A,B)
1
0
(A,C)
0
Closed
graph
(B,C)
1
31
General Procedure
Augmenting machine M into an equivalent machine M’ which possesses
one or more closed partitions:
1. Construct the implication graph of given machine M
2. From the implication graph: choose a closed subgraph with a minimal
number of vertices. If any state in Si is represented by more than one
vertex, relabel Si in the first vertex Si’, in the second vertex Si’’, and so
on
3. For each Si which has been replaced with Si’, Si’’, …: split the
corresponding state in M’s state table
4. Modify the entries of the new state table by inserting the necessary
primes: an entry Sp in row Si, column Ik, is changed to Sp’ if Si is
represented by some vertex (Si,Sj) and the Ik-successor vertex is (Sp’,Sq)
Example: Only C appears in two vertices, thus is split into C’ and C’’
 = {A,C’;B,C’’}
0
(A,B)
1
0
(A,C)
0
1
Closed
graph
(B,C)
32
Application of State Splitting to Parallel
Decomposition
Example: Machine M7 and its  -lattice
o = {A,E,F;B,D;C,G}
i = {A,E,F;B,C,D,G} =  4
(I)
( I ) = { A,B,C,D,E,F,G }
=
2 =
3 =
4 =
5 =
6 =
( 0 )=
1
1
4
3
5
2
6
{ A,C,D,E; B,F,G }
{ A,G; B,E; C,D,F }
{ A,B,E,G; C,D,F }
{ A,E,F; B,C,D,G }
{ A,E; B,G; C,D; F }
{ A; B; C,D; E; F; G }
{ A; B; C; D; E; F; G }
(0)
33
Example (Contd.)
Example (contd.): Implication graph and augmented machine M7’
• Closed cover:  = {A,G;B,E;C,F;D,F}
0
0
1 (C,F)
0
1
1
0
(A,B)
(A,G)
Closed
graph
(D,F)
1
1
(B,E)
0
 = {A,G;B,E;C,F’;D,F’’}
 4' = {A,E,F’,F’’;B,C,D,G}
 3' = {A,B,E,G;C,D,F’,F’’}
o' = {A,E,F’,F’’;B,D;C,G}
i' =  4'
34
Example (Contd.)
Example (contd.):
1.  .  4' = (0): parallel decomposition possible
2. Component machine corresponding to 4': consists of y1 only –
autonomous clock since  4' = i'
3. Since each block of  3' contains exactly two blocks of  : assign y2 to the
blocks of  3'-- making it independent of y3
4. Variable y3 must be assigned to the blocks of a partition  , s.t.  3'.  =  :
partition  = {A,C,F’,G;B,D,E,F’’} satisfies this condition
5.  . 4' = {A,F’;B,D;C,G;E,F’’} is smaller than o': z a function of y1 and y3
Autonomous
clock
Y1
y1
x
Logic
Logic
Y2
y2
Logic
Y3
z
y3
(b) Schematic diagram.
35
Information Flow in Sequential Machines
Example: Machine M8 has two closed partitions
1 = {A,B,C;D,E,F}
 2 = {A,E;B,F;C,D}
where 1. 2=  (0)
Y1 = x1’y1 + x1y1’ = f1(x1,y1)
Y2 = x2 + x1y2’ + x1y3 + x1’y2y3’
= f2(x1,x2,y2,y3)
Y3 = x1’x2’y2y3’ + x2y2’ + x1x2’y2y3
= f3(x1,x2,y2,y3)
NAND-NAND CMOS:
60 transistors
Y1 = x1’y1 + x1y1’
= f1(x1,y1)
Y2 = x2 + x1’y3 + x1y3’
= f2(x1,x2,y3)
Y3 = x2y2 + x1x2’y2’
= f3(x1,x2,y2)
NAND-NAND CMOS:
36
40 transistors
Partition Pairs
Example (contd.): Machine M8
Y1 = x1’y1 + x1y1’ = f1(x1,y1)
Y2 = x2 + x1’y3 + x1y3’ = f2(x1,x2,y3)
Y3 = x2y2 + x1x2’y2’ = f3(x1,x2,y2)
•
•
•
•
•
y1 induces: 1= {A,B,C;D,E,F}
y2 induces:  (y2) = {A,E;B,C,D,F}
y3 induces:  (y3) = {A,C,D,E;B,F}
Successors of blocks of (y2): contained in  (y3)
Successors of blocks of  (y3): contained in  (y2)
37
Partition Pairs (Contd.)
Partition pair ( , ') on the states of a sequential machine M is an ordered
pair of partitions s.t., if Si and Sj are in the same block of  , then for
every input symbol Ik in I, IkSi and IkSj are in the same block of  '
Example (contd.): Partition pairs on the states of M8:
(1, 1') = ({A,B,C;D,E,F},{A,B,C;D,E,F})
( 1, 1') = ({A,C,D,E;B,F},{A,E;B,C,D,F})
( 2, 2') = ({A,E;B,C,D,F},{A,C,D,E;B,F})
Example: ( 3, 3') = ({A,D;B;C,E;F},{A,E;B,D;C,F}) is a
partition pair on M8: hence so are the following:
({A,D;B;C;E;F},{A,E;B,D;C,F})
({A,D;B;C,E;F},{A,E;B,C,D,F})
38
Partial Ordering on Partition Pairs
If ( 1, 1') and ( 2, 2') are partition pairs: then ( 1, 1') >= ( 2, 2)' if and only if
 1>= 2 and  1'>= 2'
• If ( 1, 1') and ( 2, 2') are partition pairs on the states of a machine M: then
( 1. 2 , 1.' 2') and ( 1+ 2 , 1'+ 2') are also partition pairs on its states
• They define the glb and lub, respectively, of the given partition pairs
Mm pair: Let  ' be a partition on the set of states of M
• Define a partition M( ') such that M( ') =i , where the sum is over all i s.t.
•
•
•
•
(i , ') is a partition pair
Similarly, define a partition m( ) = i,' where the product is over all i 's.t.
( ,i ') is a partition pair
A partition pair ( , ') is said to be an Mm pair if and only if  = M( ') and  '=
m( )
Since the lub of two partition pairs is a partition pair: (M( '), ') is a partition
pair – M( ') is the largest partition the successors of whose blocks are
contained in the blocks of  '
Since the glb of two partition pairs is a partition pair: ( ,m( )) is a partition
pair – m( ) is the smallest partition containing all the successors of the
39
blocks of 
Mm Pairs
M and m partitions possess the following properties:
• If  is a partition on machine M, then
– m{M( )] <= 
– M[m( )] >=
– M{m[M( )]} = M( )
– m{M[m( )]} = m( )
• Thus, for every partition  on the states of M, {M( ),m[M( )]} and
{M[m( )],m( )} are Mm pairs on its states
• If (, ') is an Mm pair: then  is the largest partition from which we can
determine  ', and  ' is the smallest partition which contains the successor
blocks implied by 
– Thus, by enlarging  'or by refining : we can obtain other partition pairs
– Hence, corresponding to every partition pair ( , '): there exists an Mm
pair (, ') s.t.  >= and  '<= '
» Clearly, the set of all Mm pairs completely characterizes the set of
all partition pairs on the states of M: since any partition pair can be
generated from the corresponding Mm pair
40
Information-flow Inequalities
Theorem: Let variables y1, y2, …, yk be assigned to the states of machine M,
and let  (yi) be the partition induced by variable yi, where 1 <= i <= k. If the
next-state variable Yi can be computed from the external inputs and a subset
Pi of variables, then
 (yj) <= M[ (yi)]
where the product is taken over all  (yj), s.t. yj is contained in subset Pi
Conversely, a sufficient condition for the existence of an assignment,
in which a next-state variable Yi depends only on the external inputs and the
value of a corresponding subset Pi of state variables, is the existence of a
partition pair (, (yi)) on M s.t., for each i '
 (yj) <= M[ (yi)]
where the product is taken over all  (yj), s.t. yj is in Pi
41
Example
Example: For machine M8: 1.' 1.' 2'= (0) where 1=  1,'  1'= 2 and  2'=  1
• Hence, a three-variable assignment exists s.t. Y1 (assigned to  1')
is self-dependent
• Y2 and Y3 (assigned to  1' and 2)' can be computed from y3 and y2
(1, 1)' = ({A,B,C;D,E,F},{A,B,C;D,E,F})
( 1, 1') = ({A,C,D,E;B,F},{A,E;B,C,D,F})
( 2, 2') = ({A,E;B,C,D,F},{A,C,D,E;B,F})
Y1 = x1’y1 + x1y1’ = f1(x1,y1)
Y2 = x2 + x1’y3 + x1y3’ = f2(x1,x2,y3)
Y3 = x2y2 + x1x2’y2’ = f3(x1,x2,y2)
42
Computing the Mm Pairs
Let a and b be two arbitrary states of machine M and let ab be the partition
that includes a block (ab) and leaves all other states in separate
blocks
• Then m(ab) is the smallest partition containing the blocks implied by the
identification of (ab)
• Clearly, (ab,m(ab)) is a partition pair
Any partition  can be expressed as a sum  =ab, where the sum is taken
over all ab s.t.ab<= 
• Since the sum of partition pairs is also a partition pair: (ab, m(ab)) is a
partition pair
• Hence, if  is the M-partition: ( , m(ab)) is an Mm pair
43
Computing the Mm Pairs (Contd.)
Basic approach:
• First, find set {m(ab)} for all distinct a and b
– This requires n(n-1)/2 computations
• Next, find all possible sums of these partitions
– This generates all m-partitions
• The M-partition  = M( ') corresponding to every m-partition ' is given by:
 =ab where the sum is taken over allab s.t. m(ab) <= '
• This approach generates the sum of all ab which satisfy the requirement
that (ab, ') is a partition pair
44
Example
Example: Computing Mm pairs for machine M9
m(AB) = {A,C,E;B,D} =  1'
m(AC) = m(DE) = {A,C,D;B,E} =  2'
m(AD) = m(CE) = {A;B;C,E;D} =  3'
m(AE) = m(CD) =  (I)
m(BC) = m(BE) = {A;B,C,D,E} =  4'
m(BD) = {A,C;B,D;E} =  5'
M( 1') =AB+AD+ CE+BD= {A,B,D;C,E} =  1
M( 2') =AC+ DE = {A,C;B;D,E} = 2
M( 3') =AD+ CE = {A,D;B;C,E} = 3
M( 4') =BC+ BE+AD+CE= {A,D;B,C,E} =  4
M( 5') =BD= {A;B,D;C;E} = 5
Mm pairs: ( (I), (I)), ( 1, 1'), ( 2, 2'), ( 3, 3'), ( 4, 4'), ( 5, 5'), ( (0), (0))
Two closed partitions can be generated by enlarging the m-partition and
refining the M-partition of the Mm pair ( 3, 3'):
1 = {A,D;B;C,E}
 2 = {A;B;C,E;D}
45
State Assignments based on Partition
Pairs
Example (contd.): state assignment with reduced variable dependencies
• For M9: find three partitions, 1,  2 , 3, of two blocks each,
s.t. 1. 2. 3 = (0)
• For each i: determine the corresponding M(i)
• To each partition i: assign a state variable yi
• M(i) is then the partition containing the smallest amount of information
from which we can compute the value of yi assigned to the block of i which
contains the next state of the machine
• If a variable yi assigned to i is to depend on just one other variable
assigned to the blocks of  j: then  j<= M(i) and M(i) can have at most
two blocks
• As an initial selection: let1= 1'
– Since M( 1') consists of two blocks: we can select  2 = M( 1')
– Then  3 = 2'can be selected
(M(1),1) = ({A,B,D;C,E},{A,C,E;B,D})
(M( 2 ), 2) = ({A,D;B;C,E},{A,B,D;C,E})
(M( 3), 3) = ({A,C;B;D,E},{A,C,D;B,E})
• Note that 2 is not an m-partition, but since  2 > 3': M( 2 ) >= M( 3' )
46
Example (Contd.)
Example (contd.): Y1 depends only on y2, since  2 provides all the
information which Y1 requires as specified by M(1)
• To determine the dependencies of Y2 and Y3: check to see if there exists a
partition i <= M( 2) or  j <= M( 3 )
• Since there are no such partitions: check if we can form a product of two
partitions s.t. i.  j<= M( 2 ) or  p. q <= M( 3 )
– This can be accomplished since x2 x1
 2. 3 < M( 2)
y1
Y1
1.  3 < M( 3)
(M( 1), 1)
• Hence,
Y1 = f1(x1,x2,y2)
Y2 = f2(x1,x2,y2,y3)
y2
Y2
(M( 2), 2)
Y3 = f3(x1,x2,y1,y3)
(M( 3), 3)
Y3
Schematic diagram
y3
47
Serial Decomposition
Theorem: Let M be realizable as a serial loop-free connection of m
components C1, C2, …, Cm; then there exists a set of m closed partitions
{1, 2,…, m} s.t.1>= 2 >= … >=m and m = (0).
Conversely, such a set of closed partitions is a sufficient condition
for the existence of a serial decomposition in which Ci is a predecessor of Cj
if and only if i >=j
I
C1
C2
C3
Cm
(a) Cascaded chain. (The double arrows indicate a
transfer of information from all predecessor stages.)
48
Example
Example: Consider M10
• It has three closed partitions and an output-consistent partition:
 0 =  (0)
a = {A,B,G,H;C,D,E,F}
b = {A,B;C,D;E,F;G,H}
 0 = {A,C,E,G;B,D,F,H}
• Since a >b > 0: the machine is decomposable
into three components connected in series s.t. each
component is a two-state machine
• Machine Ca, derived from a, consists of #(a) = 2 states
– Hence, it can be realized with state variable ya
• Component Cb is derived from a partition  1: s.t. a. 1 = b
 1= {A,B,C,D;E,F,G,H}
• Since #( 1) =2: Cb consists of a single variable yb
• Variables ya and yb are assigned to the blocks of b: hence, are
independent of the remaining variable that is assigned to the blocks of
some partition 2, s.t. 2.b = (0)
 2 = 0 = {A,C,E,G;B,D,F,H}
49
Example (Contd.)
Example (contd.): A state assignment based on the above partitions will
yield the following functional relationships:
Ya = fa(x,ya)
Yb = fb(x,ya,yb)
Yc = fc(x,ya,yb,yc)
z = f0(yc)
Schematic diagram and  -lattice:
(I)
x
a
fa
Ya
fb
Yb
fc
Yc
f0
z
b
Ca
Cb
(a) Serial decomposition.
Cc
(0)
(b)
-lattice.
50
Example (Contd.)
Example (contd.): State table for Ca:
• Obtained from the implication graph of a
– States P = (ABGH), Q = (CDEF); output = ya
• Inputs to Cb are x and ya, and its state-dependent output = yb
– States  = (ABCD),  = (EFGH) of  1
• Cb can be reduced to a machine with only two input symbols, since the
next-state entries in three columns of Cb are identical
– Define i1 = x’ + ya, i2 = xya’
• Inputs to Cc are x, ya, and yb, and its output = z
– States:  = (ACEG),  = (BDFH) of  2
51
Parallel Decomposition
Example: Consider machine M11. It has following closed partitions:
a = {A,B;C,D;E,G;F,H}
b = {A,H;B,F;C,G;D,E}
c = {A,B,F,H;C,D,E,G}
• Since a.b = (0): a parallel decomposition
of M11 is possible
– However, since log2#(a) + log2#(b) = 4:
it requires four variables
(I)
Machine Ma
Machine M11
c
Ma
b
a
x
z = z1 z2
Mb
Machine Mb
(0)
 -lattice
z1
z2
Schematic diagram
52
Example (Contd.)
Example (contd.): Seeking another decomposition that requires three
variables
• Determine whether Ma and Mb can each be serially decomposed s.t. both
have identical independent components:
– Such a component can be factored out to serve as a common
predecessor for both Ma and Mb
– Largest component that can be factored out: smallest closed partition
greater thana and b, i.e., a+b
c =a +b = {A,B,F,H;C,D,E,G}
Md
x
Mc
Logic
Me
z = yc zd ze
53
Decompositions with Specified
Components
Example: Consider machine M12
• Determine if M12 can be serially decomposed s.t. C1 is the predecessor
component
• Generate composite machine of M12 and C1
• When C1 is in P: composite machine can be in AP or BP and M12 in A or B
• Cover:  = {A,B;D,E;B,F;C,D}
• Specifying the successor component:  = {A,B’;D’,E;B”,F;C,D”}
• Successor component distinguishes the blocks of a partition s.t.:
 . {A,B’;D’,E;B”,F;C,D”} = (0)
• A possible is:  = {A,D’,D”,F;B’,B”,E,C}
Machine M12
Component C1
Composite machine
54
Synthesis of Multiple Machines
Generalized decomposition problem: given two reduced machines M1 and
M2 with the same input alphabet I, obtain the following
decomposition
M1S
Z1
Mc
I
Z2
M2S
Example: Machines M1, M2 and their implication graphs
• Since the closed graphs are isomorphic: they are equivalent
– They can serve as the predecessor component
I2
I2
I1
I1
(R1R3)
I2
(R2R4)
(a) Machine M1.
I1
I1
(S1S3)
I2
(S2S4)
(b) Machine M2.
55
Example (Contd.)
Example (contd.): Graphs yield:
1 = {R1,R3;R2,R4} and  2 = {S1,S3;S2,S4}
• Denote first (second) blocks of each partition by P (Q)
• Common predecessor:
• Procedure for finding equivalent implication graphs not systematic: depends
on the selection of initial state identifications
– Overcome limitation by using the composite machine
56
Decomposing the Composite Machine
Example (contd.): Composite machine corresponding to M1 and M2 with
initial states R1 and S1 given below
• State-consistent partitions:
R = {R1S1,R1S3;R2S2,R2S4;R3S3,R3S1;R4S4,R4S2}
S = {R1S1,R3S1;R2S2,R4S2;R1S3,R3S3;R2S4,R4S4}
» These partitions correspond to the zero partitions on the set of
states of M1 and M2
» Thus, the implication graphs corresponding to R and S: equivalent
to the state graphs of M1 and M2
» Hence, these partitions are closed w.r.t. the states of the composite
machine
57
Example (Contd.)
Example (contd.): Outputs Z1 and Z2 can be generated by a machine
having three state variables and appropriate output logic, rather
than by two separate machines having a total of four state variables
• Consider the closed partitions:
1 = {R1S1,R2S2,R3S3,R4S4;R1S3,R2S4,R3S1,R4S2}
 2 = {R1S1,R3S3;R2S2,R4S4;R1S3,R3S1;R2S4,R4S2}
• Since  1> 2, a cascade realization results: C1, C2, C3 are two-state
machines
Z1
Composite
machine
(8 states)
I
Z2
(a) Simple realization.
Z1
I
C1
C2
C3
Z2
(b) Decomposition of the composite machine.
58
Example (Contd.)
Example (contd.): Determine if a common predecessor component exists for
M1 and M2: if several such components exist, how to find the
largest one
• A common component Mc exists if and only if we can find a closed partition
s.t. C> R and C > S
C= R + S = {R1S1,R1S3,R3S1,R3S3;R2S2,R2S4,R4S2,R4S4}
• Successor machines M1S, M2S (each consisting of one state variable):
obtained by partitions  1Sand  2S s.t.
C . 1S = R and C . 2S = S
• Possible partitions:
 1S = {R1S1,R1S3,R2S2,R2S4;R3S1,R3S3,R4S2,R4S4}
 2S= {R1S1,R3S1,R2S2,R4S2;R1S3,R3S3,R2S4,R4S4}
• Lattice of all closed partitions:
(I)
C
1
R
S
2
59
(0)