Clocked Synchronous State-machine AnalysisState Machine Analysis ExampleSlide 3Slide 4Clocked State-machine Analysis: State NamingClocked State-machine Analysis Example: Transition/Output Table Using State NamesClocked State-machine Analysis Example: State Diagram Using State NamingClocked State-machine Analysis: State Machine Timing DiagramState Machine Timing Diagram ExampleState Machine Analysis Example 2Slide 11Slide 12State-machine Analysis Example 2: Transition/Output Table Using State NamesState-machine Analysis Example 2: State Diagram (incomplete)State Machine Analysis Example 3Slide 16Slide 17State-machine Analysis Example 3: Transition/Output Table Using State NamesState-machine Analysis Example 3: State DiagramEECC341 - ShaabanEECC341 - Shaaban#1 Lec # 15 Winter 2001 2-5-2002Clocked Synchronous State-machine AnalysisClocked Synchronous State-machine AnalysisGiven the circuit diagram of a state machine:1Analyze the combinational logic to determine flip-flop input (excitation) equations: Di = Fi (Q, inputs)–The input to each flip-flop is based upon current state and circuit inputs.2Substitute excitation equations into flip-flop characteristic equations, giving transition equations: Qi* = Hi( Di )3From the circuit, find output equations: Z = G (Q, inputs)–The outputs are based upon the current state and possibly the inputs.4Construct a state transition/output table from the transition and output equations:–Similar to truth table.–Present state on the left side.–Outputs and next state for each input value on the right side.–Provide meaningful names for the states in state table, if possible.5Draw the state diagram which is the graphical representation of state table.EECC341 - ShaabanEECC341 - Shaaban#2 Lec # 15 Winter 2001 2-5-2002State Machine Analysis ExampleState Machine Analysis ExampleQ1Q1'Q0Q0'yxCPDQQ'DQQ'Analyze the state machine:1 Input (or excitation) equations: D0 = Q1’. X D1 = Q1 . x + Q0 . x 2 Characteristic equations: Q0* = D0 Q1* = D1 Find State equations: Q0* = Q1’. x Q1* = Q1 . x + Q0 . x 3 Output equation: y = (Q0 + Q1) . x'This is a Mealy Machine since output = G(current state, input)EECC341 - ShaabanEECC341 - Shaaban#3 Lec # 15 Winter 2001 2-5-20024From the state equations and output equation, construct the state transition/output table:State Machine Analysis ExampleState Machine Analysis ExampleState equations: Q0* = Q1’. x Q1* = Q1 . x + Q0 . x Output equation: y = (Q0 + Q1) . x' x Q1 Q0 0 1 0 0 00,0 01,0 0 1 00,1 11,0 1 0 00,1 10,0 1 1 00,1 10,0Q1* Q0* , yCurrent StateNext State when x =0 Output for current state when x =0Next State when x =1 Output for current state when x =1InputEECC341 - ShaabanEECC341 - Shaaban#4 Lec # 15 Winter 2001 2-5-20025Draw the state diagram of the state machine.State Machine Analysis ExampleState Machine Analysis Example x Q1 Q0 0 1 0 0 00,0 01,0 0 1 00,1 11,0 1 0 00,1 10,0 1 1 00,1 10,0Q1* Q0* , y000111101/01/01/00/10/10/01/0 0/1Arc = input x / output yNode = statestate transition/output table state diagramEECC341 - ShaabanEECC341 - Shaaban#5 Lec # 15 Winter 2001 2-5-2002•State Naming:–Optionally name the states and substitute state names S for state-variable combinations in transition/output table and in state diagram.–Example: For a circuit with two flip-flops: Q1 Q0 State Name 0 0 A 0 1 B 1 0 C 1 1 D Clocked State-machine Analysis: Clocked State-machine Analysis: State NamingState NamingEECC341 - ShaabanEECC341 - Shaaban#6 Lec # 15 Winter 2001 2-5-2002Clocked State-machine Analysis Example: Clocked State-machine Analysis Example: Transition/Output Table Using State NamesTransition/Output Table Using State Names x Q1 Q0 0 1 0 0 00,0 01,0 0 1 00,1 11,0 1 0 00,1 10,0 1 1 00,1 10,0Q1* Q0* , yFor the last examplenaming The States:Q1 Q0 State Name 0 0 A 0 1 B 1 0 C 1 1 D Transition/output Table: Transition/output Table using state names: x S 0 1 A A,0 B,0 B A,1 D,0 C A,1 C,0 D A,1 C,0 S* , yABCDEECC341 - ShaabanEECC341 - Shaaban#7 Lec # 15 Winter 2001 2-5-2002Clocked State-machine Analysis Example: Clocked State-machine Analysis Example: State Diagram Using State NamingState Diagram Using State NamingNaming The States:Q1 Q0 State Name 0 0 A 0 1 B 1 0 C 1 1 D 000111101/01/01/00/10/10/01/0 0/1Arc = input x / output yNode = stateState Diagram without state naming: State Diagram with state naming: A B D C1/01/01/00/10/10/01/0 0/1EECC341 - ShaabanEECC341 - Shaaban#8 Lec # 15 Winter 2001 2-5-2002•The timing diagram for a state machine graphically shows the state machine response in terms of state variables and output signals vs. time for given time-varying input signals and a given initial state.•State machine timing diagrams can be generated using transition/output tables or state diagrams.•Timing diagrams can be used to account for both combinational and flip-flop propagation delays.•Example: For the state machine in the previous example show the timing diagram for the following input, assuming an initial state A and ignoring propagation delays:Clocked State-machine Analysis: State Machine Timing DiagramClock 10Input X Cycle: 0 1 2 3 4 5 6 710TimeEECC341 - ShaabanEECC341 - Shaaban#9 Lec # 15 Winter 2001 2-5-2002State Machine Timing Diagram ExampleState Machine Timing Diagram ExampleClock 10Input X Cycle: 0 1 2 3 4 5 6 7Q1 Q0 Output Y 10A B D C A A B A1010TimeEECC341 - ShaabanEECC341 - Shaaban#10 Lec # 15 Winter 2001 2-5-2002State Machine Analysis Example 2State Machine Analysis Example 2Analyze the state machine:D Q CLK QD Q CLK QD Q CLK QXYQ2’Q0Q1CLK D0 D1D2Q0Q1Q2Z1Z2State MemoryInput Logic FOutput Logic GQ2’EECC341 - ShaabanEECC341 - Shaaban#11 Lec # 15 Winter 2001