Principles Of Digital Design - University Of California .

Principles OfDigital DesignSequential logic and designAnalysis State-based (Moore) Input-based (Mealy)FSM definitionSynthesis State minimization Encoding Optimization and timingCopyright 2010-2013 by Daniel D. GajskiEECS31/CSE31, University of California, Irvine

Analysis of sequential logic Excitation equations are Boolean expressions of the flip-flop inputs. Next-state equations are Boolean expressions representing the nextvalue of the flip- flop outputs. Next-state table ( similar to next-state equations ) gives the nextvalue of flip-flop outputs for each input value and state of flip-flops. Analysis of a sequential circuit is a procedure that produces the nextstate table, state diagram and timing diagram from the logic schematicof the circuit.The analysis gives the answer to the following questions:(a) What is the next state?(b) What is the output?(c) What is the function of the schematic?Copyright 2010-2013 by Daniel D. Gajski2EECS31/CSE31, University of California, Irvine

Analysis of a sequential circuitExample: Modulo-4 counterProblem: Derive the state table & state diagram for the circuit given below.CntLogic schematicD0Q0State diagramState tableCnt 0Cnt 0Q1Q0 00Q0’Cnt 1Q1Q1Q0 11Q1(next) Q0(next)Cnt 00001101100011011Cnt 0Cnt 0Q1’Q 1Q 0Cnt 1Cnt 1D1NEXT STATEPRESENT STATEQ1Q0 01Cnt 1Q1Q0 10Cnt 101101100ClkClock cycle 1 Clock cycle 2 Clock cycle 3 Clock cycle 4ClkD0 Cnt Q0 Cnt’ Q0 Cnt Q0’CntD1 Cnt’ Q1 Cnt Q1’Q0 Cnt Q1Q0’Excitation equationQ1Q0Q0(next) D0 Cnt’ Q0 Cnt Q0’t0 t1Q1(next) D1 Cnt’ Q1 Cnt Q1’Q0 Cnt Q1Q0’Next-state equationCopyright 2010-2013 by Daniel D. Gajskit2t3t4t5Timing diagram3EECS31/CSE31, University of California, Irvine

Analysis of a modulo-4 counterExample: Modulo-4 counter (state-based, Moore-type)Problem: Derive the state, output tables and the state diagram for the circuit below.CntD0YQ0D0 Cnt Q0 Cnt’ Q0 Cnt Q0’Q0’D1 Cnt’ Q1 Cnt Q1’Q0 Cnt Q1Q0’Excitation equationD1Q1Q1’Q0(next) D0 Cnt’ Q0 Cnt Q0’ClkQ1(next) D1 Cnt’ Q1 Cnt Q1’Q0 Cnt Q1Q0’Logic schematicY Q0 Q1PRESENT STATENEXT STATEOUTPUTSQ 1Q 0Q1(next) Q0(next)Y00011011Cnt 00001Cnt 1011010111100Next-state and output equation0001State and output tableCopyright 2010-2013 by Daniel D. Gajski4EECS31/CSE31, University of California, Irvine

Analysis of a modulo-4 counterExample: Modulo-4 counter (state-based, Moore-type)Problem: Derive the state, output tables and the state diagram for the circuit below.CntLogic schematicCnt 1Q1Q0 00YQ0D0State diagramCnt 0Cnt 0Q1Q0 01Y 0Y 0Q0’Cnt 1Cnt 1Cnt 0Cnt 0Cnt 1Q1D1Q1Q0 11Q1Q0 10Y 1Y 0Q1’ClkClkPRESENT STATENEXT STATEOUTPUTSQ 1Q 0Q1(next) Q0(next)Y00011011Cnt 00001Cnt 1011010111100CntQ10001Q0YState and output tablet0 t1t2t3t4t5Timing diagramCopyright 2010-2013 by Daniel D. Gajski5EECS31/CSE31, University of California, Irvine

Analysis of a modulo-4 counterExample: Modulo-4 counter (input-based, Mealy-type)Problem: Derive the state/output table and the state diagram for the circuit below.CntD0Q0YD0 Cnt Q0 Cnt’ Q0 Cnt Q0’Q0’D1 Cnt’ Q1 Cnt Q1’Q0 Cnt Q1Q0’Excitation equationD1Q1Q1’Q0(next) D0 Cnt’ Q0 Cnt Q0’ClkQ1(next) D1 Cnt’ Q1 Cnt Q1’Q0 Cnt Q1Q0’Logic schematicPRESENT STATEQ1Q000011011Y Cnt Q0 Q1NEXT STATE /OUTPUTSQ1(next) Q0(next)/YCnt 000/001/0Cnt 101/010/010/011/011/000/1Next-state and output equationState and output tableCopyright 2010-2013 by Daniel D. Gajski6EECS31/CSE31, University of California, Irvine

Analysis of a modulo-4 counterExample: Modulo-4 counter (input-based, Mealy-type)Problem: Derive the state/output table and the state diagram for the circuit below.CntCnt 0/Y 0Cnt 0/Y 0Cnt 1/Y 0Q1Q0 01Q1Q0 00D0Q0YQ0’Cnt 1/Y 0Cnt 1/Y 1Cnt 0/Y 0Cnt 0/Y 0Cnt 1/Y 0Q1Q0 11D1Q1Q1Q0 10State diagramQ1’ClkClkClock cycle 1 Clock cycle 2 Clock cycle 3 Clock cycle 4Logic schematicPRESENT STATENEXT STATE /OUTPUTSQ1Q000011011CntQ1Q1(next) Q0(next)/YCnt 000/001/0Cnt 101/010/010/011/011/000/1Q0Yt0 t1State and output tableCopyright 2010-2013 by Daniel D. Gajskit2t3t4t5Timing diagram7EECS31/CSE31, University of California, Irvine

Analysis procedure for sequential circuitsLogic schematicDerive excitation equations1Copyright 2010-2013 by Daniel D. GajskiDerive next-state andoutput equations2Generate next-state andoutput tables3GenerateFSM diagram4Developtiming diagram5Simulatelogic schematic68EECS31/CSE31, University of California, Irvine

IAkQ0 , , Qm A1 Finite-state machine modelY1OYnClkThe FSM can be defined abstractly as the quintuple S, I, O, f, h where S, I, and O represent a set of states, set of inputs and a set of outputs, respectively, and fand h represent the next-state and the output functions, that isf : S x ISh : S x IO ( Mealy-type )SO ( Moore-type )where S Q1 x Q 2 x x Qm ,I A1 x A2 x x Ak ,O Y1 x Y 2 x x Yn ,Copyright 2010-2013 by Daniel D. Gajski9EECS31/CSE31, University of California, Irvine

FSM definition of modulo-4 counterExample: Modulo-4 counter (state-based, Moore-type)Problem: Derive the state, output tables and the FSM diagram for the circuit below.CntLogic schematicFSM diagramStayS0YQ0D0StayS1UpQ1Q0 00Q1Q0 01NoNoQ0’UpUpStayStayS3Q1D1S2UpQ1Q0 11Q1Q0 10YesNoQ1’ClkS {S0 , S1, S2, S3} I {Up, Stay} O {Yes, No}PRESENT STATEQ 1Q 000011011NEXT STATEYPRESENTSTATE0001S0S1S2S3S0S1S2S3NEXT STATEOUTPUTSQ1(next) Q0(next)Cnt 00001Cnt 1011010111100State and output tableCopyright 2010-2013 by Daniel D. GajskiStay( SxI S ) OUTPUTS(S O)UpS1S2S3S0NoNoNoYesFSM table10EECS31/CSE31, University of California, Irvine

FSM definition of modulo-4 counterExample: Modulo-4 counter (input-based, Mealy-type)Problem: Derive the state/output table and the FSM diagram for the circuit below.CntLogic schematicFSM diagramStay/NoStay/NoS0D0Q0Q1Q0 00YQ0’S1Up/NoQ1Q0 01Up/NoUp/YesStay/NoStay/NoS3D1S2Up/NoQ1Q0 10Q1Q0 11Q1Q1’ClkS {S0 , S1, S2, S3} I {Up, Stay} O {Yes,No}PRESENT STATENEXT STATE /OUTPUTSQ1Q000011011Q1(next) Q0(next)/YCnt 000/001/0Cnt 101/010/010/011/011/000/1NEXT STATE(SxIS0S1S2S3S0 /NoS1 /NoS2 /NoS3 /NoStayS)/ OUTPUT(SxI O)UpS1 /NoS2 /NoS3 /NoS0 /YesFSM tableState and output tableCopyright 2010-2013 by Daniel D. GajskiPRESENTSTATE11EECS31/CSE31, University of California, Irvine

Finite-state-machine implementationsInputsignalsA1 A2 AkInputsignalsA1 A2 AkClkClk. . . . . . .Q1Q1FF1FF1Y1Y2Q2FF2h:Sf : SxI SO.Stateregister.Y1Y2Q2OutputsignalsFF2h : SxI Of : SxI Comb.logicComblogicFFmComb.logicState signalsInput-based (Mealy)State-based (Moore)Copyright 2010-2013 by Daniel D. Gajski12EECS31/CSE31, University of California, Irvine

Synthesis procedure for sequential logicDesign descriptionDevelop FSM diagramGenerate next-state and output tablesMinimize statesEncode inputs, states, outputsDerive next-state and output equationsChoose memory elementsDerive excitation equationsOptimize logic implementationDerive schematic and timing diagramsSimulate logic schematicVerify functionality and timingCopyright 2010-2013 by Daniel D. Gajski13EECS31/CSE31, University of California, Irvine

State diagram for a modulo-3 up/down counterExample: Modulo-3 up-down counterProblem: Derive the FSM diagram for an up-down, modulo-3 counter. The counter has two inputs:count enable (C) and count direction (D). When C 1, the counter will count in the directionspecified by D, and it will stop counting when C 0. the counter will count up when D 0 anddown when D 1. The counter has one output Y which will be asserted when the counterreaches 2 while counting up, or when it reaches 0 while counting down.CD 10Counter symbolu0DCModulo-3up/downcounterClkCD 10u1CD 10u2Partial state diagram(up and down counting)Yd0CD 11d1CD 11d2CD 11CD 10CD 10CD 0Xu0Partial state diagram(changing direction)CD 10 11 0CD CD 1d0CD 11u1CD 10u0u2 11C0CDCD D 10 CD 111d1CD 11CD 10 11 0CD CD 1d0d2CD 0XCD 11u1CD 0XCD 10 11CD 1 CD 100CD CD11d1CD 0XCD 11u2Final state diagramd2CD 0XCD 11CD 11Copyright 2010-2013 by Daniel D. GajskiCD 0X14EECS31/CSE31, University of California, Irvine

State minimization State minimization reduces the number of states, and therefore, number offlip-flops needed to implemented the circuit. State minimization is based on the concept of behavioral equivalence whichstates that two states are equivalent if they produce the same sequence ofoutput symbols for every sequence of input symbols. More formally, two states, sj and sk in an FSM are said to be equivalent, sj sk ,iff the following two conditions are true.Condition 1: Both states sj and sk produce the same output symbol for everyinput symbol i: that is, h (sj , i ) h (sk , i );Condition 2: Both states have equivalent next sates for every input symbol i :that is, f (sj , i ) f (sk , i ); Minimization procedure:1. partition states into equivalence classes2. construct new FSM with one state for each equivalence classCopyright 2010-2013 by Daniel D. Gajski15EECS31/CSE31, University of California, Irvine

State reduction for modulo-3 counterExample: State reductionProblem: Derive the minimal-state FSM for the modulo-3 counter.( u0 , u1 , u2 , d0 , d1 , d2 )PRESENTSTATENEXT STATE / OUTPUTCD 0Xu0 / 0u1 / 0u2 / 0d0 / 0d1 / 0d2 / 0u0u1u2d0d1d2CD 10u1 / 0u2 / 0u0 / 1u1 / 0u2 / 0u0 / 1CD 11d2 / 1d0 / 0d1 / 0d2 / 1d0 / 0d1 / 00000001000100111100100G0 (u0 , d0 ) G1 (u1 , d1)u0CD 0XCD 10 11 0CD CD 1d0CD 0Xu1G0 G0G1 G1G2 G210G1 G1G2 G2G0 G011G2 G2G0G0G1 G1CD 0XCD 10 11CD 1 CD 100 CDCD 11CD 11d1CD 0XCD 11NextstatesPartitioning into equivalence classesu2PRESENTSTATEG0G1G2d2NEXT STATE / OUTPUTCD 0XG0 / 0G1 / 0G2 / 0CD 10CD 11G1 / 0G2 / 0G0 / 1G2 / 1G0 / 0G1 / 0CD 0XFinal next-state/output tableCD 11Copyright 2010-2013 by Daniel D. GajskiG2 (u2 , d2)CD 0XCD 10CD 0XOutputvalues010000001Partition into arrayswith the same nextstateInitial next-state/output tableCD 0XPartition into arrayswith the sameoutput16EECS31/CSE31, University of California, Irvine

State reduction with implication tableExample: State reductions with implication table (modified from previous example).Problem: Find the minimal number of states for the FSM specified by the table below.s1s2PRESENTSTATEs3s4s5s6s0s1s2s3s4CD 0Xu0 / 0u0 / 0u2 / 0d0 / 0d2 / 0d2 / 0u0u1u2d0d1d2 s2 ,s6 s0 ,s4 s3 ,s4 NEXT STATEs5CD 10u1 / 0u2 / 0u0 / 1u1 / 0u2 / 0u0 / 1CD 11d2 / 1d0 / 0d1 / 0d2 / 1d0 / 0d1 / 0Next-state and output tableImplication tableStep 1:Enter x for any pair of statesthat differ in output valuesStep2:Enter implied equivalent statesfor every pair of statesStep3:Step4:Equivalenceclasses: u0, d0 u1 Enter x for the non equivalentnext-state pair d1 u2, d2 Form equivalence classes usingtransitivity : s1 s2 & s2 s3 s1 s3u1u2d0d1 u0 ,d2 d2u0u1u2d0d1Implication table for the table aboveCopyright 2010-2013 by Daniel D. Gajski17EECS31/CSE31, University of California, Irvine

State 00110000100 The cost and delay of FSM implementationdepends on encoding of symbolic states. For example, four states can be encoded in4! 24 different ways. There are more than n! different encodingsfor n states. Exploration of all encodings is impossibleThus, we use different heuristics such as minimum-bit change prioritized adjacency one-hot encoding others24 encodings of four statesCopyright 2010-2013 by Daniel D. Gajski18EECS31/CSE31, University of California, Irvine

Minimum-bit change Minimum-bit change strategy assigns codes to states so that the totalnumber of bit changes for all state transitions is minimized. In other words, if every arc in the state diagram has a weight that is equal tothe number of bits by which the source and destination encodings differ, thenthe optimal encoding would be the one that minimizes the sum of all theseweights. Example: Two different encodings for modulo-4 binary counter.100012211111010011111s0s0Straightforward encodingCopyright 2010-2013 by Daniel D. Gajski100Minimum-bit-change encoding19EECS31/CSE31, University of California, Irvine