Elevator Controller We re hired to design a digital elevator controller for a four floor building 1st try Design a counter that counts up and down 00 01 10 11 10 01 00 Problem Never stops 11 10 2nd try Add Stop button that disables counter Problem Have to press button when elevator happens by We need a way to have user 01 00 inputs into a complex system Seattle Pacific University EE 1210 Logic System Design FSM 1 Finite State Machines Counters Next state based on current state If counter is in state 101 next state is 110 No inputs other than reset enable Finite State Machines Next state is a function of the current state and the inputs If the elevator is on floor 00 and the UP button is pressed on floor 10 then move to floor 01 If current state is 00 If UP2 Next state is 01 Seattle Pacific University EE 1210 Logic System Design FSM 2 A Finite State Machine Next State Next floor direction Current State State FlipFlops Combinational Logic For Next State Current floor direction Comb Logic For Outputs Outputs Motor Door Controls Clock Clock Example shown for elevator controller Inputs Seattle Pacific University Elevator Buttons EE 1210 Logic System Design FSM 3 Gumball Machine We re building a gumball machine 15 cents for a gumball Machine has a single slot which can take dimes or nickels Subcontractor provides a coin sensor which has two outputs N is true if a nickel was input D is true if a dime was input We must provide the output Open when 15 cents entered Coin Sensor N D Reset Gumball Machine FSM Open Candy Release Mechanism Clk Seattle Pacific University EE 1210 Logic System Design FSM 4 Gumball Machine Reset N D Diagram what is going on in a state diagram S0 Tabulate typical input sequences three nickels nickel dime two nickels dime two dimes N D dime nickel N S2 D N S1 S0 D S2 open 1 N N D S1 S0 D open 1 N N D S2 S1 S0 D S2 open 1 open 1 S1 S6 S5 S8 S7 N N D S0 D N S4 N D N D Note No N D change provided D S1 open 1 Output open Seattle Pacific University N D S3 Draw state diagram Inputs N D reset N D N N D S2 S1 S0 D S2 EE 1210 Logic System Design Output open indicated during states in which is is asserted FSM 5 A More Efficient Solution Reset 0 N D N D N D 5 D N 10 N D N D 15 D open 1 N N D Reuse states whenever possible Symbolic State Table Seattle Pacific University Q D N Q Current State Input Input Next State 0 0 0 0 5 5 5 5 10 10 10 10 15 15 15 15 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 10 X 5 10 15 X 10 15 15 X 0 5 10 X EE 1210 Logic System Design Q Open Current State Output 0 0 5 0 10 0 15 1 Output Table FSM 6 Gumball Machine State Table Encode states into binary numbers Calculate Calculate total total number number of of states states 44 0 0 55 10 10 15 15 Use Use as as many many bits bits as as needed needed for for the states the states 44 states states 22 bits bits Encoding Encoding 00 55 10 10 15 15 00 00 01 01 10 10 11 11 Encoded State Table Seattle Pacific University Q1 Q0 D N Q1 Q0 Current State Input Input Next State 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 X 0 1 1 X 1 1 1 X 0 0 1 X 0 1 0 X 1 0 1 X 0 1 1 X 0 1 0 X EE 1210 Logic System Design Q1Q0 Current State Open Output 0 0 0 0 1 0 1 0 0 1 1 1 Output Table FSM 7 Gumball Machine Implementation D1 DN 00 Q1Q0 Q1 D 01 11 00 0 0 x 01 0 1 11 0 10 1 D0 DN 00 10 Q1Q0 D 01 11 10 1 00 0 1 x 0 x 1 01 1 0 x 1 0 x 1 11 0 1 x 0 1 x 1 10 0 1 x 1 N Q1Q0 Current State Q0 Q1 Q0 If we chose D FF s we don t have to convert Q s to FF inputs N Open Output 0 0 0 0 1 0 1 0 0 1 1 1 Seattle Pacific University D1 D NQ0Q1 Q0 Q1 D2 NQ0 N Q1 Q0 NQ1 DQ1Q0 Open Q1Q0 Note that the output is a function of only the state EE 1210 Logic System Design FSM 8 Inputs FSMs change state based on clock edges I e Rising clock edge clocks all FFs State FlipFlops Combinational Logic For Next State Comb Logic For Outputs Clock Clock This part can change at any time Inputs Seattle Pacific University This part can change only when clock ticks Synchronous Inputs Change in synch with the clock Obey setup and hold time Asynchronous Inputs Change at any time May violate setup and hold times EE 1210 Logic System Design FSM 9 Asynchronous vs Synchronous Inputs Asynchronous Example Elevator pushbuttons Arrive at any time Usually asserted for many clock cycles FSM logic must not make any assumptions about input timing Seattle Pacific University Synchronous Example Data arriving on a serial line from a computer Arrive synchronized exactly to a clock One bit of data per clock cycle FSM can assume that data changes once per clock cycle EE 1210 Logic System Design FSM 10 Parity Checker Assert output parity whenever input bit stream synchronous has odd of 1 s Clk Input 0 Output 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 1 0 Reset State Diagram In Even 0 In In Odd 1 In Seattle Pacific University Q In Q Present State Input Next State Q Parity Present State Output Even 0 0 Even 0 Even 0 1 Odd 1 Even 0 0 Odd 1 0 Odd 1 Odd 1 1 Odd 1 1 Even 0 Parity Q Q Q In EE 1210 Logic System Design FSM 11 Parity Checker Q Q In In D Q Parity Parity Q In Pre T Q Clr Reset Clr Reset D FF Implementation Parity T FF Implementation Parity Checking is a type of Synchronous Serial Input FSM A single input Input is synchronized with clock 1 bit …