CS 150 - Fall 2000 - Sequential Logic Implementation - 1 Sequential Logic Implementation zSequential Circuits yPrimitive sequential elements yCombinational. - презентация

1 CS Fall Sequential Logic Implementation - 1 Sequential Logic Implementation zSequential Circuits yPrimitive sequential elements yCombinational logic zModels for representing sequential circuits yFinite-state machines (Moore and Mealy) yRepresentation of memory (states) yChanges in state (transitions) zBasic sequential circuits yShift registers yCounters zDesign procedure yState diagrams yState transition table yNext state functions

2 CS Fall Sequential Logic Implementation - 2 Abstraction of State Elements zDivide circuit into combinational logic and state zLocalize feedback loops and make it easy to break cycles zImplementation of storage elements leads to various forms of sequential logic Combinational Logic Storage Elements Outputs State OutputsState Inputs Inputs

3 CS Fall Sequential Logic Implementation - 3 Forms of Sequential Logic zAsynchronous sequential logic – state changes occur whenever state inputs change (elements may be simple wires or delay elements) zSynchronous sequential logic – state changes occur in lock step across all storage elements (using a periodic waveform - the clock) Clock

4 CS Fall Sequential Logic Implementation - 4 In = 0 In = 1 In = 0In = Finite State Machine Representations zStates: determined by possible values in sequential storage elements zTransitions: change of state zClock: controls when state can change by controlling storage elements zSequential Logic ySequences through a series of states yBased on sequence of values on input signals yClock period defines elements of sequence

5 CS Fall Sequential Logic Implementation - 5 Example Finite State Machine Diagram zCombination lock from first lecture reset S3 closed mux=C1 equal & new not equal & new not new S1S2OPEN ERR closed mux=C2 equal & new closed mux=C3 equal & new open

6 CS Fall Sequential Logic Implementation - 6 Can Any Sequential System be Represented with a State Diagram? zShift Register yInput value shown on transition arcs yOutput values shown within state node DQDQDQ IN OUT1OUT2OUT3 CLK

7 CS Fall Sequential Logic Implementation bit up-counter Counters are Simple Finite State Machines zCounters yProceed thru well-defined state sequence in response to enable zMany types of counters: binary, BCD, Gray-code y3-bit up-counter: 000, 001, 010, 011, 100, 101, 110, 111, 000,... y3-bit down-counter: 111, 110, 101, 100, 011, 010, 001, 000, 111,...

8 CS Fall Sequential Logic Implementation - 8 How Do We Turn a State Diagram into Logic? zCounter yThree flip-flops to hold state yLogic to compute next state yClock signal controls when flip-flop memory can change xWait long enough for combinational logic to compute new value xDon't wait too long as that is low performance

9 CS Fall Sequential Logic Implementation - 9 FSM Design Procedure zStart with counters ySimple because output is just state ySimple because no choice of next state based on input zState diagram to state transition table yTabular form of state diagram yLike a truth-table zState encoding yDecide on representation of states yFor counters it is simple: just its value zImplementation yFlip-flop for each state bit yCombinational logic based on encoding

10 CS Fall Sequential Logic Implementation bit up-counter current state next state FSM Design Procedure: State Diagram to Encoded State Transition Table zTabular form of state diagram zLike a truth-table (specify output for all input combinations) zEncoding of states: easy for counters – just use value

11 CS Fall Sequential Logic Implementation - 11 C3C2C1N3N2N N1:= C1' N2:= C1C2' + C1'C2 := C1 xor C2 N3:= C1C2C3' + C1'C3 + C2'C3 := C1C2C3' + (C1' + C2')C3 := (C1C2) xor C3 notation to show function represent input to D-FF Implementation zD flip-flop for each state bit zCombinational logic based on encoding C1 C2 C3 N C1 C2 C3 N C1 C2 C3 N1

12 CS Fall Sequential Logic Implementation - 12 D Q Q Implementation (cont'd) zProgrammable Logic Building Block for Sequential Logic yMacro-cell: FF + logic xD-FF xTwo-level logic capability like PAL (e.g., 8 product terms)

13 CS Fall Sequential Logic Implementation - 13 InC1C2C3N1N2N N1:= In N2:= C1 N3:= C2 Another Example zShift Register yInput determines next state DQDQDQ IN OUT1OUT2OUT3 CLK

14 CS Fall Sequential Logic Implementation - 14 More Complex Counter Example zComplex Counter yRepeats five states in sequence yNot a binary number representation zStep 1: Derive the state transition diagram yCount sequence: 000, 010, 011, 101, 110 zStep 2: Derive the state transition table from the state transition diagram Present StateNext State CBAC+B+A ––– ––– ––– note the don't care conditions that arise from the unused state codes

15 CS Fall Sequential Logic Implementation - 15 C+ := A B+ := B' + A'C' A+ := BC' More Complex Counter Example (contd) zStep 3: K-maps for Next State Functions 0 00X100X1 0XX10XX1 A B C C+1 11X011X0 0XX10XX1 A B C B+ 01X101X1 0XX00XX0 A B C A+

16 CS Fall Sequential Logic Implementation - 16 Self-Starting Counters (contd) zRe-deriving state transition table from don't care assignment 0101 A B C C A B C B A B C A+ Present StateNext State CBAC+B+A

17 CS Fall Sequential Logic Implementation - 17 Self-Starting Counters zStart-up States yAt power-up, counter may be in an unused or invalid state yDesigner must guarantee it (eventually) enters a valid state zSelf-starting Solution yDesign counter so that invalid states eventually transition to a valid state yMay limit exploitation of don't cares implementation on previous slide

18 CS Fall Sequential Logic Implementation - 18 State Machine Model zValues stored in registers represent the state of the circuit zCombinational logic computes: yNext state xFunction of current state and inputs yOutputs xFunction of current state and inputs (Mealy machine) xFunction of current state only (Moore machine) Inputs Outputs Next State Current State output logic next state logic

19 CS Fall Sequential Logic Implementation - 19 State Machine Model (contd) zStates: S1, S2,..., Sk zInputs: I1, I2,..., Im zOutputs: O1, O2,..., On zTransition function: Fs(Si, Ij) zOutput function: Fo(Si) or Fo(Si, Ij) Inputs Outputs Next State Current State output logic next state logic

20 CS Fall Sequential Logic Implementation - 20 Example: Ant Brain (Ward, MIT) zSensors: L and R antennae, 1 if in touching wall zActuators: F - forward step, TL/TR - turn left/right slightly zGoal: find way out of maze zStrategy: keep the wall on the right

21 CS Fall Sequential Logic Implementation - 21 A: Following wall, touching Go forward, turning left slightly B: Following wall, not touching Go forward, turning right slightly C: Break in wall Go forward, turning right slightly D: Hit wall again Back to state A E: Wall in front Turn left until... F:...we are here, same as state B G: Turn left until... LOST: Forward until we touch something Ant Behavior

22 CS Fall Sequential Logic Implementation - 22 Designing an Ant Brain zState Diagram R C (TR, F) RL R B (TR, F) L R L R A (TL, F) R L R L + R E/G (TL) L + R LOST (F) L R

23 CS Fall Sequential Logic Implementation - 23 Synthesizing the Ant Brain Circuit zEncode States Using a Set of State Variables yArbitrary choice - may affect cost, speed zUse Transition Truth Table yDefine next state function for each state variable yDefine output function for each output zImplement next state and output functions using combinational logic y2-level logic (ROM/PLA/PAL) yMulti-level logic yNext state and output functions can be optimized together

24 CS Fall Sequential Logic Implementation - 24 Transition Truth Table zUsing symbolic states and outputs LOST (F) E/G (TL) A (TL, F) B (TR, F) C (TR, F) R R L R R L R L + R L R stateLRnext stateoutputs LOST00LOSTF LOST–1E/GF LOST1– E/GF A00BTL, F A01ATL, F A1– E/GTL, F B– 0CTR, F B– 1ATR, F

25 CS Fall Sequential Logic Implementation - 25 stateLRnext stateoutputs X,Y,ZX', Y', Z'FTRTL LOST- 000 E/G- 001 A- 010 B- 011 C- 100 it now remains to synthesize these 6 functions Synthesis z5 states : at least 3 state variables required (X, Y, Z) yState assignment (in this case, arbitrarily chosen)

26 CS Fall Sequential Logic Implementation - 26 stateinputsnext stateoutputs X,Y,ZL RX +,Y +,Z + FTRTL e.g. TR = X + Y Z X + = X R + Y Z R = R TR Synthesis of Next State and Output Functions

27 CS Fall Sequential Logic Implementation - 27 Circuit Implementation zOutputs are a function of the current state only - Moore machine LRLR F TR TL Next State Current State output logic next state logic X+X+ Y+Y+ Z+Z+ XYZ

28 CS Fall Sequential Logic Implementation - 28 Ant is in deep trouble if it gets in this state Dont Cares in FSM Synthesis zWhat happens to the "unused" states (101, 110, 111)? zExploited as don't cares to minimize the logic yIf states can't happen, then don't care what the functions do yif states do happen, we may be in trouble 000 (F) 001 (TL) 010 (TL, F) 011 (TR, F) 100 (TR, F) R R L R R L R L + R L R

29 CS Fall Sequential Logic Implementation - 29 State Minimization zFewer states may mean fewer state variables zHigh-level synthesis may generate many redundant states zTwo state are equivalent if they are impossible to distinguish from the outputs of the FSM, i. e., for any input sequence the outputs are the same zTwo conditions for two states to be equivalent: y1) Output must be the same in both states y2) Must transition to equivalent states for all input combinations

30 CS Fall Sequential Logic Implementation - 30 Ant Brain Revisited zAny equivalent states? LOST (F) E/G (TL) A (TL, F) B (TR, F) C (TR, F) R R L R R L R L + R L R

31 CS Fall Sequential Logic Implementation - 31 New Improved Brain zMerge equivalent B and C states zBehavior is exactly the same as the 5-state brain zWe now need only 2 state variables rather than 3 LOST (F) E/G (TL) A (TL, F) B/C (TR, F) R L R R L L + R L R

32 CS Fall Sequential Logic Implementation - 32 stateinputs next stateoutputs X,YL RX',Y'FTRTL New Brain Implementation X F Y R L X TR Y R L X TL Y R L X X+ Y R L X Y+ Y R L

33 CS Fall Sequential Logic Implementation - 33 react right away to leaving the wall Mealy vs. Moore Machines zMoore: outputs depend on current state only zMealy: outputs depend on current state and inputs zAnt brain is a Moore Machine yOutput does not react immediately to input change zWe could have specified a Mealy FSM yOutputs have immediate reaction to inputs yAs inputs change, so does next state, doesnt commit until clocking event A L R / TR, F L / TL L R / TL, F

34 CS Fall Sequential Logic Implementation - 34 D/1 E/1 B/0 A/0 C/ reset currentnext resetinputstatestateoutput 1––A 00AB0 01AC0 00BB0 01BD0 00CE0 01CC0 00DE1 01DC1 00EB1 01ED1 Specifying Outputs for a Moore Machine zOutput is only function of state ySpecify in state bubble in state diagram yExample: sequence detector for 01 or 10

35 CS Fall Sequential Logic Implementation - 35 currentnext resetinputstatestateoutput 1––A0 00AB0 01AC0 00BB0 01BC1 00CB1 01CC0 B A C 0/1 0/0 1/1 1/0 reset/0 Specifying Outputs for a Mealy Machine zOutput is function of state and inputs ySpecify output on transition arc between states yExample: sequence detector for 01 or 10

36 CS Fall Sequential Logic Implementation - 36 state feedback inputs outputsreg combinational logic for next state logic for outputs inputsoutputs state feedback reg combinational logic for next state logic for outputs Comparison of Mealy and Moore Machines zMealy Machines tend to have less states yDifferent outputs on arcs (n^2) rather than states (n) zMoore Machines are safer to use yOutputs change at clock edge (always one cycle later) yIn Mealy machines, input change can cause output change as soon as logic is done – a big problem when two machines are interconnected – asynchronous feedback zMealy Machines react faster to inputs yReact in same cycle – don't need to wait for clock yIn Moore machines, more logic may be necessary to decode state into outputs – more gate delays after

37 CS Fall Sequential Logic Implementation - 37 Mealy and Moore Examples zRecognize A,B = 0,1 yMealy or Moore?

38 CS Fall Sequential Logic Implementation - 38 Mealy and Moore Examples (contd) zRecognize A,B = 1,0 then 0,1 yMealy or Moore?

39 CS Fall Sequential Logic Implementation - 39 Registered Mealy Machine (Really Moore) zSynchronous (or registered) Mealy Machine yRegistered state AND outputs yAvoids glitchy outputs yEasy to implement in PLDs zMoore Machine with no output decoding yOutputs computed on transition to next state rather than after entering yView outputs as expanded state vector Inputs Outputs Current State output logic next state logic

40 CS Fall Sequential Logic Implementation - 40 Vending Machine FSM N D Reset Clock Open Coin Sensor Release Mechanism Example: Vending Machine zRelease item after 15 cents are deposited zSingle coin slot for dimes, nickels zNo change

41 CS Fall Sequential Logic Implementation - 41 Example: Vending Machine (contd) zSuitable Abstract Representation yTabulate typical input sequences: x3 nickels xnickel, dime xdime, nickel xtwo dimes yDraw state diagram: xInputs: N, D, reset xOutput: open chute yAssumptions: xAssume N and D asserted for one cycle xEach state has a self loop for N = D = 0 (no coin) S0 Reset S2 D S6 [open] D S4 [open] D S1 N S3 N S7 [open] N S5 [open] N

42 CS Fall Sequential Logic Implementation - 42 Example: Vending Machine (contd) zMinimize number of states - reuse states whenever possible symbolic state table presentinputsnextoutput stateDNstateopen 0¢00 0¢0 01 5¢0 1010¢0 11–– 5¢00 5¢0 0110¢0 1015¢0 11–– 10¢0010¢0 0115¢0 1015¢0 11–– 15¢––15¢1 0¢0¢ Reset 5¢5¢ N N N + D 10¢ D 15¢ [open] D

43 CS Fall Sequential Logic Implementation - 43 present stateinputsnext stateoutput Q1Q0DND1D0open ––– ––– ––– 11–– 111 Example: Vending Machine (contd) zUniquely Encode States

44 CS Fall Sequential Logic Implementation - 44 D1 = Q1 + D + Q0 N D0 = Q0 N + Q0 N + Q1 N + Q1 D OPEN = Q1 Q0 Example: Vending Machine (contd) zMapping to Logic XXXX XXXX1111 Q1 D1 Q0 N D XXXX XXXX0111 Q1 D0 Q0 N D XXXX XXXX0010 Q1 Open Q0 N D

45 CS Fall Sequential Logic Implementation - 45 present stateinputsnext stateoutput Q3Q2Q1Q0DND3D2D1D0open D0 = Q0 D N D1 = Q0 N + Q1 D N D2 = Q0 D + Q1 N + Q2 D N D3 = Q1 D + Q2 D + Q2 N + Q3 OPEN = Q3 Example: Vending Machine (contd) zOne-hot Encoding

46 CS Fall Sequential Logic Implementation - 46 Equivalent Mealy and Moore State Diagrams zMoore machine youtputs associated with state 0¢ [0] 10¢ [0] 5¢ [0] 15¢ [1] N D + Reset D D N N+D N N D Reset N D Reset Mealy machine outputs associated with transitions 0¢0¢ 10¢ 5¢5¢ 15¢ (N D + Reset)/0 D/0 D/1 N/0 N+D/1 N/0 N D/0 Reset/1 N D/0 Reset/0

47 CS Fall Sequential Logic Implementation - 47 Example: Traffic Light Controller zA busy highway is intersected by a little used farmroad zDetectors C sense the presence of cars waiting on the farmroad ywith no car on farmroad, light remain green in highway direction yif vehicle on farmroad, highway lights go from Green to Yellow to Red, allowing the farmroad lights to become green ythese stay green only as long as a farmroad car is detected but never longer than a set interval ywhen these are met, farm lights transition from Green to Yellow to Red, allowing highway to return to green yeven if farmroad vehicles are waiting, highway gets at least a set interval as green zAssume you have an interval timer that generates: ya short time pulse (TS) and ya long time pulse (TL), yin response to a set (ST) signal. yTS is to be used for timing yellow lights and TL for green lights

48 CS Fall Sequential Logic Implementation - 48 highway farm road car sensors Example: Traffic Light Controller (cont) zHighway/farm road intersection

49 CS Fall Sequential Logic Implementation - 49 Example: Traffic Light Controller (cont) zTabulation of Inputs and Outputs inputsdescriptionoutputs description resetplace FSM in initial stateHG, HY, HR assert green/yellow/red highway lights Cdetect vehicle on the farm roadFG, FY, FR assert green/yellow/red highway lights TSshort time interval expiredST start timing a short or long interval TLlong time interval expired zTabulation of unique states – some light configurations imply others statedescription S0highway green (farm road red) S1highway yellow (farm road red) S2farm road green (highway red) S3farm road yellow (highway red)

50 CS Fall Sequential Logic Implementation - 50 S0: HG S1: HY S2: FG S3: FY Example: Traffic Light Controller (cont) zState Diagram Reset TS' TS / ST (TLC)' TLC / ST TS' TS / ST (TL+C')' TL+C' / ST S0 S2 S3S1

51 CS Fall Sequential Logic Implementation - 51 InputsPresent StateNext StateOutputs CTLTSSTHF 0––HGHG0GreenRed –0–HGHG0GreenRed 11–HGHY1GreenRed ––0HYHY0YellowRed ––1HYFG1YellowRed 10–FGFG0RedGreen 0––FGFY1RedGreen –1–FGFY1RedGreen ––0FYFY0RedYellow ––1FYHG1RedYellow SA1:HG = 00HY = 01FG = 11FY = 10 SA2:HG = 00HY = 10FG = 01FY = 11 SA3:HG = 0001HY = 0010FG = 0100FY = 1000(one-hot) output encoding – similar problem to state assignment (Green = 00, Yellow = 01, Red = 10) Example: Traffic Light Controller (cont) zGenerate state table with symbolic states zConsider state assignments

52 CS Fall Sequential Logic Implementation - 52 Logic for Different State Assignments zSA1 NS1 = CTL'PS1PS0 + TSPS1'PS0 + TSPS1PS0' + C'PS1PS0 + TLPS1PS0 NS0 = CTLPS1'PS0' + CTL'PS1PS0 + PS1'PS0 ST = CTLPS1'PS0' + TSPS1'PS0 + TSPS1PS0' + C'PS1PS0 + TLPS1PS0 H1 = PS1H0 = PS1'PS0 F1 = PS1'F0 = PS1PS0' zSA2 NS1 = CTLPS1' + TS'PS1 + C'PS1'PS0 NS0 = TSPS1PS0' + PS1'PS0 + TS'PS1PS0 ST = CTLPS1' + C'PS1'PS0 + TSPS1 H1 = PS0H0 = PS1PS0' F1 = PS0'F0 = PS1PS0 zSA3 NS3 = C'PS2 + TLPS2 + TS'PS3NS2 = TSPS1 + CTL'PS2 NS1 = CTLPS0 + TS'PS1NS0 = C'PS0 + TL'PS0 + TSPS3 ST = CTLPS0 + TSPS1 + C'PS2 + TLPS2 + TSPS3 H1 = PS3 + PS2H0 = PS1 F1 = PS1 + PS0F0 = PS3

53 CS Fall Sequential Logic Implementation - 53 D0= reset'(Q0'N + Q0N' + Q1N + Q1D) D1= reset'(Q1 + D + Q0N) OPEN= Q1Q0 Vending Machine Example (PLD mapping)

54 CS Fall Sequential Logic Implementation - 54 Vending Machine (contd) zOPEN = Q1Q0 creates a combinational delay after Q1 and Q0 change zThis can be corrected by retiming, i.e., move flip-flops and logic through each other to improve delay zOPEN = reset'(Q1 + D + Q0N)(Q0'N + Q0N' + Q1N + Q1D) = reset'(Q1Q0N' + Q1N + Q1D + Q0'ND + Q0N'D) zImplementation now looks like a synchronous Mealy machine yCommon for programmable devices to have FF at end of logic

55 CS Fall Sequential Logic Implementation - 55 OPEN= reset'(Q1Q0N' + Q1N + Q1D + Q0'ND + Q0N'D) Vending Machine (Retimed PLD Mapping)

56 CS Fall Sequential Logic Implementation - 56 Finite State Machine Optimization zState Minimization yFewer states require fewer state bits yFewer bits require fewer logic equations zEncodings: State, Inputs, Outputs yState encoding with fewer bits has fewer equations to implement xHowever, each may be more complex yState encoding with more bits (e.g., one-hot) has simpler equations xComplexity directly related to complexity of state diagram yInput/output encoding may or may not be under designer control

57 CS Fall Sequential Logic Implementation - 57 Algorithmic Approach to State Minimization zGoal – identify and combine states that have equivalent behavior zEquivalent States: ySame output yFor all input combinations, states transition to same or equivalent states zAlgorithm Sketch y1. Place all states in one set y2. Initially partition set based on output behavior y3. Successively partition resulting subsets based on next state transitions y4. Repeat (3) until no further partitioning is required xstates left in the same set are equivalent yPolynomial time procedure

58 CS Fall Sequential Logic Implementation - 58 Input Next State Output SequencePresent StateX=0X=1X=0X=1 ResetS0S1S200 0S1S3S400 1S2S5S600 00S3S0S000 01S4S0S010 10S5S0S000 11S6S0S010 State Minimization Example zSequence Detector for 010 or 110 S0 S3 S2S1 S5S6S4 1/00/0 1/0 0/1 0/01/00/0 1/0 0/0 1/0 0/1 1/0 0/0

59 CS Fall Sequential Logic Implementation - 59 ( S0 S1 S2 S3 S4 S5 S6 ) ( S0 S1 S2 S3 S5 ) ( S4 S6 ) ( S0 S3 S5 ) ( S1 S2 ) ( S4 S6 ) ( S0 ) ( S3 S5 ) ( S1 S2 ) ( S4 S6 ) Input Next State Output SequencePresent StateX=0X=1X=0X=1 ResetS0S1S200 0S1S3S400 1S2S5S600 00S3S0S000 01S4S0S010 10S5S0S000 11S6S0S010 S1 is equivalent to S2 S3 is equivalent to S5 S4 is equivalent to S6 Method of Successive Partitions

60 CS Fall Sequential Logic Implementation - 60 Input Next State Output SequencePresent StateX=0X=1X=0X=1 ResetS0S1'S1' S1'S3'S4'00 X0S3'S0S000 X1S4'S0S010 Minimized FSM zState minimized sequence detector for 010 or 110 S0 S1 S3 S4 X/0 1/0 0/1 0/0 X/0

61 CS Fall Sequential Logic Implementation - 61 symbolic state transition table present next state output state S0S0S1S2S31 S1S0S3S1S40 S2S1S3S2S41 S3S1S0S4S50 S4S0S1S2S51 S5S1S4S0S50 inputs here More Complex State Minimization zMultiple input example S0 [1] S2 [1] S4 [1] S1 [0] S3 [0] S5 [0] 01

62 CS Fall Sequential Logic Implementation - 62 S0-S1 S1-S3 S2-S2 S3-S4 S0-S0 S1-S1 S2-S2 S3-S5 S0-S1 S3-S0 S1-S4 S4-S5 S0-S1 S3-S4 S1-S0 S4-S5 S1-S0 S3-S1 S2-S2 S4-S5 S4-S0 S5-S5 S1-S1 S0-S4 minimized state table (S0==S4) (S3==S5) present next state output state S0'S0'S1S2S3'1 S1S0'S3'S1S3'0 S2S1S3'S2S0'1 S3'S1S0'S0'S3'0 Minimized FSM zImplication Chart Method yCross out incompatible states based on outputs yThen cross out more cells if indexed chart entries are already crossed out S1 S2 S3 S4 S5 S0S1S2S3S4

63 CS Fall Sequential Logic Implementation - 63 Minimizing Incompletely Specified FSMs zEquivalence of states is transitive when machine is fully specified zBut its not transitive when don't cares are present e.g.,stateoutput S0– 0S1 is compatible with both S0 and S2 S11 –but S0 and S2 are incompatible S2– 1 zNo polynomial time algorithm exists for determining best grouping of states into equivalent sets that will yield the smallest number of final states

64 CS Fall Sequential Logic Implementation - 64 XQ1Q0Q1+Q –1000XQ1Q0Q1+Q –1000 Q 1 + = X (Q 1 xor Q 0 ) Q 0 + = X Q 1 Q 0 Minimizing States May Not Yield Best Circuit zExample: edge detector - outputs 1 when last two input changes from 0 to 1 00 [0] 11 [0] 01 [1] X X X X X X

65 CS Fall Sequential Logic Implementation - 65 Another Implementation of Edge Detector z"Ad hoc" solution - not minimal but cheap and fast 00 [0] 10 [0] 01 [1] XX X X X X 11 [0] X X

66 CS Fall Sequential Logic Implementation - 66 State Assignment zChoose bit vectors to assign to each symbolic state yWith n state bits for m states there are 2 n ! / (2 n – m)! [log n <= m <= 2 n ] y2 n codes possible for 1st state, 2 n –1 for 2nd, 2 n –2 for 3rd, … yHuge number even for small values of n and m xIntractable for state machines of any size xHeuristics are necessary for practical solutions yOptimize some metric for the combinational logic xSize (amount of logic and number of FFs) xSpeed (depth of logic and fanout) xDependencies (decomposition)

67 CS Fall Sequential Logic Implementation - 67 State Assignment Strategies zPossible Strategies ySequential – just number states as they appear in the state table yRandom – pick random codes yOne-hot – use as many state bits as there are states (bit=1 –> state) yOutput – use outputs to help encode states yHeuristic – rules of thumb that seem to work in most cases zNo guarantee of optimality – another intractable problem

68 CS Fall Sequential Logic Implementation - 68 One-hot State Assignment zSimple yEasy to encode, debug zSmall Logic Functions yEach state function requires only predecessor state bits as input zGood for Programmable Devices yLots of flip-flops readily available ySimple functions with small support (signals its dependent upon) zImpractical for Large Machines yToo many states require too many flip-flops yDecompose FSMs into smaller pieces that can be one-hot encoded zMany Slight Variations to One-hot yOne-hot + all-0

69 CS Fall Sequential Logic Implementation - 69 IQQ+OiacjibckIQQ+Oiacjibck IQQ+OiabjkaclIQQ+Oiabjkacl IQQ+OiabjicdjIQQ+Oiabjicdj c = i * a + i * b b = i * a c = k * a j = i * a + i * c b = i * a d = i * c i / j i / k a b c a bc i / j k / l bd i / j a c Heuristics for State Assignment zAdjacent codes to states that share a common next state yGroup 1's in next state map zAdjacent codes to states that share a common ancestor state yGroup 1's in next state map zAdjacent codes to states that have a common output behavior yGroup 1's in output map

70 CS Fall Sequential Logic Implementation - 70 General Approach to Heuristic State Assignment zAll current methods are variants of this y1) Determine which states attract each other (weighted pairs) y2) Generate constraints on codes (which should be in same cube) y3) Place codes on Boolean cube so as to maximize constraints satisfied (weighted sum) zDifferent weights make sense depending on whether we are optimizing for two-level or multi-level forms zCan't consider all possible embeddings of state clusters in Boolean cube yHeuristics for ordering embedding yTo prune search for best embedding yExpand cube (more state bits) to satisfy more constraints

71 CS Fall Sequential Logic Implementation - 71 Output-Based Encoding zReuse outputs as state bits - use outputs to help distinguish states yWhy create new functions for state bits when output can serve as well yFits in nicely with synchronous Mealy implementations HG = ST H1 H0 F1 F0 + ST H1 H0 F1 F0 HY = ST H1 H0 F1 F0 + ST H1 H0 F1 F0 FG = ST H1 H0 F1 F0 + ST H1 H0 F1 F0 HY = ST H1 H0 F1 F0 + ST H1 H0 F1 F0 Output patterns are unique to states, we do not need ANY state bits – implement 5 functions (one for each output) instead of 7 (outputs plus 2 state bits) InputsPresent StateNext StateOutputs CTLTSSTHF 0––HGHG00010 –0–HGHG –HGHY10010 ––0HYHY00110 ––1HYFG –FGFG ––FGFY –1–FGFY ––0FYFY ––1FYHG110 01

72 CS Fall Sequential Logic Implementation - 72 Current State Assignment Approaches zFor tight encodings using close to the minimum number of state bits yBest of 10 random seems to be adequate (averages as well as heuristics) yHeuristic approaches are not even close to optimality yUsed in custom chip design zOne-hot encoding yEasy for small state machines yGenerates small equations with easy to estimate complexity yCommon in FPGAs and other programmable logic zOutput-based encoding yAd hoc - no tools yMost common approach taken by human designers yYields very small circuits for most FSMs

73 CS Fall Sequential Logic Implementation - 73 Sequential Logic Implementation Summary zModels for representing sequential circuits yAbstraction of sequential elements yFinite state machines and their state diagrams yInputs/outputs yMealy, Moore, and synchronous Mealy machines zFinite state machine design procedure yDeriving state diagram yDeriving state transition table yDetermining next state and output functions yImplementing combinational logic zImplementation of sequential logic yState minimization yState assignment ySupport in programmable logic devices