L6: 6.111 Spring 2004 1Introductory Digital Systems LaboratoryL6: L6: FSMsFSMsand Synchronizationand SynchronizationLecture material courtesy of Rex MinL6: 6.111 Spring 2004 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?L6: 6.111 Spring 2004 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 SystemL6: 6.111 Spring 2004 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 SystemClockDQDQLikeley to be metastableright after samplingVery unlikely to be metastable for >1 clock cycleExtremely unlikely to be metastable for >2 clock cycleL6: 6.111 Spring 2004 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 2004 6Introductory Digital Systems LaboratoryTwo Types of Two Types of FSMsFSMsMoore and Mealy FSMs are distinguished by their output generationoutputsyk= fk(S)inputsx0...xninputsx0...xnMoore FSM:Mealy FSM:Comb.LogicCLKnFlip-FlopsComb.LogicDQpresent state SnnextstateS+SComb.LogicCLKFlip-FlopsComb.LogicDQnS+noutputsyk= fk(S, x0...xn)direct combinational path!L6: 6.111 Spring 2004 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 2004 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 2004 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=0101010LIn001100POut101010S0+101000S1+110000S1Next StateCurrent State111100S0 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 2004 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 2004 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, this output is asserted.L=1 | P=1L=0 | P=0L=1 | P=0L=0 | P=0Output transitions immediately.State transitions at the clock edge.12L6: 6.111 Spring 2004 12Introductory Digital Systems LaboratoryMealy LevelMealy Level--toto--Pulse ConverterPulse ConverterMealy FSM circuit implementation of level-to-pulse converter:0Input is low1Input is highL=1 | P=1L=0 | P=0L=1 | P=0L=0 | P=01010LIn0010POut1010S+Next StatePres. State1100SDQSCLKS+LPQS FSM’s state simply remembers the previous value of L Circuit benefits from the Mealy FSM’s implicit single-cycle assertion of outputs during state transitionsL6: 6.111 Spring 2004 13Introductory Digital Systems LaboratoryMoore/Mealy TradeMoore/Mealy Trade--OffsOffs Remember that the difference is in the output: Moore outputs are based on state only Mealy outputs are based on state and input Therefore, Mealy outputs generally occur one cycle earlier than a Moore:PLStateClock Compared to a Moore FSM, a Mealy FSM might... Be more difficult to conceptualize and design Have fewer statesPLState[0]ClockMoore: delayed assertion of P Mealy: immediate assertion of PL6: 6.111 Spring 2004 14Introductory Digital Systems LaboratoryFSM
View Full Document
Unlocking...