Machine Minimization

ECE 152A – Winter 2012

Reading Assignment

 Brown and Vranesic

 8 Synchronous Sequential Circuits
 8.6 State Minimization
 8.6.1 Partitioning Minimization Procedure
 8.6.2 Incompletely Specified FSMs

March 7, 2012 ECE 152A - Digital Design Principles 2

Reading Assignment

 Roth
 15 Reduction of State Tables / State Assignment
 15.1 Elimination of Redundant States
 15.2 Equivalent States
 15.3 Determination of State Equivalence Using an
Implication Table
 15.4 Equivalent Sequential Circuits
 15.5 Incompletely Specified State Tables

March 7, 2012 ECE 152A - Digital Design Principles 3

Elimination of Redundant States

 Row Matching
 Recall CD player controller
 Mealy implementation contained two sets of rows with
same next state and output
 Eliminate redundant states
 Row matching doesn’t identify “equivalent
states”
 Row matching identifies “same state”
 Equivalent states are the more general case

March 7, 2012 ECE 152A - Digital Design Principles 4

Equivalent States

 Definitions of equivalent states

 Roth : 2 states equivalent iff for every single input
x, outputs are the same and next states are
equivalent (as opposed to row matching)
 Pairwise comparison using implication table

 Kohavi : Iff for every possible input sequence the

same output sequence will be produced
regardless of whether Si or Sj is the initial state
 Moore reduction procedure to find equivalence partition

March 7, 2012 ECE 152A - Digital Design Principles 5

Determination of State Equivalence using
an Implication Table
 Find Equivalent Pairs
NS
PS x=0 x=1 z
A D C 0
B F H 0
C E D 1
D A E 0
E C A 1
F F B 1
G B H 0
H C G 1

March 7, 2012 ECE 152A - Digital Design Principles 6

Determination of State Equivalence using
an Implication Table
(1) Construct Implication Table for Pairwise
Comparison
(2) First Pass
 Compare outputs
 For states to be equivalent, next state and output must
be the same
 Put “X’s” where outputs differ

March 7, 2012 ECE 152A - Digital Design Principles 7

Implication Table (first pass)
NS
B
PS x=0 x=1 z
A D C 0
C X X B F H 0
C E D 1

D X D A E 0
E C A 1
F F B 1
E X X X G B H 0
H C G 1

F X X X

G X X X

H X X X X

A B C D E F G

March 7, 2012 ECE 152A - Digital Design Principles 8

Determination of State Equivalence using
an Implication Table
(3) One column (or row) at a time, find implied
pairs

March 7, 2012 ECE 152A - Digital Design Principles 9

Implication Table (second pass)
D-F NS
B
C-H PS x=0 x=1 z
A D C 0
C X X B F H 0
C E D 1
A-D A-F
D X D A E 0
C-E E-H E C A 1

C-E F F B 1
E X X X
A-D G B H 0
H C G 1
E-F C-F
F X X X A-B
B-D
B-D B-F A-B
G C-H H-H X E-H X X

C-E C-C C-F

H X X D-G X A-G B-G X

A B C D E F G

March 7, 2012 ECE 152A - Digital Design Principles 10

Determination of State Equivalence using
an Implication Table
(3) One column (or row) at a time, find implied
pairs (cont)
 Remove self implied pairs
 A-D in cell A-D
 C-E in cell C-E
 Remove same state pairs
 H-H in cell B-G
 C-C in cell H-E

March 7, 2012 ECE 152A - Digital Design Principles 11

Implication Table (second pass)
D-F
B
C-H
Self-implied pairs
C X X

A-D A-F
D X
C-E E-H
C-E Same state pairs
E X X X
A-D
E-F C-F
F X X X A-B
B-D
B-D B-F A-B
G C-H H-H X E-H X X

C-E C-C C-F

H X X D-G X A-G B-G X

A B C D E F G

March 7, 2012 ECE 152A - Digital Design Principles 12

Implication Table (second pass)
D-F
B
C-H
Self-implied pairs
C X X

A-F
D C-E X
E-H

E X X A-D X Same state pairs

E-F C-F
F X X X A-B
B-D
B-D A-B
G B-F X X X
C-H E-H
C-E C-F
H X X X A-G X
D-G B-G

A B C D E F G

March 7, 2012 ECE 152A - Digital Design Principles 13

Determination of State Equivalence using
an Implication Table
(4) One column (or row) at a time, eliminate
implied pairs

March 7, 2012 ECE 152A - Digital Design Principles 14

Implication Table (third pass)

B X
D-F
C-H PS x=0
NS
x=1 z
A D C 0
C X X B F H 0
C E D 1
A-F
D C-E X
E-H
X D
E
A
C
E
A
0
1
F F B 1
E X X A-D X G B H 0
H C G 1
C-F
F X X
X
E-F
B-D
X
X
A-B
B-D A-B
G C-H X
B-F X
X
E-H X X

C-E C-F
H X X D-G X A-G
X
B-G X

A B C D E F G

March 7, 2012 ECE 152A - Digital Design Principles 15

Determination of State Equivalence using
an Implication Table
(5) Next pass, one column (or row) at a time,
eliminate implied pairs
(6) Continue until pass results in no further
elimination of implied pairs

March 7, 2012 ECE 152A - Digital Design Principles 16

Implication Table (fourth pass)

B X
D-F
C-H PS x=0
NS
x=1 z
A D C 0
C X X B F H 0
C E D 1
A-F
D C-E X
E-H
X D
E
A
C
E
A
0
1
F F B 1
E X X A-D X G B H 0
H C G 1
C-F
F X X
X
E-F
B-D
X
X
A-B
B-D A-B
G
X X
C-H
B-F X
X
E-H X X

C-E C-F
H X X
X
D-G X
X X
A-G
B-G X

A B C D E F G

March 7, 2012 ECE 152A - Digital Design Principles 17

Determination of State Equivalence using
an Implication Table
(7) Combine equivalent states (based on
coordinates of cells, not contents)
 A ≡ D, C ≡ E in example
 Equivalence is pairwise
 A ≡ B, B ≡ C implies A ≡ C (transitive)

(8) Construct reduced state table

March 7, 2012 ECE 152A - Digital Design Principles 18

Determination of State Equivalence using
an Implication Table
 Reduced State Table
 * indicates change from original state table
NS
PS x=0 x=1 z
A A* C 0
B F H 0
C C* A* 1
F F B 1
G B H 0
H C G 1

March 7, 2012 ECE 152A - Digital Design Principles 19

Determination of State Equivalence using
an Implication Table
 Row Matching on an Implication Table
 Mealy Machine outputs
 Recall 101 sequence detector (direct Mealy conversion)

NS,z
PS x=0 x=1
A A,0 B,0
B C,0 B,0
C A,0 D,1
D C,0 B,0

March 7, 2012 ECE 152A - Digital Design Principles 20

Implication Table

 Same state pairs

A-C
 Eliminate implied B X
B-B

pairs C X X

 Matching rows A-B

 No implied pairs
D X
B-B
B-B
√
C-C
X

 B and D are “same A B C

state” NS,z
PS x=0 x=1
A A,0 B,0
B C,0 B,0
C A,0 D,1
D C,0 B,0

March 7, 2012 ECE 152A - Digital Design Principles 21

Moore Reduction Procedure

 States Si and Sj of machine M are said to be

equivalent If and only if, for every possible
input sequence, the same output sequence
will be produced regardless of whether Si or
Sj is the initial state

Zvi Kohavi,
Switching and Finite Automata Theory

March 7, 2012 ECE 152A - Digital Design Principles 22

Moore Reduction Procedure

 Two states, Si and Sj, of machine M are

distinguishable if and only if there exists at
least one finite input sequence which, when
applied to M, causes different output
sequences depending on whether Si or Sj is
the initial state
 The sequence which distinguishes these states is
called a distinguishing sequence of the pair (Si,Sj)

March 7, 2012 ECE 152A - Digital Design Principles 23

Moore Reduction Procedure

 If there exists for pair (Si,Sj) a distinguishing

sequence of length k, the states in (Si,Sj) are
said to be k-distinguishable
 States that are not k-distinguishable are said to be
k-equivalent

March 7, 2012 ECE 152A - Digital Design Principles 24

Moore Reduction Procedure

 The result sought is a partition of the states of

M such that two states are in the same block
if and only if they are equivalent
 P0 corresponds to 0-distinguishablity (includes all
states of machine M)
 P1 is obtained simply by inspecting the table and
placing those states having the same outputs,
under all inputs, in the same block
 P1 establishes the sets of states which are 1-equivalent

March 7, 2012 ECE 152A - Digital Design Principles 25

Moore Reduction Procedure

 Obtain partition P2
 This step is carried out by splitting blocks of P1,
whenever their successors are not contained in a
common block of P1
 Iterate process of splitting blocks
 If for some k, Pk+1 = Pk, the process terminates
and Pk defines the sets of equivalent states of the
machine
 Pk is thus called the equivalence partition
 The equivalence partition is unique

March 7, 2012 ECE 152A - Digital Design Principles 26

Moore Reduction Procedure

 Recall state table from earlier example

NS
PS x=0 x=1 z
A D C 0
B F H 0
C E D 1
D A E 0
E C A 1
F F B 1
G B H 0
H C G 1

March 7, 2012 ECE 152A - Digital Design Principles 27

Moore Reduction Procedure

 P0 = (ABCDEFGH)
 P1 is obtained by splitting states having
different outputs NS

 P1 =(ABDG)(CEFH) PS
A
x=0
D
x=1
C
z
0

 Block 1 = ABDG, Block 2 = CEFH B F H 0

C E D 1
D A E 0
E C A 1
F F B 1
G B H 0
H C G 1

March 7, 2012 ECE 152A - Digital Design Principles 28

Moore Reduction Procedure

 Obtain P2
 Block 1 = ABDG, Block 2 = CEFH

NS
D (1) F (2) PS x=0 x=1 z
A B A D C 0
C (2) H (2) B F H 0
C E D 1
D A E 0
E C A 1
A (1) B (1) F F B 1

D G G B H 0

E (2) H (2) H C G 1

March 7, 2012 ECE 152A - Digital Design Principles 29

Moore Reduction Procedure

 Obtain P2 (cont)
 Block 1 = ABDG, Block 2 = CEFH

E (2) C (2) NS

C E PS x=0 x=1 z
A D C 0
D (1) A (1)
B F H 0
C E D 1
D A E 0
E C A 1
F (2) C (2) F F B 1

F H G B H 0

B (1) G (1) H C G 1

March 7, 2012 ECE 152A - Digital Design Principles 30

Moore Reduction Procedure

 Split B out of block 1

 B is “2 distinguishable” from A, D and G
 No states of block 2 are “2 distinguishable”
 P2 = (ADG)(B)(CEFH)
 Block 1 = ADG
 Block 2 = B
 Block 3 = CEFH

March 7, 2012 ECE 152A - Digital Design Principles 31

Moore Reduction Procedure

 Obtain P3 PS
NS
x=0 x=1 z

 P2 = (ADG)(B)(CEFH) A
B
D
F
C
H
0
0
C E D 1
D A E 0
E C A 1
D (1) A (1) B (2) F F B 1

A D G G B H 0

C (3) E (3) H (3) H C G 1

E (3) C (3) F (3) C (3)

C E F H
D (1) A (1) B (2) G (1)

March 7, 2012 ECE 152A - Digital Design Principles 32

Moore Reduction Procedure

 Obtain P3 (cont)
 Split G from block 1
 G is 3-distinguishable from A and D
 Split F from block 3
 F is 3-distinguishable from C, E and H
 P3 = (AD)(G)(B)(CEH)(F)
 Block 1 = AD, block 2 = G, block 3 = B,
block 4 = CEH and block 5 = F

March 7, 2012 ECE 152A - Digital Design Principles 33

Moore Reduction Procedure

 Obtain P4 NS
PS x=0 x=1 z
 P3 = (AD)(G)(B)(CEH)(F) A D C 0
B F H 0
C E D 1
D A E 0
E C A 1
D (1) A (1) F F B 1
A D G B H 0

C (4) E (4) H C G 1

E (4) C (4) C (4)

C E H
D (1) A (1) G (2)

March 7, 2012 ECE 152A - Digital Design Principles 34

Moore Reduction Procedure

 Obtain P4 (cont)
 Split H from block 4
 H is 4-distinguishable from C and E
 P4 = (AD)(G)(B)(CE)(H)(F)
 Block 1 = AD, block 2 = G, block 3 = B,
block 4 = CEH, block 5 = H and block 6 = F

March 7, 2012 ECE 152A - Digital Design Principles 35

Moore Reduction Procedure

 Obtain P5
 P4 = (AD)(G)(B)(CE)(H)(F)

NS
D (1) A (1) PS x=0 x=1 z
A D A D C 0
C (4) E (4) B F H 0
C E D 1
D A E 0
E C A 1

E (4) C (4) F F B 1
G B H 0
C E
H C G 1
D (1) A (1)

March 7, 2012 ECE 152A - Digital Design Principles 36

Moore Reduction Procedure

 Obtain P5 (cont)
 No blocks split from P5
 P5 = P4 = (AD)(G)(B)(CE)(H)(F)
 P5 = P4 = equivalence partition
 Same result as implication table

March 7, 2012 ECE 152A - Digital Design Principles 37

Reduction of Incompletely Specified
State Tables
 Use “modified row matching” to combine
states

NS Z
PS x=0 x=1 x=0 x=1
A - B - - A and C can be combined
B C D - - A and D can be combined
C A - 0 -
C and D cannot (outputs differ)
D A - 1 -

March 7, 2012 ECE 152A - Digital Design Principles 38

Reduction of Incompletely Specified
State Tables
 Using an Implication Table
 State pairs are compatible, not equivalent
 States must be “pairwise” compatible
 ABC requires A-B, B-C and A-C
 Compatible relationship is not transitive like equality
 Compatible pairs must be grouped and included in
reduced machine

March 7, 2012 ECE 152A - Digital Design Principles 39

Reduction of Incompletely Specified
State Tables
 √ indicates “compatible pair”

A-C and A-D are compatible pairs

C-D are not compatible pairs
B B-D

√ A-C A-B implies B-D; B-D implies A-C

C
→ requires ABCD grouping
D √ A-C X B-C implies A-C; A-B implies B-D
→ requires ABCD grouping
A B C B-D implies A-C
→ √

March 7, 2012 ECE 152A - Digital Design Principles 40

Reduction of Incompletely Specified
State Tables
 Heuristic (non-deterministic) process
 Requires “trial and error”
 Not necessarily minimal

NS Z
PS x=0 x=1 x=0 x=1
AC AC BD 0 -
BD AC BD 1 -

March 7, 2012 ECE 152A - Digital Design Principles 41