Digital Logic Design - Lecture 22: Sequential Circuits Analysis

Lecture 22Sequential Circuits AnalysisCombinational vs. SequentialCombinational Logic CircuitOutput is a function only of the present inputs.Does not have state information.Does not require memory.Sequential Logic Circuit (Finite State Machine)Output is a function of the present state and at times present state and input.Has state informationRequires memory.Uses Flip-Flops to implement memory.Synchronous vs. AsynchronousSynchronous Sequential Logic CircuitClockedAll Flip-Flops use the same clock and change state on the same triggering edge.Asynchronous Sequential Logic CircuitNo clockCan change state at any instance in time.Faster but more complex than synchronous sequential circuits.General Models for Sequential CircuitsA sequential circuit can be divided conveniently into two parts -- the flip-flops which serve as memory for the circuit and the combinational logic which realizes the input functions for the flip-flops and the output functions.The combinational logic may be implemented with gates, with a ROM, or with a PLA.Sequential Logic (Why) ?Sequential circuit has additional dimension which is timeCombinational logic only depends on current inputSequential circuit output depends on previous input other than current inputMore powerful than combinational logicAble to model condition that can’t be accommodated by combinational logic Analysis of Clocked Sequential CircuitsAnalysis of a sequential circuit consists of obtaining a table or a diagram for the time sequence of inputs, outputs, and internal states.Sequential circuit behavior is determined from the inputs, the outputs, and the state of its flip-flopsBoolean expressions that describe the behavior of the sequential circuitOutputs and the next state are both a function of the inputs and the present stateA logic diagram is recognized as a clocked sequential circuit if it includes flip-flops.Logic diagram may or may not include combinational circuit gates.The Current “State”It is inconvenient, and often impossible, to describe the behaviour of a sequential circuit by means of a table that lists outputs as a function of the input sequence that has been received up until the current time.To know where you are going next, you need to know where you are now.With the TV channel selector, it is impossible to determine what channel is currently selected by looking only at the preceding sequence of presses, whether we look at the preceding 10 presses or the preceding 1000.More information, the current “state” of the channel selector, is needed.StateThe state of a sequential circuit is a collection of state variables whose values at any particular time contain all the information about the past necessary to account for the circuit’s future behaviour.In the channel-selector example, the current channel number is the current state.Inside the TV, this state might be stored as seven binary state variables representing a decimal number between 1 and 9.Given the current state (channel number), we can always predict the next state as a function of the inputs (up/down pushes).“Finite-State Machines”In a digital circuit, state variables have binary values.A circuit with n binary state variables has 2n possible states.2n is always finite, so sequential circuits are sometimes called finite-state machines. D Flip-Flop with Clock input Q(t+1) = Q.D + Q.D = D.(Q +Q) = D.1 = DBoolean equation for D Flip-Flop Sequential Circuit AnalysisGiven sequential circuit diagram, behavioral analysis from state table and also state diagramNeed state equations to get flip-flop input and output functions for circuit output other than flip-flop (if any)A(t) and A(t+1) are used to represent current state and the next state for flip-flop.A and A+ can also be used in order to represent current state and the following stateSequential Circuit AnalysisExample (using D flip-flop)State equationOutput FunctionSequential Circuit AnalysisFrom the state equations and output function, state table can be derived that contains all combined binary combination for the current condition (present state) and inputState tableThe same as Truth TableInput and condition pad on the leftOutput and next condition on the rightCombined binary combination available for current state and inputM flip-flop and n input => 2m+n lineSequential Circuit AnalysisState table for circuit in Example 1From the state equations and output function, state table can be derived that contains all combined binary combination for the current condition (present state) and inputState tableThe same as Truth TableInput and condition pad on the leftOutput and next condition on the rightcombined binary combination available for current state and inputM flip-flop and n input => 2m+n lineState equation Output functionSequential Circuit AnalysisOther methodSequential Circuit AnalysisFrom the truth table, we can draw state diagramState diagramEach state is represented by circleEach arrow (between two circle) represent transfer for sequential logic (i.e. line transition in truth table)a/b label for each arrow where a represent inputs and b represent output for circuit in transitionEach flip-flop value combination represent state. Therefore, m flip-flop=> until 2m state.Sequential Circuit Analysis State diagram for circuit in previous exampleEach state is represented by circleEach arrow (between two circle) represent transfer for sequential logic (i.e. line transition in truth table)a/b label for each arrow where a represent inputs and b represent output for circuit in transitionFlip-flop Input FunctionOutput of sequential circuit is a function of the current state of the flip-flop and the input. This is explained using algebra by circuit output functionIn previous example : y= (A+B)x’Circuit part that generate input to flip-flop is represented by using Boolean equation and is known as flip-flop input’s functionFlip-flop input function determine next stateFrom flip-flop input function and criteria table for flip-flop, next state of the flip-flop is obtainedFlip-flop Input FunctionExample: circuit with JK flip flop2 characters are used in order to represent flip-flop input: first character represents the flip-flop input (J or K for JK flip-flop, S or R for SR flip-flop, D for D flip-flop, T for T flip-flop respectively) and the second character represents the name of the flip-flopAnalysis: Example Given a sequential circuit with two JK flip-flop, namely A, B and one input xFlip-flop input function obtained from the circuit isAnalysis: Example Input flip-flop functionFill the state table with the above function using criteria table for the used flip-flopAnalysis: Example Draw state diagram from the state tableFlip-flop Excitation TablesAnalysis Vs DesignAnalysis: Start from circuit diagram, build state table or state diagramDesign: Start from specification set (i.e. in state equation form, state table or state diagram) build logic circuit.Criteria table is used in analysisExcitation tables is used in designFlip-flop Excitation TablesExcitation tables : it give transition characteristic between current state and next state to determine flip-flop inputDesigning Sequential CircuitDesign stepsStart with circuit specification – characteristic of circuitBuild state tablePerform state reduction if required State assignment Determine number of flip-flop ( that has to be used)Build circuit excitation and output table from state tableBuild circuit output function and flip-flop input functionDraw logic diagramDesign: Example Given state diagram as follows, get the sequential circuit using JK flip-flopDesign: ExampleState/excitation table using JK flip-flopFor example, in the first row of Table (bottom right), we have a transition for flip-flop A from 0 in the present state to 0 in the next state. In Table (excitation table), we find that a transition of states from 0 to 0 requires that input J= 0 and input K = XDesign: ExampleBlock diagramDesign: ExampleFrom state table, get input flip-flop functionDesign: ExampleInput flip-flop functionLogic DiagramDesign: ExampleDesign, using D flip-flop, circuit is based on state table below.Design: ExampleDetermine input expression for flip-flop and y outputDesign ExampleFrom Boolean expressions built, draw logic diagramDesign: ExampleHow if using JK flip-flop (Homework)Design a Synchronous CounterCounter: sequential circuit cycle through state sequenceBinary counter: follow binary sequence. n-bit binary counter (with n flip-flop) able to count from 0 to 2n-1.Example: 3-bit binary counter (using T flip-flop)Design a Synchronous Counter3-bit binary counter (cont)Design a Synchronous Counter3-bit binary counterSequential Circuit DesignSequential circuit consists of A combinational circuit that produces outputA feedback circuitWe use JK flip-flops for the feedback circuit Simple counter examples using JK flip-flopsProvides alternative counter designsWe know the outputNeed to know the input combination that produces this outputUse an excitation tableBuilt from the truth tableSequential Circuit Design (cont’d)Sequential Circuit Design (cont’d)Build a design table that consists ofCurrent state outputNext state outputJK inputs for each flip-flopBinary counter example3-bit binary counter3 JK flip-flops are neededCurrent state and next state outputs are 3 bits each3 pairs of JK inputsSequential Circuit Design (cont’d)Design table for the binary counter exampleSequential Circuit Design (cont’d)Use K-maps to simplify expressions for JK inputsSequential Circuit Design (cont’d)Final circuit for the binary counter exampleCompare this design with the synchronous counter designThanks