New version page

MIT 6 111 - L6: FSMs and Synchronization

Documents in this Course
Verilog

Verilog

21 pages

Video

Video

28 pages

Bass Hero

Bass Hero

17 pages

Deep 3D

Deep 3D

12 pages

SERPENT

SERPENT

8 pages

Vertex

Vertex

92 pages

Vertex

Vertex

4 pages

Snapshot

Snapshot

15 pages

Memories

Memories

42 pages

Deep3D

Deep3D

60 pages

Design

Design

2 pages

Frogger

Frogger

11 pages

SkiFree

SkiFree

81 pages

Vertex

Vertex

10 pages

EXPRESS

EXPRESS

2 pages

Labyrinth

Labyrinth

81 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

L6: 6.111 Spring 2005 1Introductory Digital Systems LaboratoryL6: L6: FSMsFSMsand Synchronizationand SynchronizationLecture material courtesy of Rex MinL6: 6.111 Spring 2005 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 2005 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 2005 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 2005 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 2005 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 2005 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 2005 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 2005 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 2005 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 2005 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 2005 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 2005 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 2005 14Introductory Digital Systems LaboratoryFSM


View Full Document
Download L6: FSMs and Synchronization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view L6: FSMs and Synchronization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view L6: FSMs and Synchronization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?