1Mealy and Moore MachinesECE 152A – Summer 2009August 3, 2009ECE 152A - Digital Design Principles2Reading AssignmentBrown and Vranesic8 Synchronous Sequential Circuits8.3 Mealy State Model2August 3, 2009ECE 152A - Digital Design Principles3Reading AssignmentRoth13 Analysis of Clocked Sequential Circuits13.1 A Sequential Parity Checker13.2 Analysis by Signal Tracing and Timing Charts13.3 State Tables and Graphs13.4 General Models for Sequential CircuitsAugust 3, 2009ECE 152A - Digital Design Principles4Finite State MachinesThus far, sequential circuit (counter and register) outputs limited to state variablesIn general, sequential circuits (or Finite State Machines, FSM’s) have outputs in addition to the state variablesFor example, vending machine controllers generate output signals to dispense product, provide change, illuminate displays, etc.3August 3, 2009ECE 152A - Digital Design Principles5Finite State MachinesTwo types (or models) of sequential circuits (or finite state machines)Mealy machineOutput is function of present state and present inputMoore machineOutput is function of present state onlyAnalysis first, then proceed to the design of general finite state machinesAugust 3, 2009ECE 152A - Digital Design Principles6Analysis by Signal Tracing and Timing DiagramsTiming AnalysisDetermine flip-flop input equationsDetermine output equationsMealy or Moore model Generate timing diagram illustrating circuit’s response to a particular input sequenceOutputs as well as to state4August 3, 2009ECE 152A - Digital Design Principles7Moore Network ExampleImplemented with falling edge triggered (by way of external inverter) JK flip-flopsSchematic (following slide)JA= x KA= xB’JB= x KB= x XOR A’ = xA + x’A’z = B (function of present state only)August 3, 2009ECE 152A - Digital Design Principles8Moore Network ExampleSchematic5August 3, 2009ECE 152A - Digital Design Principles9Moore Network ExampleTiming Diagram and AnalysisInitial conditions:A = B = z = 0Input sequence:x = 10101All state and output transitions occur after the falling clock edgeAssumes x changes on rising edgeBest case assumption for satisfying setup and hold timeAugust 3, 2009ECE 152A - Digital Design Principles10Moore Network ExampleTiming Diagram (Functional Simulation)x=1z=1x=0z=1x=1z=0x=0z=0x=1z=1x=1A=B=z=0AB=11AB=11AB=10 AB=10AB=01JA= x KA= xB’JB= x KB= x XOR A’ = xA + x’A’z = B6August 3, 2009ECE 152A - Digital Design Principles11Mealy Network ExampleImplemented with falling edge triggered (by way of external inverter) JK flip-flopsSchematic (following slide)JA= xB KA= xJB= x KB= xAz = xB’ + xA + x’A’Bfunction of present state and present inputAugust 3, 2009ECE 152A - Digital Design Principles12Mealy Network ExampleSchematic7August 3, 2009ECE 152A - Digital Design Principles13Mealy Network ExampleTiming Diagram and AnalysisInitial conditions:A = B = 0 z = 1Input sequence:x = 10101Analysis again assumes x changes on rising edge of clockAll state transitions occur after the falling clock edge (as with Moore machine)August 3, 2009ECE 152A - Digital Design Principles14Mealy Network ExampleTiming Diagram and Analysis (cont)Output transitions occur in response to both input and state transitions“glitches” may be generated by transitions in inputsMoore machines don’t glitch because outputs are associated with present state onlyAssumes gate delays to output(s) much shorter than clock periodAll outputs stable before occurrence of active clock edge8August 3, 2009ECE 152A - Digital Design Principles15Mealy Network ExampleTiming Diagram (Timing Simulation)x=1 x=0 x=1 x=0 x=1z=1 z=1 z=0 z=0 z=1false 0 false 1JA= xB KA= xJB= x KB= xAz = xB’ + xA + x’A’BxB’ x’A’B xA xA xB’AB=00 AB=01 AB=01AB=11AB=11AB=00August 3, 2009ECE 152A - Digital Design Principles16Mealy Machines and GlitchesIn synchronous network, glitches don’t matterAll data transfers occur around common, falling (or rising) clock edgeRegister transfer operationsOutputs sampled only on active clock edgeOutput is stable before and after active clock edgeSetup and hold times satisfied9August 3, 2009ECE 152A - Digital Design Principles17FSM Outputs & Timing - SummaryFor Moore machine, output is valid after state transitionOutput associated with stable present stateFor Mealy machine, output is valid on occurrence of active clock edgeOutput associated with transition from present state to next stateOutput in Mealy machine occurs one clock period before output in equivalent Moore machineAugust 3, 2009ECE 152A - Digital Design Principles18Derivation of State Tables and DiagramsTiming diagram illustrates the sequential circuit’s response to a particular input sequenceMay not include all states and all transitionsIn general, analysis needs to produce state diagram and state tableReverse of design processBegin with implementation, derive state diagram10August 3, 2009ECE 152A - Digital Design Principles19Derivation of State Tables and DiagramsReturning to Moore machine exampleFlip-Flop inputs and circuit output functionsJA= x KA= xB’JB= x KB= x XOR A’ = xA + x’A’z = B (function of present state only)Begin with characteristic equation for JK Flip-FlopQ+= JQ’ + K’QAugust 3, 2009ECE 152A - Digital Design Principles20Derivation of State Tables and DiagramsUsing characteristic function, generate next state equations and maps for each flip flopQ+= JQ’ + K’Q → A+= JAQ’ + KA’QA+= xA’ + (xB’)’ A = xA’ + x’A + ABQ+= JQ’ + K’Q → B+= JBQ’ + KB’QB+= xB’ + (x xor A’)’B = xB’ + xA’B + x’AB11August 3, 2009ECE 152A - Digital Design Principles21Derivation of State Tables and DiagramsNext State MapsABx00 010111 101 11ABx00 010111 10111A+= xA’ + x’A + ABB+= xB’ + xA’B + x’AB1 11August 3, 2009ECE 152A - Digital Design Principles22Derivation of State Tables and DiagramsState Table1101111001101011100010110000z (=B)ABABABX=1X=0PSNS12August 3, 2009ECE 152A - Digital Design Principles23Derivation of State Tables and DiagramsState Diagram000100011111X=1X=0X=1X=0X=1X=0X=1X=01101111001101011100010110000z (=B)ABABABX=1X=0PSNSAugust 3, 2009ECE 152A - Digital Design Principles24Derivation of State Tables and DiagramsMealy
View Full Document