Digital Logic Design - Lecture 23: More Sequential Circuit Analysis and Design

Lecture 24More Sequential Circuit Analysis and DesignAnalysis by Signal TracingWe can analyze clocked sequential circuits to find the output sequence resulting from a given input sequence by tracing 0 and 1 signals through the circuit. The basic procedure is:Assume an initial state of the flip-flops (all flip-flops reset to 0 unless otherwise specified).For the first input in the given sequence, determine the circuit output(s) and flip-flop inputs.Determine the new set of flip-flop states after the next active clock edge.Determine the output(s) that corresponds to the new states.Repeat 2, 3, and 4 for each input in the given sequence.Example: Serial AdderThe serial adder adds two n-bit binary numbers.serial inputsserial outputExample: Serial AdderTruth Table for the Full Adder:serial inputsserial outputExample: Serial AdderTiming Diagram for the Serial Adder:Timing Diagram for Serial AdderExample: Serial AdderState Graph for the Serial Adder:Analysis - GoalsCharacterize as Mealy or Moore machineDetermine next state equations, i.e., find the function Fnext state = F (current state, inputs)Determine output equationsMeally: outputs = F (current state, inputs), orMoore: outputs = F (current state)Express as machine behavior State table, or State diagramFormulate English description of machine behaviorState Reduction and AssignmentAnalysis of sequential circuits starts from a circuit diagram and culminates in a state table or diagram.Design of a sequential circuit starts from a set of specifications and culminates in a logic diagramAny design process must consider the problem of minimizing the cost of the final circuit Two most obvious cost reductions are Reductions in the number of flip-flops Reductions in the number of gatesReduction of the number of flip-flops in a sequential circuit is referred to as the state-reduction problemState-reduction algorithms are concerned with procedures for reducing the number of states in a state table while keeping the external input-output requirements unchangedSequential Logic Optimization and TradeoffsState Reduction and AssignmentPros and Cons of State ReductionPros Since m flip-flops produce 2m states, a reduction in the number of states may (or may not) result in a reduction in the number of flip-flops.ConsSometimes the reduction in the number of Flip Flops results in the additional number of combinational gates, so the combinational logic may increase State Reduction (Example) Input-output sequences are important; the internal states are used merely to provide the required sequences. That’s why the states marked inside the circles are denoted by letter symbols instead of by their binary values Input sequence 01010110100 starting from the initial state a.State Reduction (Example)Is it possible to reduce this FSM?we use letters to denote states rather than binary codeswe only consider input/output sequence and transitionsIn order to have possible state reduction we need to go through certain number of stepsState Reduction (Example)Step 1: get the state tableState Reduction (Example)Step 1: get the state tableStep 2: find similar states e and g are equivalent states remove g and replace it with eState Reduction (Example)Step 1: get the state tableStep 2: find similar states e and g are equivalent states remove g and replace it with eState Reduction (Example)Step 1: get the state tableStep 2: find similar states d and f are equivalent states remove f and replace it with dState Reduction (Example)Step 1: get the state tableStep 2: find similar states d and f are equivalent states remove f and replace it with dState Reduction (Example)Reduced FSMVerify sequence:Stateaabcdeffgfinput010101101output000001101State AssignmentState Assignment: Assign unique binary codes to the statesExample Three Possible Assignments:Design of Synchronous Sequential CircuitsObtain a state diagramState reduction if necessaryObtain State TableState AssignmentChoose type of flip-flopsUse FF’s excitation table to complete the tableDerive state equationsUse K-MapsObtain the FF input equations and the output equationsDraw the circuit diagramExample: Sequence RecognizerExample: Recognize the sequence 1101Note that the sequence 1111101 contains 1101 and "11" is a proper sub-sequence of the sequence. Thus, the sequential machine must remember that the first two one's have occurred as it receives another symbol. Also, the sequence 1101101 contains 1101 as both an initial subsequence and a final subsequence with some overlap, i. e., 1101101 or 1101101. And, the 1 in the middle, 1101101, is in both subsequences.The sequence 1101 must be recognized each time it occurs in the input sequence.Example: Recognize 1101Define states for the sequence to be recognized:Assuming it starts with first symbol, Continues through each symbol in the sequence to be recognized, and Uses output 1 to mean the full sequence has occurred,With output 0 otherwise.Starting in the initial state (Arbitrarily named "A"):Add a state that recognizes the first "1."State "A" is the initial state, and state "B" is the state which represents the fact that the "first" one in the input subsequence has occurred. The output symbol "0" means that the full recognized sequence has not yet occurred.AB1/0After one more 1, we have:C is the state obtained when the input sequence has two "1"s.Finally, after 110 and a 1, we have:Transition arcs are used to denote the output function (Mealy Model)Output 1 on the arc from D means the sequence has been recognizedTo what state should the arc from state D go? Remember: 1101101 ?Note that D is the last state but the output 1 occurs for the input applied in D. This is the case when a Mealy model is assumed.Example: Recognize 1101 (continued)AB1/0AB1/0C1/00/0C1/0D1/1Example: Recognize 1101 (continued)Clearly the final 1 in the recognized sequence 1101 is a sub-sequence of 1101. It follows a 0 which is not a sub-sequence of 1101. Thus it should represent the same state reached from the initial state after a first 1 is observed. We obtain:AB1/0C1/00/01/1DAB1/0C1/00/0D1/1Example: Recognize 1101 (continued)The state have the following abstract meanings:A: No proper sub-sequence of the sequence has occurred.B: The sub-sequence 1 has occurred.C: The sub-sequence 11 has occurred.D: The sub-sequence 110 has occurred.The 1/1 on the arc from D to B means that the last 1 has occurred and thus, the sequence is recognized.1/1AB1/0C1/0D0/0Example: Recognize 1101 (continued)The other arcs are added to each state for inputs not yet listed. Which arcs are missing?Answer: "0" arc from A  "0" arc from B  "1" arc from C  "0" arc from D.1/1AB1/0C1/0D0/0Example: Recognize 1101 (continued)State transition arcs must represent the fact that an input subsequence has occurred. Thus we get:Note that the 1 arc from state C to state C implies that State C means two or more 1's have occurred.C1/1AB1/01/0D0/00/00/01/00/0Formulation: Find State Table From the State Diagram, we can fill in the State Table.There are 4 states, one input, and one output. We will choose the form with four rows, one for each current state.From State A, the 0 and 1 input transitions have been filled in along with the outputs.1/00/00/01/1AB1/0C1/0D0/00/0Present StateNext Statex=0 x=1Outputx=0 x=1 A B C D 1/0B00/0A0StatePresent Formulation: Find State TableFrom the state diagram, we complete the state table.What would the state diagram and state table look like for the Moore model?1/00/00/00/01/1AB1/0C1/0D0/0 Next Statex=0 x=1Outputx=0 x=1AA B 0 0 BA C0 0 CD C 0 0 DA B 0 1 Example: Moore Model for Sequence 1101For the Moore Model, outputs are associated with states.We need to add a state "E" with output value 1 for the final 1 in the recognized input sequence.This new state E, though similar to B, would generate an output of 1 and thus be different from B.The Moore model for a sequence recognizer usually has more states than the Mealy model.Example: Moore Model (continued)We mark outputs on states for Moore modelArcs now show only state transitionsAdd a new state E to produce the output 1Note that the new state, E produces the same behavior in the future as state B. But it gives a different output at the present time. Thus these states do represent a different abstraction of the input history.A/0B/0C/0D/00E/1000111110Example: Moore Model (continued)The state table is shown belowMemory aid: more state in the Moore model: “Moore is More.”A/0B/0C/0D/00E/1000111110 Present StateNext Statex=0 x=1Outputy A A B0BA C0CD C0DA E 0EA C1Counting Order Assignment: A = 0 0, B = 0 1, C =1 0, D = 1 1The resulting coded state table:State AssignmentPresent StateNext Statex = 0 x = 1Output x = 0 x = 10 00 00 1000 10 01 0001 01 11 0001 10 00 101Gray Code Assignment: A = 0 0, B = 0 1, C = 1 1, D = 1 0The resulting coded state table: State Assignment (continued)Present StateNext Statex = 0 x = 1Output x = 0 x = 10 00 00 1000 10 01 1001 11 01 1001 00 00 101Find Flip-Flop Input and Output Equations– Gray Code AssignmentAssume D flip-flops (two is needed for 4 states)Obtain K-maps for DA, DB, and Z:Circuit:ImplementationClockDDCRBZCRAXResetExample 2Problem: Design of a 3-bit CounterDesign a circuit that counts in binary form as follows 000, 001, 010, 111, 000, 001, Example 2 (cont.)Step1: State Diagram The outputs = the statesWhere is the input?What is the type of this sequential circuit?Example 2 (cont.)Step2: State TableNo need for state assignment hereExample 2 (cont.)Step2: State TableWe choose T-FFT–FF excitation tableExample 2 (cont.)Step3: State EquationsExample 2 (cont.)Step4: Draw CircuitTA0 = 1TA1 = A0TA2 = A1A0Sequential 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 designSummaryThanksAnalysis by signal tracingSequential DesignState ReductionDesign Examples