Elevator ControllerFinite State MachinesA Finite State MachineGumball MachineSlide 5A More Efficient SolutionGumball Machine State TableGumball Machine ImplementationInputsAsynchronous vs. Synchronous InputsParity CheckerSlide 12Pattern MatcherSlide 14Pattern Matcher - ImplementationSlide 16Seattle Pacific University EE 1210 - Logic System Design FSM-1Elevator Controller•We’re hired to design a digital elevator controller for a four-floor building00011011•1st try: Design a counter that counts up and down•00, 01, 10, 11, 10, 01, 00, ...•Problem: Never stops!•2nd try: Add “Stop” button that disables counter•Problem: Have to press button when elevator happens by•We need a way to have user inputs into a complex systemSeattle Pacific University EE 1210 - Logic System Design FSM-2Finite 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-3A Finite State MachineCombinationalLogicFor Next StateComb.LogicFor OutputsOutputsStateFlipFlopsClockClockCurrentStateNextStateInputsElevator ButtonsMotor/Door ControlsCurrent floor/directionNext floor/ directionExample shown for elevator controllerSeattle Pacific University EE 1210 - Logic System Design FSM-4Gumball 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 enteredGumballMachine FSMNDResetClkOpenCoin SensorCandyRelease MechanismSeattle Pacific University EE 1210 - Logic System Design FSM-5Gumball MachineTabulate typical input sequences:three nickelsnickel, dimetwo nickels, dimetwo dimes dime, nickelDraw state diagram:Inputs: N, D, resetOutput: openDiagram what is going on in a state diagramS0S1 S2S3[open=1]S4[open=1]S5[open=1]S6[open=1]S8[open=1]S7DDDDNNNNResetOutput (open) indicatedduring states in which isis assertedNote: No change provided!N’D’S0NS1DS2N’D’S0NS1DS2N’D’S0NS1DS2N’D’S0NS1DS2N’D’S0NS1DS2N’D’N’D’N’D’N’D’Seattle Pacific University EE 1210 - Logic System Design FSM-6A More Efficient SolutionReuse states whenever possibleSymbolic State Table0¢5¢10¢DDNNN+DReset15+¢[open=1]15+¢15+¢0¢5¢10¢X15+¢10¢10¢5¢XX5¢X0¢10¢QCurrent StateOpenOutput0¢ 05¢ 010¢ 015+¢ 10010¢1010¢0110¢115¢1110¢0015+¢1015+¢0115+¢1115+¢015¢105¢005¢110¢010¢100¢000¢Q+Next StateNInputDInputQCurrent StateOutput TableN’D’N’D’N’D’N’D’DNSeattle Pacific University EE 1210 - Logic System Design FSM-7Gumball Machine State TableEncode states into binary numbersCalculate total number of states: 4 (0¢, 5¢, 10¢, 15¢)Use as many bits as needed for the states 4 states --> 2 bitsEncoding: 0¢: 005¢: 0110¢: 1015+¢: 11Calculate total number of states: 4 (0¢, 5¢, 10¢, 15¢)Use as many bits as needed for the states 4 states --> 2 bitsEncoding: 0¢: 005¢: 0110¢: 1015+¢: 11Encoded State TableX100X111X110X100011XX010X101X01011111111000000000001011111110000Q1Q0Current State00100111110010011101100011011000Q1+Q0+Next StateNInputDInputQ1Q0Current StateOpenOutput0000 1 01001 1 1Output TableSeattle Pacific University EE 1210 - Logic System Design FSM-8Gumball Machine ImplementationQ1Q0DN00 01 11 10 00 01 11 10 Q1 Q0D ND11 0x1 x 00 1 1 x 1 0 1 0 x 1 Q1Q0DN00 01 11 10 00 01 11 10 Q1 Q0D ND01 1x0 x 00 1 0 x 1 1 0 1 x 0 D1= D + NQ0Q1’ + Q0’Q1D2= NQ0’ + N’Q1’Q0 + NQ1 + DQ1Q0’Open = Q1Q0Note that the output is a function of only the stateIf we chose D FF’s, we don’t have to convert Q’s to FF inputsQ1Q0Current StateOpenOutput0000 1 01001 1 1Seattle Pacific University EE 1210 - Logic System Design FSM-9Inputs•FSMs change state based on clock edges•I.e. Rising clock edge clocks all FFsThis part can change only when clock “ticks”CombinationalLogicFor Next StateComb.LogicFor OutputsStateFlipFlopsClockClockInputsThis part can change at any timeSynchronous Inputs: Change in synch with the clock. Obey setup and hold time.Asynchronous Inputs: Change at any time. May violate setup and hold times.Seattle Pacific University EE 1210 - Logic System Design FSM-10Asynchronous vs. Synchronous Inputs•Asynchronous•Synchronous•Example: Elevator pushbuttons•Arrive at any time•Usually asserted for many clock cycles•FSM logic must not make any assumptions about input timing•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Seattle Pacific University EE 1210 - Logic System Design FSM-11Parity CheckerAssert output (parity) whenever input bit stream (synchronous) has odd # of 1'sQPresent StateInInputQ+Next StateEven 0 0 Even 0Even 0 1 Odd 1Odd 1 0 Odd 1Odd 1 1 Even 00 1 1 110 00 0 0 00 0 1 1 1 01 1 1 1 0ClkInputOutputState DiagramEven [0]Odd [1]ResetInInIn’In’QPresent StateParityOutputEven 0 0Odd 1 1Q+ = Q  InParity = QSeattle Pacific University EE 1210 - Logic System Design FSM-12Parity Checker•Parity Checking is a type of Synchronous Serial Input FSM•A single input•Input is synchronized with clock (1 bit per clock cycle)•Goal is to look for patterns in the input bit streamD FF ImplementationT FF ImplementationD QClrParityInResetT QPreClrParityInResetQ+ = Q  In Parity = QSeattle Pacific University EE 1210 - Logic System Design FSM-13Pattern MatcherA string recognizer has one synchronous input (X) and one output (Z).The output is asserted whenever the input sequence …010…has been observed, as long as the sequence …100… has never been seen.Sample input/output behavior:00010000000Z:01001011011X:00010101000Z:01001010100X:This is a synchronous serial input problem1. Work though sample inputs to understand problem2. Develop FSM to recognize patterns3. Implement using standard techniquesSeattle Pacific University EE 1210 - Logic System Design FSM-14Pattern Matcher1. Pick a reset state.2. Draw paths for strings