L6: FSMs and SynchronizationAsynchronous Inputs in Sequential SystemsAsynchronous Inputs in Sequential SystemsHandling MetastabilityFinite State MachinesReview: FSM Timing RequirementsTwo 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-OffsThe 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 2008 1Introductory Digital Systems LaboratoryL6: L6: FSMsFSMs and Synchronizationand SynchronizationLecture material courtesy of Rex MinLecture notes prepared by Professor Anantha ChandrakasanL6: 6.111 Spring 2008 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 metastable for an indeterminate amount of time.Q: Which cases are problematic?L6: 6.111 Spring 2008 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-flopD QSequential SystemClockThis prevents the possibility of I and II occurring in different places in the circuit, but what about metastability?D QD QQ0ClockClockQ1AsyncInputClocked Synchronous SystemL6: 6.111 Spring 2008 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 sufficientD QComplicated Sequential Logic SystemClockD QD QLikeley to be metastable right after samplingVery unlikely to be metastable for >1 clock cycleExtremely unlikely to be metastable for >2 clock cycleL6: 6.111 Spring 2008 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+present stateoutputs+next statennL6: 6.111 Spring 2008 6Introductory Digital Systems LaboratoryReview: FSM Timing RequirementsReview: FSM Timing Requirements Timing requirements for FSM are identical to any generic sequential system with feedbackT > Tcq + Tlogic + TsuTcq,cd + Tlogic,cd > TholdCombinationalLogicFlip- FlopsQDCLKinputs+present stateoutputs+next statennTcqTsuTlogicCombinationalLogicFlip- FlopsQDCLKinputs+present stateoutputs+next statennTcq,cdTholdTTlogic,cdMinimum Clock Period Minimum DelayL6: 6.111 Spring 2008 7Introductory Digital Systems LaboratoryTwo Types of Two Types of FSMsFSMsMoore and Mealy FSMs are distinguished by their output generationoutputs yk = fk (S)inputs x0 ...xninputs x0 ...xnMoore FSM:Mealy FSM:Comb.LogicCLKnFlip- FlopsComb.LogicDQpresent state Snnext state S+SComb.LogicCLKFlip- FlopsComb.LogicDQnS+noutputs yk = fk (S, x0 ...xn )direct combinational path!L6: 6.111 Spring 2008 8Introductory 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 to Pulse ConverterL PCLKWhenever input L goes from low to high......output P produces a single pulse, one clock period wide.L6: 6.111 Spring 2008 9Introductory Digital Systems LaboratoryState Transition DiagramsState Transition Diagrams Block diagram of desired system: State transition diagram is a useful FSM representation and design aid00 Low input, Waiting for rise P = 001 Edge Detected! P = 1High input, Waiting for fallD QLevel to Pulse FSML Punsynchronized user 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.”D QCLKL6: 6.111 Spring 2008 10Introductory 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)00 Low input, Waiting for rise P = 001 Edge Detected! P = 111High input, Waiting for fallP = 0L=1L=1L=0L=0L=1L=0Current StateInNext StateOutS1S0L S1+S0+P0 0 0 0 0 00 0 1 0 1 00 1 0 0 0 10 1 1 1 1 11 1 0 0 0 01 1 1 1 1 0 Combinational logic may be derived by Karnaugh mapsComb.LogicCLKnFlip- FlopsComb.LogicDQSnS+00 01 11 100 0 0 0 X1 0 1 1 X00 01 11 100 0 0 0 X1 1 1 1 XS1 S0LS1 S0Lfor S1+:for S0+:0 10 0 X1 1 0S1for P:LPS0S1 + = LS0 S0 + = L S1+ = LS0 S0+ = LP = S1 S0 P = S1 S0L6: 6.111 Spring 2008 11Introductory Digital Systems LaboratoryMoore LevelMoore Level--toto--Pulse ConverterPulse ConverterMoore FSM circuit implementation of level-to-pulse converter:outputs yk = fk (S)inputs x0 ...xnComb.LogicCLKnFlip- FlopsComb.LogicDQpresent state Snnext state S+D QS1 + = LS0 S0 + = L S1+ = LS0 S0+ = LP = S1 S0 P = S1 S0D QS0S1CLKS0+S1+LPQQL6: 6.111 Spring 2008 12Introductory Digital Systems LaboratoryDesign of a Mealy LevelDesign of a Mealy Level--toto--PulsePulse Since outputs
View Full Document