Clocked Synchronous State-MachinesClocked Synchronous State-Machine ModelLatch/Flip-Flop Characteristic EquationsCharacteristic EquationsSlide 5Slide 6Clocked Synchronous State-machine AnalysisState DiagramState Machine Analysis ExampleSlide 10Slide 11EECC341 - ShaabanEECC341 - Shaaban#1 Lec # 14 Winter 2001 1-30-2002Clocked Synchronous State-Machines•Such machines have the characteristics:–Sequential circuits designed using flip-flops.–All flip-flops use a common clock (clocked synchronous).–A machine using n flip-flops (state memory) has n state variables (the outputs of the flip-flops) and 2n states.–In general, the next state and output of the machine both depend on the current state of the machine and on the current input: Next state = F(current state, input) output = G(current state, input) This type of state machine is called Mealy Machine–In some cases the next output depends only on the current state and not directly on the current input – Next state = F(current state, input) output = G(current state) Such machines are called Moore machines.EECC341 - ShaabanEECC341 - Shaaban#2 Lec # 14 Winter 2001 1-30-2002Clocked Synchronous State-Machine ModelClocked Synchronous State-Machine ModelNext-stateLogicFStateMemoryclockOutputLogicGexcitationcurrent stateoutputs(Mealy machine)Moore MachineState memory:Usually edge-triggeredD or JK flip-flopsinputsclockEECC341 - ShaabanEECC341 - Shaaban#3 Lec # 14 Winter 2001 1-30-2002Latch/Flip-Flop Characteristic Equations•The next output of a flip flop (or next state) can be obtained from the function table of each type of flip-flop.•This latch/flip-flop next output behavior is expressed in as a characteristic function which gives the next state in terms of the current state and output: Q* = f (Q , inputs) (Q* is the next state of Q).•Vary important in state machine analysis and design.EECC341 - ShaabanEECC341 - Shaaban#4 Lec # 14 Winter 2001 1-30-2002 D latch or flip-flop present nextinput state state D Q(t) Q* ________________________________________ 0 0 0 0 1 0 1 0 1 1 1 1________________________________________ Characteristic Equation: Q* = D S-R latch S R Q(t) Q* ____________________________________________________ 0 0 0 0 0 0 1 1 0 1 X 0 1 0 X 1 1 1 X X __________________________________________________ Characteristic Equation: Q* = S + R’. QCharacteristic EquationsCharacteristic EquationsEECC341 - ShaabanEECC341 - Shaaban#5 Lec # 14 Winter 2001 1-30-2002Characteristic EquationsCharacteristic Equations J-K flip-flop J K Q Q*_______________________________________________________ 0 0 0 0 0 0 1 1 = hold 0 1 0 0 0 1 1 0 = reset 1 0 0 1 1 0 1 1 = set 1 1 0 1 1 1 1 0 = flip ______________________________________________________ Characteristic Equation: Q* = J . Q’ + K’. Q T flip-flop with enable T Q Q* ________________________________________ 0 0 0 0 1 1 1 0 1 1 1 0 ________________________________________ Characteristic Equation: Q* = T. Q’ + T’ .QEECC341 - ShaabanEECC341 - Shaaban#6 Lec # 14 Winter 2001 1-30-2002 Device Characteristic Equations S-R latch Q* = S+R’.Q D latch Q* = D Edge-triggered D flip-flop Q* = D Master/Slave S-R flip-flop Q* = S+R’.Q Master/Slave J-K flip flop Q* = J.Q’ + K’.Q Edge Triggered J-K flip-flop Q* = J.Q’ + K’.Q T flip-flop Q* = Q’ T flip-flop with enable Q* = EN.Q’ + EN’.QLatch/Flip-Flop Characteristic EquationsLatch/Flip-Flop Characteristic EquationsEECC341 - ShaabanEECC341 - Shaaban#7 Lec # 14 Winter 2001 1-30-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#8 Lec # 14 Winter 2001 1-30-2002B10, 1A0 1B1 / 10 / 1, 1 / 0 A0MooreMealyState Diagram0/0Format:Arc = input XNode = state/output QFormat:Arc = input X / mealy output YNode = stateStateOutputInputBasic Format:EECC341 - ShaabanEECC341 - Shaaban#9 Lec # 14 Winter 2001 1-30-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#10 Lec # 14 Winter 2001 1-30-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