Finite State Machines Inputs Combinational

Finite State Machines Finite State Machines (FSMs) are a useful abstraction forsequential circuits with centralized “states” of operation At each clock edge, combinational logic computes outputs andnext state as a function of inputs and present stateFinite State MachinesinputsCombinationalLogic Design methodology for sequential logic-- identify distinct states-- create state transition diagram-- choose state encoding-- write combinational Verilog for next-state logic-- write combinational Verilog for output signals Lots of examplespresentstateoutputs nextstatennQRegistersDCLK6.111 Fall 2017Lecture 616.111 Fall 2017Two Types of FSMs A level-to-pulse converter produces a singlecycle pulse each time its input goes high. Moore FSM: It’s a synchronous rising-edge detector.nextstateinputsx0.xnComb.Logicn2Design Example: Level-to-PulseMoore and Mealy FSMs : different output generationS Lecture 6QDComb.LogicRegistersCLK Sample uses:outputsyk fk(S)– Buttons and switches pressed by humans forarbitrary periods of timen– Single-cycle enable signals for counterspresent state S Mealy FSM:direct combinational path!inputsx0.xnComb.LogicS nDComb.LogicQRegistersCLKoutputsyk fk(S, x0.xn)LWhenever input L goesfrom low to high.nLevel toPPulseConverterCLK.output P produces asingle pulse, one clockperiod wide.S6.111 Fall 2017Lecture 636.111 Fall 2017Lecture 64

Valid State Transition DiagramsStep 1: State Transition Diagram Block diagram of desired system:Synchronizerunsynchronizeduser inputD QL 1Edge DetectorD QLLevel toPulseFSM00L 0PCLK“if L 1 at the clock edge,then jump to state 01.”L 0L 1L 10001Low input,Waiting for riseP 0Edge Detected!L 0P 1“if L 0 at the clockedge, then stay in state00.”6.111 Fall 2017L 1This is the output that resultsfrom this state. (Moore orMealy?)L 0 Often a starting state is specified Each state specifies values for all outputs (Moore)56.111 Fall 2017Lecture 6Choosing State Representation6Step 2: Logic DerivationTransition diagram is readily converted to astate transition table (just a truth table)Choice #1: binary encodingL 1L 1For N states, use ceil(log2N) bits to encode the state with eachstate represented by a unique combination of the bits.Tradeoffs: most efficient use of state registers, but requiresmore complicated combinational logic to detect when in aparticular state.L 000P 0Edge Detected!L 0L 11101Low input,Waiting for riseP 1High input,Waiting for fallP 0L 0NextStateCurrentStateInS1 S0LS1000011010101000101001111 S0Out 010101P001100 Combinational logic may be derived using Karnaugh mapsChoice #2: “one-hot” encodingS1S0 for S1 :L00 01 11 10 For N states, use N bits to encode the state where the bitcorresponding to the current state is 1, all the others 0.Tradeoffs: more state registers, but often much lesscombinational logic since state decoding is trivial.6.111 Fall 2017L 0L 1P 0 So for each state: for any combination of input values there’sexactly one applicable arcP 0Lecture 6P 1 Arcs leaving a state are collectively exhaustive, i.e., for anycombination of input values there’s at least one applicable arc1111L 0High input,Waiting for fallEdge Detected! Arcs leaving a state are mutually exclusive, i.e., for anycombination input values there’s at most one applicable arcBinary values of statesHigh input,Waiting for fall1101Low input,Waiting for riseP 0 State transition diagram is a useful FSM representation anddesign aid:L 1Lecture 60 0 0 0 X1 0 1 1 Xfor S0 :S1S000 01 11 10L0 0 0 0 X1 1 1 1 X76.111 Fall 2017LComb.LogicS1 LS0S0 LS nDQComb.LogicRegistersCLKnSLecture 6P S1S0PS0S1for P:0 10 0 X1 1 08

Design of a Mealy Level-to-PulseMoore Level-to-Pulse Converternextstatedirect combinational path!S inputsComb.Logicx0.xnQDoutputsyk fk(S)Comb.LogicRegistersnCLKComb.LogicnS Since outputs are determined by state and inputs, Mealy FSMs mayneed fewer states than Moore FSM implementationsP S1S01. When L 1 and S 0, this output isasserted immediately and until thestate transition occurs (or Lchanges).Moore FSM circuit implementation of level-to-pulse converter:S0 LCLKDS0PQCLKDS1 QQQComb.LogicQDRegistersnpresent state SS1 LS0S0 LS nL 0 P 00LPL 1 P 1Input is low2Clock1StateInput is highL 0 P 0S11L 1 P 0Output transitions immediately.State transitions at the clockedge.2. While in state S 1 and as long as L remainsat 1, this output is asserted until next clock.6.111 Fall 2017Lecture 696.111 Fall 2017Lecture 6Mealy Level-to-Pulse Converter0L 1 P 1Input is low1Input is highL 0 P 0L 0 P 0L 1 P 0Moore/Mealy Trade-OffsInNextStateOutSLS P0000011111101000Pres.State How are they different?– Moore: outputs f( state ) only– Mealy outputs f( state and input )– Mealy outputs generally occur one cycle earlier than a Moore:Moore: delayed assertion of PMealy FSM circuit implementation of level-to-pulse converter:LS CLKDQQSPSLecture 6Mealy: immediate assertion of PLLPPClockClockState[State0] FSM’s state simply remembers the previous value of L Circuit benefits from the Mealy FSM’s implicit single-cycleassertion of outputs during state transitions6.111 Fall 201710 Compared to a Moore FSM, a Mealy FSM might.– Be more difficult to conceptualize and design– Have fewer states116.111 Fall 2017Lecture 612

Example: Intersection Traffic LightsFSM ExampleGOAL:Build an electronic combination lock with a resetbutton, two number buttons (0 and 1), and an unlockoutput. The combination should be 01011. Design a controller for the traffic lights at the intersection oftwo streets – two sets of traffic lights, one for each of thestreets. Step 1: Draw starting state transition diagram. Just handle theusual green-yellow-red cycle for both streets. How many states?Well, how many different combinations of the two sets of lightsare needed? Step 2: add support for a walk button and walk lights to yourstate transition diagram. Step 3: add support for a traffic sensor for each of the streets– when the sensor detects traffic the green cycle for that streetis extended.RESET“0”“1”STEPS:1. Design lock FSM (block diagram, state transitions)2. Write Verilog module(s) for FSMExample to be worked collaboratively on the board 6.111 Fall 2017Lecture 6136.111 Fall 2017Step 1A: Block Diagramfsm clockreset buttonButton0b0 in buttonButton1b1 inunlockreset0RESETUnlock 0UnlockLED101“0”Unlock 01“01”Unlock 001b0statebutton14RESETfsmButtonEnterLecture 6Step 1B: State transition 1”Unlock 11“0101”Unlock 01“010”Unlock 0b106 states 3 bits6.111 Fall 2017Lecture 6156.111 Fall 2017Lecture 616

Step 2: Write VerilogStep 2A: Synchronize buttons////////module lock(input clk,reset in,b0 in,b1 in,output out);// synchronize push buttons, convert to pulsesbuttonpush button synchronizer and level-to-pulse converterOUT goes high for one cycle of CLK whenever IN makes alow-to-high transition.outmodule button(input clk,in,output out);reg r1,r2,r3;always @(posedgebeginr1 in;//r2 r1;//r3 r2;//end// implement state transition diagramreg [2:0] state,next state;always @(*) begin// combinational logic!next state ?;endalways @(posedge clk) state next state;// generate outputassign out ?;// debugging?endmodule6.111 Fall 2017D Qr1D Qr2D Qr3clkclk)synchronizerstatefirst reg in synchronizersecond reg in synchronizer, output is in sync!remembers previous state of button// rising edge old value is 0, new value is 1assign out r3 & r2;endmoduleLecture 6176.111 Fall 2017Step 2B: state transition erparameterinS RESET 0; // state assignmentsS 0 1;RESETS 01 2;1S 010 3;RESETUnlock 0S 0101 4;S 01011 5;1“0”Unlock 0// it’s a Moore machine!1118Step 2C: generate output00Lecture 6“01”Unlock 0Output only depends on current stateassign out (state S 01011);00011reg [2:0] state, next state;“01011 ”“0101 ”“010”Unlock 1Unlock 0Unlock 0always @(*) begin0// implement state transition diagramif (reset) next state S RESET;else case (state)S RESET: next state b0 ? S 0: b1 ? S RESET : state;S 0:next state b0 ? S 0: b1 ? S 01: state;S 01:next state b0 ? S 010 : b1 ? S RESET : state;S 010:next state b0 ? S 0: b1 ? S 0101 : state;S 0101: next state b0 ? S 010 : b1 ? S 01011 : state;S 01011: next state b0 ? S 0: b1 ? S RESET : state;default: next state S RESET; // handle unused statesendcaseendStep 2D: debugging?// hmmm. What would be useful to know? Current state?// hex display on labkit shows 16 four bit valuesassign hex display {60’b0, 1'b0, state[2:0]};always @(posedge clk) state next state;6.111 Fall 2017Lecture 6196.111 Fall 2017Lecture 620

Step 2: final Verilog implementationReal FSM Security Systemmodule lock(input clk,reset in,b0 in,b1 in,output out, output [3:0] hex display);wire reset, b0, b1; // synchronize push buttons, convert to pulsesbutton b reset(clk,reset in,reset);button b 0(clk,b0 in,b0);button b 1(clk,b1 in,b1);parameter S RESET 0; parameter S 0 1; // state assignmentsparameter S 01 2; parameter S 010 3;parameter S 0101 4; parameter S 01011 5;reg [2:0] state,next state;always @(*) begin// implement state transition diagramif (reset) next state S RESET;else case (state)S RESET: next state b0 ? S 0: b1 ? S RESET : state;S 0:next state b0 ? S 0: b1 ? S 01: state;S 01:next state b0 ? S 010 : b1 ? S RESET : state;S 010:next state b0 ? S 0: b1 ? S 0101 : state;S 0101: next state b0 ? S 010 : b1 ? S 01011 : state;S 01011: next state b0 ? S 0: b1 ? S RESET : state;default: next state S RESET;// handle unused statesendcaseendalways @ (posedge clk) state next state;assign out (state S 01011);// assign output: Moore machineassign hex display {1'b0,state};// debuggingendmodule6.111 Fall 2017Lecture 6216.111 Fall 2017What States are in the System?The 6.111 Vending Machine Lab assistants demand a new sodamachine for the 6.111 lab. Youdesign the FSM controller. All selections are 0.30. The machine makes change.(Dimes and nickels only.) Inputs: limit 1 per clock– Q - quarter inserted– D - dime inserted– N - nickel inserted A starting (idle) state:idle30 A state for each possible amount of money captured:30 got5cCOINS ONLY25 10 5 .JoltWatergot35cgot40cgot45cgot50c States to dispense change (one per coin dispensed):LS163got45cLecture 6.25 cents (just shy of a purchase) one quarter (largest coin)– DC - dispense can– DD - dispense dime– DN - dispense nickel6.111 Fall 2017got15cgot10c What’s the maximum amount of money captured before purchase?CoSprite Outputs: limit 1 per clock22Lecture 6236.111 Fall 2017DispenseDimeDispenseNickelLecture 624