1ECE 274 - Digital LogicChapter 8: Synchronous Sequential Circuits Lecture 20 - State Minimization Implication Tables (not in book) Partitioning Method (8.6)2xyif x = 1,1,0,0then y = 0,1,1,0,0xstateyxstateyS0 S0S1 S1S1 S1S2 S0S2 S0S0S1y=0y=1S2y=0S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0S1y=0 y=1x’ xxx’For the same sequence of inputs,the output of the two FSMs is the sameECE 274 - Digital Logic State Reduction (State Minimization) Goal: Reduce number of states in FSM withoutchanging behavior Fewer states potentially reduces size of state register Consider the two FSMs below with input sequence x =1, 1, 0, 03S0 S1y=0y=1S2y=0S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yStates S0 and S2 equivalentStates S1 and S3 equivalentECE 274 - Digital Logic State Reduction: Equivalent StatesTwo states are equivalent if:1. They assign the same values to outputs S0 and S2 both assign yto 0, S1 and S3 both assign yto 12. AND, for all possible sequences of inputs, the FSM outputs will be the same starting from either state e.g. say x=1,1,0,0,… starting from S1, y=1,1,0,0,… starting from S3, y=1,1,0,0,…S0,S2S1,S3y=0y=1x’ xxx’merge equivalent states4S1y=0y=1S2y=1S3y=1xxxxx’x’x’x’Inputs: x; Outputs: yS0S1y=0 y=1S2y=1S3y=1xxxxx’x’x’x’S0Start from S1, x=0S1y=0 y=1S2y=1S3y=1xxxxx’x’x’x’S0Start from S3, x=0ECE 274 - Digital Logic State Reduction: Example with no Equivalencies Another example… State S0 is not equivalent with any other state since its output (y=0) differs from other states’output Consider state S1 and S3 Output Assignment Initially the same (y=1) All possible inputs, yield same outputs From S1, when x=0, go to S2where y=1 From S3, when x=0, go to S0where y=0 Outputs differ, so S1 and S3are not equivalent.Continue checking all possibilities5RedundantRemove redundant state pairsDiagonalRemove state pairs along the diagonal since a state is equivalent to itselfS0 S1y=0y=1S2y=0S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yECE 274 - Digital Logic State Reduction with Implication Tables State reduction through visual inspection (what we did in the last few slides) isn’t reliable and cannot be automated – a more methodical approach is needed: implication tablesTo compare every pair of states, construct a table of state pairsS0S0 S1 S2 S3S1S2S3S0 S1 S2S1S2S36S0S1y=0y=1S2y=0S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3ECE 274 - Digital Logic State Reduction with Implication Tables Step 1: Mark (with an X) state pairs with different outputs as non-equivalent:  (S1,S0): At S1, y=1 and at S0, y=0. So S1 and S0 are non-equivalent.  (S2, S0): At S2, y=0 and at S0, y=0. So we don’t mark S2 and S0 now.  (S2, S1): Non-equivalent (S3, S0): Non-equivalent (S3, S1): Don’t mark (S3, S2): Non-equivalent After first pass S2 & S0 might be equivalent S3 & S1 might be equivalentOnly if their next states are equivalent7S0S1y=0y=1S2y=0S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3(S3, S1)(S2, S0)(S3, S1)(S0, S2)ECE 274 - Digital Logic State Reduction with Implication Tables Step 2: Check each unmarked state pair’s next states Start by listing what each unmarked state pair’s next states are for every combination of inputs (S2, S0)  From S2, when x=1 go to S3 From S0, when x=1 go to S1 So we add (S3, S1) as a next state pair From S2, when x=0 go to S2 From S0, when x=0 go to S0 So we add (S2, S0) as a next state pair (S3, S1)  By a similar process, we add the next state pairs (S3, S1) and (S0, S2)8S0S1y=0y=1S2y=0S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3(S3, S1)(S2, S0)(S3, S1)(S0, S2)ECE 274 - Digital Logic State Reduction with Implication Tables Step 3: Next we check every unmarked state pair’s next state pairs We mark the state pair if one of its next state pairs is marked (i.e. not equivalent) (S2, S0) Next state pair (S3, S1) is not marked Next state pair (S2, S0) is not marked So we do nothing and move on (S3, S1) Next state pair (S3, S1) is not marked Next state pair (S0, S2) is not marked So we do nothing and move on9S0,S2S1,S3y=0y=1x’ xxx’S0S1y=0y=1S2y=0S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3(S3, S1)(S2, S0)(S3, S1)(S0, S2)ECE 274 - Digital Logic State Reduction with Implication Tables We just made one passthrough the implication table Make additional passes until no change occurs Step 4: merge the unmarked state pairs as they are equivalent10ECE 274 - Digital LogicState Minimization Using Implication TablesStep Description1 Mark state pairs having different outputs as nonequivalentStates having different outputs obviously cannot be equivalent2 For each unmarked state pair, write the next state pairs for the same input values3 For each unmarked state pair, mark state pairs having nonequivalent next-state pairs as nonequivalent. Repeat this step until no change occurs, or until all states are marked.States with nonequivalent next states for the same input values cannot be equivalent. Each time through this step is called a pass.4 Merge remaining state pairs Remaining state pairs must be equivalent.11S0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3S0 S1 S2S1S2S3S0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3S0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3S0 S1 S2S1S2S3S0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3S0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yS0 S1 S2S1S2S3S0 S1 S2S1S2S3S0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: yECE 274 - Digital Logic State Reduction Example Given FSM on the right Step 1: Mark state pairs having different outputs as nonequivalent12S0S1y=0y=1S2y=1S3y=1xxxx’x’xx’ x’Inputs: x; Outputs: y(S2, S2)S0 S1 S2S1S2S3(S3, S1)(S0, S2)(S3, S1)(S0, S2)(S3, S3)ECE 274 - Digital Logic State Reduction Example Given FSM on the right Step 1: Mark state pairs having different outputs as nonequivalent  Step 2: For each unmarked state pair, write the next state pairs for the same input valuesFor pair (S2, S1)X = 0 S2 goes to S2S1 goes to S2X = 1 S2 goes to S3S1 goes to S1For pair (S3, S1)X = 0 S3 goes to