3/20/25, 7:44 AM Structure OF Sequential Machines
Chapter 12
Structure of sequential machines
Present Next state Output
state
A A D 0 1
B A C 0 0
C C B 0 0
D C A 0 1
Table 1: machine M1
a) Assignment
A 0 00 10 0 1
B 01 00 11 0 0
C 1 11 01 0 0
D 10 11 00 0 1
Table 2: Excitation and output taken for machine M1
b) Assignment
A 0 00 11 0 1
B 01 00 10 0 0
C 1 10 01 0 0
D 11 10 00 0 1
Logical equations corresponding to which are derived from the excitation and output are
about:blank 1/14
3/20/25, 7:44 AM Structure OF Sequential Machines
Circuit diagram
about:blank 2/14
3/20/25, 7:44 AM Structure OF Sequential Machines
State assignments using partitions :
Closed partitions: A partition on the set of states of sequential machine N is said to be closed if ,for
every two states and which are in the same block of and any input in the states and are
in 0 common block of .
denotes successor of .
A 0 00 10 0 1
B 01 00 01 0 0
C 1 11 01 0 0
D 0 11 00 0 1
Y1
Y1
zero partition
Example : for machine M1 in table 1
Present Next state Output
state
A A D 0 1
B A C 0 0
C C B 0 0
D C A 0 1
closed covers of A,B,C,D.
The 0 and 1 successor of AC are AC and BD. The only successor of BD is AC.
Assign P to AC and Q to BD.
about:blank 3/14
3/20/25, 7:44 AM Structure OF Sequential Machines
Reduction of the functional dependency of the state variables.
Example : Consider machine M2 given in table below.
Present
Next state Output Z
state
A H B 0
B F A 0
C G D 0
D E C 1
E A C 0
F C D 0
G B A 0
H D B 0
The partitions are
Select the partition such that
0 1
about:blank 4/14
3/20/25, 7:44 AM Structure OF Sequential Machines
0 1
0 1
A 00 100 010 0
B 01 111 000 0
C 011 110 001 0
D 00 101 011 1
E 10 000 011 0
F 111 011 001 0
G 11 010 000 0
H 10 001 010 0
Lattice of closed partitions
Theorem: of two closed partitions on the set of states of M are also closed.
Proof: let be two closed partitions on the states of M, we shall show that is closed.
Let B an arbitrary block of
Since is the intersection of some block of and of ,then is contained in both B1 and B2.
about:blank 5/14
3/20/25, 7:44 AM Structure OF Sequential Machines
Since are closed the –successor of is also contained within some block of and
of , where is the –successor of 1 .
There fore, is contained within the intersection
But the intersection is the contained in a block of and is contained in block of
There fore is closed.
is lower bound.
is the upper bound..
Therefore, the set of closed partitions on the states of a machine is closed under + and . Binary
operations and therefore forms a lattice. This is referred to as -lattice.
-lattice can be determined in two steps.
1) For every pair of states determine ..
2) Obtain all possible sums of the basic partitions.
Example: determine the -lattice for machine M3 shown in table below.
Present state Next state
A E B
B E A
C D A
D C F
E F C
F E C
B AB;C;D;E
C ABCF;D ABCF;D
D
E ABCF;DE
F ABCF;DE ABCF;DE ABCF;DE ABCF;DE
A B C D E
Fig : derivation of basic partitions
Let
about:blank 6/14
3/20/25, 7:44 AM Structure OF Sequential Machines
is closed.
AC AB;DE ABCF;DE
AC AB; DE ABCF; DE
AD CE; BF ABCF; DE; DF
AE EF; BC ABCF; DE; EF
AF BC DE CF (DE and AC)
BC DE CF (DE and AC) ABCF; DE
BD CE, AF BC ABCF; DE; CE
BE EF, AC ABCF; DE; EF
BF AC ABCF; DE
CD CD, AF ABCF; DE; DF
CF AC,DE ABCF; DE
DE CF ABCF; DE
DF CE, CF ABCF; DE; DF
EF EF
Partitions are
-lattice
about:blank 7/14
3/20/25, 7:44 AM Structure OF Sequential Machines
Reduction of output dependency :
Table: machine M4
Present Next state Output
state
A B D 1 0
B A C 0 1
C D A 0 1
D C B 1 0
0 1
0 1
0 1
about:blank 8/14
3/20/25, 7:44 AM Structure OF Sequential Machines
A 00 A 00
B 0 B 01
C 1 C 1
D 1 D 1
For and assignment…
For α assignment
A 0 01 11 1 0
B 01 00 01 0 1
C 1 11 00 0 1
D 11 10 01 1 0
Logical equations for assignment
For assignment
Present state
A 0 01 10 1 0
B 01 00 11 0 1
C 1 11 00 0 1
D 10 10 01 1 0
about:blank 9/14
3/20/25, 7:44 AM Structure OF Sequential Machines
Logical equations for assignment
Input Partition is
Output Partition is
A partition on the states of machine M is said to be output consisted if, for every block of
and every input, all the states contained in the block has output.
INPUT INDEPENDENCE AND AUTONOMOUS CLOCK
Consider a machine :
Present Next state Output
state
A D C 0 1
B C D 0 0
C E F 0 1
D F F 0 0
E B A 0 1
F A B 0 0
Input partition is a closed partition.
Output partition
since ,
Assign
00 01 10
about:blank 10/14
3/20/25, 7:44 AM Structure OF Sequential Machines
0 1
Table assignment:
Next state Output
Present state
A 000 011 010 0 1
B 001 010 011 0 0
C 01 100 101 0 1
D 011 101 101 0 0
E 100 001 000 0 1
F 10 000 001 0 0
Logical equations
Schematic diagram
AUTONOMOUS CLO
about:blank 11/14
3/20/25, 7:44 AM Structure OF Sequential Machines
Clock period =p=3
Covers and generation of closed partitions using state splitting
Table machine
Present Next state Output
state
A A B 0 1
B C B 0 0
C A C 0 0
No closed set exits. So add .
Present Next state Output
state
A A B 0 1
B C B 0 0
C A C 0 0
C’ A C” 0 0
C” A C” 0 0
0 1
Choose partition such that
0 1
about:blank 12/14
3/20/25, 7:44 AM Structure OF Sequential Machines
Next state Output
Present state
A 00 00 10 0 1
B 10 01 10 0 0
C 0 00 11 0 0
D 11 00 11 0 0
Logical equations are
When C’ and C ‘’ are equivalent covers and is a
closed cover.
Next state
Present state
AC P P Q
BC Q P P
IMPLICATION GRAPH:
Definition: A closed IMPLICATION GRAPH is a subgraph of an implication graph such that
For every vertex in the subgraph all outgoing arcs and their terminating vertices also belong to
the subgraph.
Every state of M is represented by atleast 1 vertex.
For machine M6
CLOSED GRAP
about:blank 13/14
3/20/25, 7:44 AM Structure OF Sequential Machines
about:blank 14/14