1Mealy and Moore MachinesECE 152A – Fall 2006November 7, 2006ECE 152A - Digital Design Principles2Reading Assignment Brown and Vranesic 8 Synchronous Sequential Circuits 8.3 Mealy State Model2November 7, 2006ECE 152A - Digital Design Principles3Reading Assignment Roth 13 Analysis of Clocked Sequential Circuits 13.1 A Sequential Parity Checker 13.2 Analysis by Signal Tracing and Timing Charts 13.3 State Tables and Graphs 13.4 General Models for Sequential CircuitsNovember 7, 2006ECE 152A - Digital Design Principles4Finite State Machines Thus far, sequential circuit (counter and register) outputs limited to state variables In general, sequential circuits (or Finite State Machines, FSM’s) have outputs in addition to the state variables For example, vending machine controllers generate output signals to dispense product, provide change, illuminate displays, etc.3November 7, 2006ECE 152A - Digital Design Principles5Finite State Machines Two types (or models) of sequential circuits (or finite state machines) Mealy machine Output is function of present state and present input Moore machine Output is function of present state only Analysis first, then proceed to the design of general finite state machinesNovember 7, 2006ECE 152A - Digital Design Principles6Analysis by Signal Tracing and Timing Diagrams Timing Analysis Determine flip-flop input equations Determine output equations Mealy or Moore model Generate timing diagram illustrating circuit’s response to a particular input sequence Outputs as well as to state4November 7, 2006ECE 152A - Digital Design Principles7Moore Network Example Implemented with falling edge triggered (by way of external inverter) JK flip-flops Schematic (following slide) JA= x KA= xB’ JB= x KB= x XOR A’ = xA + x’A’ z = B (function of present state only)November 7, 2006ECE 152A - Digital Design Principles8Moore Network Example Schematic5November 7, 2006ECE 152A - Digital Design Principles9Moore Network Example Timing Diagram and Analysis Initial conditions: A = B = z = 0 Input sequence: x = 10101 All state and output transitions occur after the falling clock edge Assumes x changes on rising edge Best case assumption for satisfying setup and hold timeNovember 7, 2006ECE 152A - Digital Design Principles10Moore Network Example Timing 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 = B6November 7, 2006ECE 152A - Digital Design Principles11Mealy Network Example Implemented with falling edge triggered (by way of external inverter) JK flip-flops Schematic (following slide) JA= xB KA= x JB= x KB= xA z = xB’ + xA + x’A’B function of present state and present inputNovember 7, 2006ECE 152A - Digital Design Principles12Mealy Network Example Schematic7November 7, 2006ECE 152A - Digital Design Principles13Mealy Network Example Timing Diagram and Analysis Initial conditions: A = B = 0 z = 1 Input sequence: x = 10101 Analysis again assumes x changes on rising edge of clock All state transitions occur after the falling clock edge (as with Moore machine)November 7, 2006ECE 152A - Digital Design Principles14Mealy Network Example Timing Diagram and Analysis (cont) Output transitions occur in response to both input and state transitions “glitches” may be generated by transitions in inputs Moore machines don’t glitch because outputs are associated with present state only Assumes gate delays to output(s) much shorter than clock period All outputs stable before occurrence of active clock edge8November 7, 2006ECE 152A - Digital Design Principles15Mealy Network Example Timing 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=00November 7, 2006ECE 152A - Digital Design Principles16Mealy Machines and Glitches In synchronous network, glitches don’t matter All data transfers occur around common, falling (or rising) clock edge Register transfer operations Outputs sampled only on active clock edge Output is stable before and after active clock edge Setup and hold times satisfied9November 7, 2006ECE 152A - Digital Design Principles17FSM Outputs & Timing - Summary For Moore machine, output is valid after state transition Output associated with stable present state For Mealy machine, output is valid on occurrence of active clock edge Output associated with transition from present state to next state Output in Mealy machine occurs one clock period before output in equivalent Moore machineNovember 7, 2006ECE 152A - Digital Design Principles18Derivation of State Tables and Diagrams Timing diagram illustrates the sequential circuit’s response to a particular input sequence May not include all states and all transitions In general, analysis needs to produce state diagram and state table Reverse of design process Begin with implementation, derive state diagram10November 7, 2006ECE 152A - Digital Design Principles19Derivation of State Tables and Diagrams Returning to Moore machine example Flip-Flop inputs and circuit output functions JA= 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-Flop Q+= JQ’ + K’QNovember 7, 2006ECE 152A - Digital Design Principles20Derivation of State Tables and Diagrams Using characteristic function, generate next state equations and maps for each flip flop Q+= JQ’ + K’Q → A+= JAQ’ + KA’Q A+= xA’ + (xB’)’ A = xA’ + x’A + AB Q+= JQ’ + K’Q → B+= JBQ’ + KB’Q B+= xB’ + (x xor A’)’B = xB’ + xA’B + x’AB11November 7, 2006ECE 152A - Digital Design Principles21Derivation of State Tables and Diagrams Next State MapsABx00 010111 10111ABx00 010111 10111A+= xA’ + x’A + ABB+= xB’ + xA’B + x’AB111November 7, 2006ECE 152A - Digital Design Principles22Derivation of State Tables and Diagrams State Table1101111001101011100010110000z (=B)ABABABX=1X=0PSNS12November 7, 2006ECE 152A - Digital Design Principles23Derivation of State Tables and Diagrams State
View Full Document