L6: FSMs and SynchronizationAsynchronous Inputs in Sequential SystemsAsynchronous Inputs in Sequential SystemsHandling MetastabilityFinite State MachinesTwo Types of FSMsDesign Example: Level-to-PulseState Transition DiagramsLogic Derivation for a Moore FSMMoore Level-to-Pulse ConverterDesign of a Mealy Level-to-PulseMealy Level-to-Pulse ConverterMoore/Mealy Trade-OffsReview: FSM Timing RequirementsThe 6.111 Vending MachineWhat States are in the System?A Moore VenderState ReductionVerilog for the Moore VenderVerilog for the Moore VenderSimulation of Moore VenderCoding Alternative: Two BlocksFSM Output GlitchingRegistered FSM Outputs are Glitch-FreeMealy Vender (covered in Recitation)Verilog for Mealy FSM Verilog for Mealy FSM Simulation of Mealy VenderDelay Estimation : Simple RC NetworksClocks are Not Perfect: Clock SkewPositive and Negative SkewClocks are Not Perfect: Clock JitterSummaryL6: 6.111 Spring 2006 1Introductory Digital Systems LaboratoryL6: L6: FSMsFSMsand Synchronizationand Synchronizationre courtesy of the following sources and are used with permission. J. Rabaey, A. Chandrakasan, B. Nikolic. Digital Integrated Circuits: A Design Perspective.Prentice Hall/Pearson, 2003., 2003.Acknowledgements: Materials in this lecture aRex MinL6: 6.111 Spring 2006 2Introductory Digital Systems LaboratoryAsynchronous Inputs in Sequential SystemsAsynchronous Inputs in Sequential SystemsWhat about external signals?Sequential SystemClockCan’t guarantee setup and hold times will be met!When an asynchronous signal causes a setup/hold violation...ClockQD?I II IIITransition is missed on first clock cycle, but caught on next clock cycle.Transition is caught on first clock cycle.Output is metastablefor an indeterminate amount of time.Q: Which cases are problematic?Courtesy of Nathan Ickes. Used with permission.L6: 6.111 Spring 2006 3Introductory Digital Systems LaboratoryAsynchronous Inputs in Sequential SystemsAsynchronous Inputs in Sequential SystemsAll of them can be, if more than one happens simultaneously within the same circuit.Idea: ensure that external signals directly feed exactly one flip-flopDQSequential SystemClockThis prevents the possibility of I and II occurring in different places in the circuit, but what about metastability?D QD QQ0ClockClockQ1AsyncInputClocked Synchronous SystemCourtesy of Nathan Ickes. Used with permission.L6: 6.111 Spring 2006 4Introductory Digital Systems LaboratoryHandling Handling MetastabilityMetastability Preventing metastability turns out to be an impossible problem High gain of digital devices makes it likely that metastable conditions will resolve themselves quickly Solution to metastability: allow time for signals to stabilizeHow many registers are necessary? Depends on many design parameters(clock speed, device speeds, …) In 6.111, one or maybe two synchronization registers is sufficientDQComplicated Sequential Logic SystemClockDQDQLikely to be metastableright after samplingVery unlikely to be metastable for >1 clock cycleExtremely unlikely to be metastable for >2 clock cycleL6: 6.111 Spring 2006 5Introductory Digital Systems LaboratoryFinite State MachinesFinite State Machines Finite State Machines (FSMs) are a useful abstraction for sequential circuits with centralized “states” of operation At each clock edge, combinational logic computes outputs and next state as a function of inputs and present stateCombinationalLogicFlip-FlopsQDCLKinputs+presentstateoutputs+nextstatennL6: 6.111 Spring 2006 6Introductory Digital Systems LaboratoryTwo Types of Two Types of FSMsFSMsMoore and Mealy FSMs are distinguished by their output generationoutputsyk= fk(S)inputsx0...xnMoore FSM:inputsx0...xnMealy FSM:Comb.LogicCLKnFlip-FlopsComb.LogicDQpresent state SnnextstateS+SComb.LogicCLKFlip-FlopsComb.LogicDQnS+noutputsyk= fk(S, x0...xn)direct combinational path!L6: 6.111 Spring 2006 7Introductory Digital Systems LaboratoryDesign Example: LevelDesign Example: Level--toto--PulsePulse A level-to-pulse converter produces a single-cycle pulse each time its input goes high. In other words, it’s a synchronous rising-edge detector. Sample uses: Buttons and switches pressed by humans for arbitrary periods of time Single-cycle enable signals for countersLevel toPulseConverterLPCLKWhenever input L goes from low to high......output P produces a single pulse, one clock period wide.L6: 6.111 Spring 2006 8Introductory Digital Systems LaboratoryState Transition DiagramsState Transition Diagrams Block diagram of desired system: State transition diagram is a useful FSM representation and design aid00Low input, Waiting for riseP = 001Edge Detected!P = 1High input,Waiting for fallDQLevel toPulseFSMLPunsynchronizeduser inputSynchronizerEdge DetectorL=1This is the output that results from this state. (Moore or Mealy?)L=0P = 011Binary values of statesL=0L=0L=1L=1“if L=0 at the clock edge, then stay in state 00.”“if L=1 at the clock edge, then jump to state 01.”DQCLKL6: 6.111 Spring 2006 9Introductory Digital Systems LaboratoryLogic Derivation for a Moore FSMLogic Derivation for a Moore FSM Transition diagram is readily converted to a state transition table (just a truth table)00Low input, Waiting for riseP = 001Edge Detected!P = 111High input,Waiting for fallP = 0L=1L=1L=0L=0L=1L=0Current StateInNext StateOutS1L01010S1+S0+10P00110101001000101000011S0001111 Combinational logic may be derived by Karnaugh mapsComb.LogicCLKnFlip-FlopsComb.LogicDQSnS+X1101X000010110100X1111X000010110100S1S0LS1S0Lfor S1+:for S0+:011X0010S1for P:LPS0S1+= LS0S0+= LS1+= LS0S0+= LP = S1S0P = S1S0L6: 6.111 Spring 2006 10Introductory Digital Systems LaboratoryMoore LevelMoore Level--toto--Pulse ConverterPulse ConverterMoore FSM circuit implementation of level-to-pulse converter:outputsyk= fk(S)inputsx0...xnComb.LogicCLKnFlip-FlopsComb.LogicDQpresent state SnnextstateS+DQS1+= LS0S0+= LS1+= LS0S0+= LP = S1S0P = S1S0DQS0S1CLKS0+S1+LPQQL6: 6.111 Spring 2006 11Introductory Digital Systems LaboratoryDesign of a Mealy LevelDesign of a Mealy Level--toto--PulsePulse Since outputs are determined by state and inputs, Mealy FSMs may need fewer states than Moore FSM implementations0Input is lowSComb.LogicCLKFlip-FlopsComb.LogicDQnS+ndirect combinational path!1Input is highPLStateClock1. When L=1 and S=0, this output is asserted immediately and until the state transition occurs (or L changes).2. After the transition to S=1 and as long as L remains at 1,
View Full Document
Unlocking...