11Elec 326 Sequential Circuit DesignSequential Circuit Design ObjectivesThis section deals with the design of sequential circuits including the following: A discussion of the construction of state/output tables or diagrams from a word description or flow chart specification of sequential behavior A formal synthesis technique for realizing state tables and diagrams A less formal technique based on transition equationsReading AssignmentSections 3.3 and 3.4.2Elec 326 Sequential Circuit Design1. State Table/Diagram SpecificationThere is no algorithmic way to construct the state table from a word description of the circuit. Instead, we provide a few examples to illustrate the technique.It is convenient to group sequential circuits as to whether the  generate sequences,  detect sequences, or  transform sequences23Elec 326 Sequential Circuit DesignSequence Generation: Example: An up/down mod 6 counter: Six states and two inputs X & Y. The inputs have the following effect:XY = 00: Do nothing (no state changes)XY = 01: Count upXY = 11: Reset to state 0XY = 10: Count down00 01 11 100123450123450123450000000123454Elec 326 Sequential Circuit DesignExample: An arbitrary sequence generator0101234567QXQ*Y2Y1Y001234056700000000 0 00 1 00 1 10 1 01 0 01 0 01 1 01 0 035Elec 326 Sequential Circuit Design10Sequence detection Example: Detect an even number of 1s Example: Detect 0011010ODD0EVEN100000001000110ACC1ST000110REJ06Elec 326 Sequential Circuit Design Alternative Solution00110100110147Elec 326 Sequential Circuit Design Example: Universal length 4 sequence detectorThis one detects 1011 or 0101 or 0001 or 0111Sequence transformation Serial binary adder (arbitrary length operands)0100/001/110/101/010/011/111/000/18Elec 326 Sequential Circuit Design2. Formal Sequential Circuit SynthesisSummary of Design Steps  Assign state vectors to states; the state assignment problem Construct the transition table Pick a flip-flop type for each state variable and use the flip-flop’s application tables to construct an excitation table Derive excitation and output equations from the excitation table. Construct a logic diagram from the excitation and output equations.59Elec 326 Sequential Circuit DesignState Assignment Any assignment of ⎡log2n⎤ state variables will work, but different ones can give radically different circuits.Example: mod 6 counter0 1 25 4 411111100000010Elec 326 Sequential Circuit Design Number of possible state assignments:Assume we have k bits to encode n states (of course k ≥ ⎡log2n⎤ ). Then we have m = 2kpossible state vectors. The number of ways to pick n of the m state vectors to encode the states is given byGiven m state vectors, we can pick any one for the first state, any one of the remaining m-1 for the second state, etc. In general we can assign the m state vectors to states in m! ways. Therefore the number of different state assignments for encoding n states with m state vectors (where m = 2k) isFor n = 5 and m = 8 we have 6720 different possible state assignments.Trying all possible state assignments to find the best one is not an option.nm()=n! m!•(n-m)!n! m!•(n-m)!• m!611Elec 326 Sequential Circuit Design There is no known way to get the best assignment other than trying every possible one, which is not practical.Note that if we took this approach we would have to do a complete design for each assignment and compare all the resulting designs.  Guidelines for selecting good (but not necessarily optimal) state assignments:Choose 0…00 or 1…11 for the initial reset state.Minimize the number of state variables that change on each transition.Maximize the number of state variables that don’t change in a group of related states (a group in which most transitions stay in the group)Consider using more than the minimum number of state variables. E.g., one-hot assignments.12Elec 326 Sequential Circuit DesignConstruct the transition table from the state table or state graph and the chosen state assignment. Example 1. QABC0AAA1BCCY001XState TableQ*A - 00 B - 01 C - 10State AssignmentQ1Q000 01 10 11000 00 00 dd101 10 10 ddY001dXQ*1Q*2Transition Table713Elec 326 Sequential Circuit Design Example 2Q01234500 00000001 12345010 50123400 00000001 00000110 100000XYXYZQ*State Table0 - 000 1 - 001 2 - 010 3 - 011 4 - 100 5 - 101State AssignmentQ2Q1Q0000 001 010 011 100 101 110 11100 000 000 000 000 000 000 ddd ddd01 001 010 011 100 101 000 ddd ddd10 101 000 001 010 011 100 ddd ddd00 000000dd01 000001dd10 100000ddXYZXYQ*2Q*1Q*0Transition Table14Elec 326 Sequential Circuit DesignSelect the Flip-Flop Type The four main types of flip-flops are SR, D, T and JK.The choice of flip-flop type can affect the complexity of the combinational logic in the resulting sequential circuit.Of three common types, the most versatile is the JK, since it can be easily converted into the other two. z Any one can be converted into one of the other types, but some of these conversions take more logic than others.The T flip-flop is the one most suitable for counters, since it usually results in less logic than the other types.z This is because extra logic internal to the flip-flop is exactly what is needed to implement counters.D flip-flops are the ones found in almost all PLDs.z If your design is targeted for a PLD, you are usually stuck with D flip-flops.815Elec 326 Sequential Circuit DesignConstruct the Excitation Table Recall that the excitation table specifies the values for the flip-flop input signals needed to cause the transitions in the transition table. Flip-Flop Application TableThese tables list the flip-flop inputs signals needed for each possible transition of the flip-flop’s state. Use these flip-flop application tables to convert a transition table into an excitation table.D0101Q → Q* 0 → 0 0 → 1 1 → 0 1 → 1Q → Q* 0 → 0 0 → 1 1 → 0 1 → 1J K 0 d 1 d d 1 d 0Q → Q* 0 → 0 0 → 1 1 → 0 1 → 1S R 0 d 1 d d 1 d 0T0110Q → Q* 0 → 0 0 → 1 1 → 0 1 → 1D Flip-Flop SR Flip-Flop T Flip-Flop JK Flip-Flop16Elec 326 Sequential Circuit Design Example 1Chose JK flip-flops for both state variables to get the following:Note the rather high percentage of don’t care entries. This is common with JK flip-flops.Note that had we used D flip-flops the transition table and excitation