6.004-6 Storage elements, finite state machines

MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L06 – FSMs 1 6.004 – Spring 20092/24/09(Synchronous)Finite State Machines Lab 2 is due Thursday Great -Theory! Finally! Some ENGINEERING!modified 2/23/09 09:27 L06 – FSMs 2 6.004 – Spring 20092/24/09Our New Machine Combinational Logic Current State NewState InputOutput Clock State Registers kkmn•Acyclic graph •Obeys static discipline •Can be exhaustively enumerated by a truth table of 2k+mrows and k+n output columns •Engineered cycles •Works only if dynamic discipline obeyed •Remembers k bits for a total of 2k unique combinations L06 – FSMs 3 6.004 – Spring 20092/24/09Must Respect Timing Assumptions! Questions: •Constraints on TCD for the logic? •Minimum clock period? •Setup, Hold times for Inputs? Combinational Logic Current State NewState InputOutput Clock tCD,L = ? tPD,L = 5ns tCD,R = 1ns tPD,R = 3ns tS,R = 2ns tH,R = 2ns tCD,L > 1 ns tS = tPD,L + tS,R = 7 nS tH = tH,R-tCD,L= 1 nS We know how fast it goes… But what can it do? tCD,R (1 ns) + tCD,L(?) > tH,R(2 ns) tCLK > tPD,R+tPD,L+ tS,R > 10nS L06 – FSMs 4 6.004 – Spring 20092/24/09A simple sequential circuit… Lets make a digital binary Combination Lock: Specification: •One input ( “0” or “1”) •One output (“Unlock” signal) •UNLOCK is 1 if and only if: Last 4 inputs were the “combination”: 0110 How many registers do I need? Lock INUCLKL06 – FSMs 5 6.004 – Spring 20092/24/09Abstractiondu jour: Finite State Machines •A FINITE STATE MACHINE has ClockedFSMmn•k STATES: S1 … Sk (one is “initial” state) •m INPUTS: I1 … Im•n OUTPUTS: O1 … On•Transition Rules s’(s, I) for each state s and input I •Output Rules Out(s) for each state s L06 – FSMs 6 6.004 – Spring 20092/24/09State Transition Diagram SXU=0S0U=00S01U=01S011U=01S0110U=10100011XXXU=0NAMEof state OUTPUT when in this state 0INPUTcausing transition Heavy circle MeansINITIAL state Designing our lock … •Need an initial state; call it SX. •Must have a separate state for each step of the proper entry sequence •Must handle other (erroneous) entries Why do these go to S0 and S01? L06 – FSMs 7 6.004 – Spring 20092/24/09Yet Another SpecificationSXU=0S0U=00S01U=01S011U=01S0110U=10100011IN Current State Next State Unlock 0SXS0 0 1SXSX 0 0S0S0 0 1S0S01 0 0S01S0 0 1S01S011 0 0S011S0110 0 1S011SX 0 0S0110S0 1 1S0110S01 1 All state transition diagrams can be described by truth tables…Binary encodings are assigned to each state (a bit of an art) The truth table can then be simplified using the reduction techniques we learned for combinational logic 00000000 1 00 1 0 1 1 0 1 1 0 10 0 10 100 100 00 1 00000 1 0 1 1 00 1 0 10 1 00 00000 1 0 1 1 The assignment of codes to states can be arbitrary, however, if you choose them carefully you can greatly reduce your logic requirements. L06 – FSMs 8 6.004 – Spring 20092/24/09Valid State Diagrams •Arcs leaving a state must be: •(1) mutually exclusive–can’t have two choices for a given input value •(2) collectively exhaustive –every state must specify what happens for each possible input combination. “Nothing happens” means arc back to itself. S1S300S2111010MOORE Machine: Outputs on States S1S30/00/1S21/01/11/0MEALY Machine: Outputs on Transitions 00/0L06 – FSMs 9 6.004 – Spring 20092/24/09Now put it in Hardware! ROM16x4unlock Next state Current state INTrigger update periodically (“clock”) 334 inputs 24 locations each location supplies 4 bits We assume inputsare synchronized with clock… L06 – FSMs 10 6.004 – Spring 20092/24/09Discrete State, Time ClockSTATENEXTClock Period 1Clock Period 2Clock Period 3Clock Period 4Clock Period 5ROMNEXTSTATE inputsoutputssss state bits2s possible states Two design choices: (1) outputs only depend on state (2) outputs depend on inputs + state (Moore) (Mealy) L06 – FSMs 11 6.004 – Spring 20092/24/091110Asynchronous Inputs -I Our example assumed a single clock transition per input. What if the “button pusher” is unaware of, or not synchronized with, the clock? SXU=0S0U=0S01U=0S011U=0U=0B0B0U=0B1B1U=0B1B1U=0B1B1What if each button input is an asynchronous 0/1 level? How do we prevent a single buttonpress, e.g., from making several transitions? Lock B1UB00101Useintervening states to synchronize button presses! But what About the DynamicDiscipline? L06 – FSMs 12 6.004 – Spring 20092/24/09FSM Party Games ROMkk1. What can you say about the number of states? 2. Same question: mStatesnStatesxyz3. Here's an FSM. Can you discover its rules? A finite state machine with two states, 0 and 1.Figure by MIT OpenCourseWare.L06 – FSMs 13 6.004 – Spring 20092/24/09What’s My Transition Diagram? 10101011010100vs.0="1The same finite state machine, with a person jumping from 0 to 1.OFF,1=ON?111" =Surprise!•If you know NOTHING about the FSM, you’re never sure! •If you have a BOUND on the number of states, you can discover its behavior: K-state FSM: Every (reachable) state can be reached in < k steps.BUT ... states may be equivalent!1L06 – FSMs 14 6.004 – Spring 20092/24/09FSM Equivalence 10101011010100vs.ARE THEY DIFFERENT? NOT in any practical sense! They are EXTERNALLY INDISTINGUISHABLE, hence interchangeable. FSMsEQUIVALENT iff every input sequence yields identical output sequences. ENGINEERING GOAL: • HAVE an FSM which works... • WANT simplest (ergo cheapest) equivalent FSM. L06 – FSMs 15 6.004 – Spring 20092/24/09Lets build an Ant•SENSORS: antennae L and R, each 1 if in contact with something. •ACTUATORS: Forward Step F, ten-degree turns TL and TR (left, right). 8 legs?GOAL: Make our ant smart enough to get out of a maze like:STRATEGY: "Right antenna to the wall" L06 – FSMs 16 6.004 – Spring 20092/24/09Lost in space ?LOST FL+R_ _ L R “lost” is the initial stateAction: Go forward until we hit something. The Figure by MIT OpenCourseWare.L06 – FSMs 17 6.004 – Spring 20092/24/09Bonk!LOST FL+R_ _ L R RCCW L+RTL_ _ L R Action: Turn left (CCW) until we don’t touch anymore L06 – FSMs 18 6.004 – Spring 20092/24/09A little to the right… LOST FRCCW L+RL+RWall1 TR,FR_RTL_ _ L R _ _ L R Action: Step and turn right a little, look for wall L06 – FSMs 19 6.004 – Spring 20092/24/09Then a little to the left LOST FWall1 TR,FRCCW RL+RL+R_RTL_ _ L R _ _ L R _ _ L R Wall2 TL,FL_L R Action: Step and turn left a little, till not touching (again) L06 – FSMs 20 6.004 – Spring 20092/24/09Dealing with corners LOST FWall2 TL,FWall1 TR,FRCCW RL+RL+R_RLTL_ _ L R _ _ L R _ _ L R _L R TR,FCorner R_RAction: Step and turn right until we hit perpendicular wall L06 – FSMs 21 6.004 – Spring 20092/24/09Equivalent State Reduction Observation: SiSjif 1. States have identical outputs; AND 2. Every input equivalent states. Reduction Strategy: Find pairs of equivalent states, MERGE them.LOST FWall2 TL,FWall1 TR,FRCCW RL+RL+R_RLTL_ _ L R _ _ L R _ _ L R _L R TR,FCorner R_RL06 – FSMs 22 6.004 – Spring 20092/24/09An Evolutionary Step Behaves exactly as previous (5-state) FSM, but requires half the ROM in its implementation! Mergeequivalent states Wall1 and Corner into a single new, combined state. LOST FWall2 TL,FWall1 TR,FRCCW RL+RL+R_RLTL_ _ L R _ _ L R _ _ L R _L R L06 – FSMs 23 6.004 – Spring 20092/24/0900 1 -01 0 0 1 00 0 1 01 0 0 1 L+RRCCW L+R01 1 -| 01 0 1 0 01 0 1 | 01 0 1 0 TLBuilding the Transition Table S L R | S’ TR TL F -------+-----------00 0 0 | 00 0 0 1 | | | | | | | | LOST F_ _ L R L06 – FSMs 24 6.004 – Spring 20092/24/09Implementation Details S L R | S’ TR TL F -------+-----------00 0 0 | 00 0 0 1 00 1 -| 01 0 0 1 00 0 1 | 01 0 0 1 01 1 -| 01 0 1 0 01 0 1 | 01 0 1 0 01 0 0 | 10 0 1 0 10 – 0 | 10 1 0 1 10 – 1 | 11 1 0 1 11 1 -| 01 0 1 1 11 0 0 | 10 0 1 1 11 0 1 | 11 0 1 1 LOST RCCW WALL1 WALL2 S1’ S1S000 01 11 10 00 0 1 1 1 LR01 0 0 1 1 11 0 0 0 1 10 0 0 0 1 S0’ S1S000 01 11 10 00 0 0 0 0 LR01 1 1 1 1 11 1 1 1 1 10 1 1 1 0 01011SRLSLSSS++=Complete Transition table 010LSSLRS++=L06 – FSMs 25 6.004 – Spring 20092/24/09Ant Schematic L06 – FSMs 26 6.004 – Spring 20092/24/09Roboant® Mazeselection FSM state table StatusdisplayPlan view of mazeSimulation controls Featuring the new Mark-II ant: can add (M), erase (E), and sense (S) marks along its path. L06 – FSMs 27 6.004 – Spring 20092/24/09Housekeeping issues… ROMorgates NEXTSTATE inputsoutputsss1. Initialization? Clear the memory? 2. Unused state encodings? -waste ROM (use PLA or gates) -what does it mean? -can the FSM recover? 3. Choosing encoding for state? 4. Synchronizing input changes with state update? INCLKUNow, that’s a funny looking state machine L06 – FSMs 28 6.004 – Spring 20092/24/09Twisting you Further… •MORE THAN ANTS: Swarming, flocking, and schooling can result from collections of very simple FSMs • PERHAPS MOST PHYSICS: Cellular automata, arrays of simple FSMs, can more accurately model fluilds than numerical solutions to PDEs • WHAT IF: We replaced the ROM with a RAM and have outputs that modify the RAM? ... You'll see FSMs for the rest of your life! I prefer to think we ascended…Did we all descend from FSMs???