EECS150Section 4Finite State MachinesFall 2001EECS150 - Fall 2001 1-2Abstraction of State ElementsDivide circuit into combinational logic and stateLocalize feedback loops and make it easy to break cyclesImplementation of storage elements leads to various forms of sequential logicCombinationalLogicStorage ElementsOutputsState OutputsState InputsInputsEECS150 - Fall 2001 1-3In = 0In = 1In = 0In = 1100010110111001Finite State Machine RepresentationStates: determined by possible values in sequential storage elementsTransitions: change of stateClock: controls when state can change by controlling storage elementsSequential LogicSequences through a series of statesBased on sequence of values on input signalsClock period defines elements of sequenceEECS150 - Fall 2001 1-4Pieces of FSMsDQNex tstateDecoder/ //new value forpresentinputscomb. logicst atenext stateNSDDecoder/ //outp utsP.S .inpu tscomb. logicODOutput/ /State registernext state to loadon rising edgeclockpresentstateEECS150 - Fall 2001 1-5Types of FSM’sMoore and Mealey FSMclockQDNSDinpu ts/OD /Mo oreclockQDNSDinputsOD/Mealey/PSNSoutputsoutp ut sfun ction only ofpresent stateEECS150 - Fall 2001 1-6Example Finite State MachineCombination lock from first lectureresetS3closedclosedmux=C1equal& newnot equal& newnot equal& newnot equal& newnot newnot newnot newS1 S2 OPENERRclosedmux=C2equal& newclosedmux=C3equal& newopenEECS150 - Fall 2001 1-7Shift Registers as FSM’sShift RegisterInput value shownon transition arcsOutput values shownwithin state node1001101110111010100000010111111100000100DQ DQ DQINOUT1 OUT2 OUT3CLKEECS150 - Fall 2001 1-80101001100110010001011113-bit up-counterCounters as FSM’sCountersProceed thru well-defined state sequence in response to enableMany types of counters: binary, BCD, Gray-code3-bit up-counter: 000, 001, 010, 011, 100, 101, 110, 111, 000, ...3-bit down-counter: 111, 110, 101, 100, 011, 010, 001, 000, 111, ...EECS150 - Fall 2001 1-9Turn a State Diagram into LogicCounterThree flip-flops to hold stateLogic to compute next stateClock signal controls when flip-flop memory can changeWait long enough for combinational logic to compute new valueDon't wait too long as that is low performanceDQ DQ DQOUT1 OUT2 OUT3CLK"1"EECS150 - Fall 2001 1-100101001100110010001011113-bit up-countercurrent state next state0 000 001 11 001 010 22 010 011 33 011 100 44 100 101 55 101 110 66 110 111 77 111 000 0State Transition TableTabular form of state diagramLike a truth-table (specify output for all input combinations)Encoding of states: easy for counters – just use valueN1 := C1'N2 := C1C2' + C1'C2:= C1 xor C2N3 := C1C2C3' + C1'C3 + C2'C3:= C1C2C3' + (C1' + C2')C3:= (C1C2) xor C3EECS150 - Fall 2001 1-11D QQImplementationProgrammable Logic Building Block for Sequential LogicMacro-cell: FF + logicD-FFTwo-level logic capability like PAL (e.g., 8 product terms)EECS150 - Fall 2001 1-12In C1 C2 C3 N1 N2 N30000000000100000100010011001010001001010100110011011101110001001001100101010110111011100110110111011101111111111N1 := InN2 := C1N3 := C2Another ExampleShift RegisterInput determines next state1001101110111010100000010111111100000100DQ DQ DQINOUT1 OUT2 OUT3CLKEECS150 - Fall 2001 1-13State Machine ModelValues stored in registers represent the state of the circuitCombinational logic computes:Next stateFunction of current state and inputsOutputsFunction of current state and inputs (Mealy machine)Function of current state only (Moore machine)InputsOutputsNext StateCurrent Stateoutputlogicnext statelogicEECS150 - Fall 2001 1-14State Machine Model (cont’d)States: S1, S2, ..., SkInputs: I1, I2, ..., ImOutputs: O1, O2, ..., OnTransition function: Fs(Si, Ij)Output function: Fo(Si) or Fo(Si, Ij)InputsOutputsNext StateCurrent Stateoutputlogicnext statelogicClockNext StateState012345EECS150 - Fall 2001 1-15D/1E/1B/0A/0C/01000011110resetcurrent nextreset input state state output1–– A00A B 001A C 000B B 001B D 000C E 001C C 000D E 101D C 100E B 101E D 1Specifying Outputs: Moore MachineOutput is only function of state Specify in state bubble in state diagram Example: sequence detector for 01 or 10EECS150 - Fall 2001 1-16current nextreset input state state output1–– A 000A B 001A C 000B B 001B C 100C B 101C C 0BAC0/10/00/01/11/01/0reset/0Specifying Outputs: Mealy MachineOutput is function of state and inputs Specify output on transition arc between states Example: sequence detector for 01 or 10EECS150 - Fall 2001 1-17state feedbackinputsoutputsregcombinational logic for next statelogic foroutputsinputs outputsstate feedbackregcombinational logic fornext statelogic foroutputsComparison: Mealy/Moore MachinesMealy Machines tend to have less statesDifferent outputs on arcs (n^2) rather than states (n)Moore Machines are safer to useOutputs change at clock edge (always one cycle later)In Mealy machines, input change can cause output change as soon as logic is done – a big problem when two machines are interconnected – asynchronous feedbackMealy Machines react faster to inputsReact in same cycle – don't need to wait for clockIn Moore machines, more logic may be necessary to decode state into outputs – more gate delays after EECS150 - Fall 2001 1-18DQQBAclockoutDQQDQQclockoutABMealy and Moore ExamplesRecognize A,B = 0,1 Mealy or Moore?EECS150 - Fall 2001 1-19DQQDQQDQQDQQABclockoutDQQDQQABclockoutMealy and Moore ExamplesRecognize A,B = 1,0 then 0,1 Mealy or Moore?EECS150 - Fall 2001 1-20Registered Mealy (Really Moore)Synchronous (or registered) Mealy MachineRegistered state AND outputsAvoids ‘glitchy’ outputsEasy to implement in PLDsMoore Machine with no output decodingOutputs computed on transition to next state rather than after enteringView outputs as expanded state vectorInputsOutputsCurrent Stateoutputlogicnext statelogicEECS150 - Fall 2001 1-21Example: Ant Brain (Ward, MIT)Sensors: L and R antennae, 1 if in touching wallActuators: F - forward step, TL/TR - turn left/right slightlyGoal: find way out of mazeStrategy: keep the wall on the rightEECS150 - Fall 2001 1-22A: Following wall, touching Go forward, turning left slightlyB: Following wall, not touching Go forward, turning right slightlyC: Break in wall Go forward, turning right slightlyD: Hit wall again Back to state AE: Wall in
View Full Document
Unlocking...