1Machine MinimizationECE 152A – Fall 2006November 30, 2006ECE 152A - Digital Design Principles2Reading Assignment Brown and Vranesic 8 Synchronous Sequential Circuits 8.6 State Minimization 8.6.1 Partitioning Minimization Procedure 8.6.2 Incompletely Specified FSMs2November 30, 2006ECE 152A - Digital Design Principles3Reading 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 TablesNovember 30, 2006ECE 152A - Digital Design Principles4Elimination 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 case3November 30, 2006ECE 152A - Digital Design Principles5Equivalent 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 Sior Sjis the initial state  Moore reduction procedure to find equivalence partitionNovember 30, 2006ECE 152A - Digital Design Principles6Determination of State Equivalence using an Implication Table Find Equivalent Pairs1GCH0HBG1BFF1ACE0EAD1DEC0HFB0CDAzx=1x=0PSNS4November 30, 2006ECE 152A - Digital Design Principles7Determination of State Equivalence using an Implication Table(1) Construct Implication Table for PairwiseComparison(2) First Pass Compare outputs For states to be equivalent, next state and output must be the same Put “X’s” where outputs differNovember 30, 2006ECE 152A - Digital Design Principles8Implication Table (first pass)BCDEFGHAB CDEFGXXXXX XXX XXXXXX X X1GCH0HBG1BFF1ACE0EAD1DEC0HFB0CDAzx=1x=0PSNS5November 30, 2006ECE 152A - Digital Design Principles9Determination of State Equivalence using an Implication Table(3) One column (or row) at a time, find implied pairsNovember 30, 2006ECE 152A - Digital Design Principles10Implication Table (second pass)BCDEFGHAB CDEFGD-FC-HXA-DC-EB-DC-HA-FE-HB-FH-HC-EA-DE-FB-DC-ED-GA-BE-HC-FA-BC-CA-GC-FB-GXXXX XXX XXXXXX X X1GCH0HBG1BFF1ACE0EAD1DEC0HFB0CDAzx=1x=0PSNS6November 30, 2006ECE 152A - Digital Design Principles11Determination 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-ENovember 30, 2006ECE 152A - Digital Design Principles12Implication Table (second pass)BCDEFGHAB CDEFGD-FC-HXA-DC-EB-DC-HA-FE-HB-FH-HC-EA-DE-FB-DC-ED-GA-BE-HC-FA-BC-CA-GC-FB-GXXXX XXX XXXXXX X XSelf-implied pairsSame state pairs7November 30, 2006ECE 152A - Digital Design Principles13Implication Table (second pass)BCDEFGHAB CDEFGD-FC-HXC-EB-DC-HA-FE-HB-FA-DE-FB-DC-ED-GA-BE-HC-FA-BA-GC-FB-GXXXX XXX XXXXXX X XSelf-implied pairsSame state pairsNovember 30, 2006ECE 152A - Digital Design Principles14Determination of State Equivalence using an Implication Table(4) One column (or row) at a time, eliminate implied pairs8November 30, 2006ECE 152A - Digital Design Principles15Implication Table (third pass)BCDEFGHAB CDEFGD-FC-HXC-EB-DC-HA-FE-HB-FA-DE-FB-DC-ED-GA-BE-HC-FA-BA-GC-FB-GXXXX XXX XXXXXX X XXXXXXXX1GCH0HBG1BFF1ACE0EAD1DEC0HFB0CDAzx=1x=0PSNSNovember 30, 2006ECE 152A - Digital Design Principles16Determination 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 pairs9November 30, 2006ECE 152A - Digital Design Principles17Implication Table (fourth pass)BCDEFGHAB CDEFGD-FC-HXC-EB-DC-HA-FE-HB-FA-DE-FB-DC-ED-GA-BE-HC-FA-BA-GC-FB-GXXXX XXX XXXXXX X XXXXXXXXXXX1GCH0HBG1BFF1ACE0EAD1DEC0HFB0CDAzx=1x=0PSNSNovember 30, 2006ECE 152A - Digital Design Principles18Determination 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 table10November 30, 2006ECE 152A - Digital Design Principles19Determination of State Equivalence using an Implication Table Reduced State Table * indicates change from original state table1GCH0HBG1BFF1A*C*C0HFB0CA*Azx=1x=0PSNSNovember 30, 2006ECE 152A - Digital Design Principles20Determination of State Equivalence using an Implication Table Row Matching on an Implication Table Mealy Machine outputs Recall 101 sequence detector (direct Mealy conversion)B,0C,0DD,1A,0CB,0C,0BB,0A,0Ax=1x=0PSNS,z11November 30, 2006ECE 152A - Digital Design Principles21Implication Table Same state pairs Eliminate implied pairs Matching rows No implied pairs B and D are “same state”BCDA-CB-BXA-BB-BB-BC-CCXXABXX√B,0C,0DD,1A,0CB,0C,0BB,0A,0Ax=1x=0PSNS,zNovember 30, 2006ECE 152A - Digital Design Principles22Moore Reduction Procedure States Siand Sjof 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 Sior Sjis the initial stateZvi Kohavi, Switching and Finite Automata Theory12November 30, 2006ECE 152A - Digital Design Principles23Moore Reduction Procedure Two states, Siand 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 Sior Sjis the initial state The sequence which distinguishes these states is called a distinguishing sequence of the pair (Si,Sj)November 30, 2006ECE 152A - Digital Design Principles24Moore 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-equivalent13November 30, 2006ECE 152A - Digital Design Principles25Moore Reduction Procedure The result sought is a partition of the states