Charles Kime & Thomas Kaminski © 2008 Pearson Education, Inc. (Hyperlinks are active in View Show mode) Chapter 5 – Sequential Circuits Part 2 – Sequential Circuit Design Logic and Computer Design Fundamentals

Chapter 5 - Part 2 2 Overview Part 1 - Storage Elements and Sequential Circuit Analysis Part 2- Sequential Circuit Design Specification Formulation State Assignment Flip-Flop Input and Output Equation Determination Verification

Chapter 5 - Part 2 3 The Design Procedure Specification Formulation - Obtain a state diagram or state table State Assignment - Assign binary codes to the states Flip-Flop Input Equation Determination - Select flip-flop types and derive flip-flop equations from next state entries in the table Output Equation Determination - Derive output equations from output entries in the table Optimization - Optimize the equations Technology Mapping - Find circuit from equations and map to flip-flops and gate technology Verification - Verify correctness of final design

Chapter 5 - Part 2 4 How may assignments of codes with a minimum number of bits? Two – A = 0, B = 1 or A = 1, B = 0 Does it make a difference? Only in variable inversion, so small, if any. State Assignment – Example 1

Chapter 5 - Part 2 5 How may assignments of codes with a minimum number of bits? = 24 Does code assignment make a difference in cost? State Assignment – Example 2

Chapter 5 - Part 2 6 Counting Order Assignment: A = 0 0, B = 0 1, C = 1 0, D = 1 1 The resulting coded state table: State Assignment – Example 2 (continued) Present State Next State x = 0 x = 1 Output x = 0 x =

Chapter 5 - Part 2 7 Gray Code Assignment: A = 0 0, B = 0 1, C = 1 1, D = 1 0 The resulting coded state table: State Assignment – Example 2 (continued) Present State Next State x = 0 x = 1 Output x = 0 x =

Chapter 5 - Part 2 8 Find Flip-Flop Input and Output Equations: Example 2 – Counting Order Assignment Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X D1D1 D2D2 Z Assume D flip-flops Interchange the bottom two rows of the state table, to obtain K-maps for D 1, D 2, and Z:

Chapter 5 - Part 2 9 Optimization: Example 2: Counting Order Assignment Performing two-level optimization: D 1 = Y 1 Y 2 + XY 1 Y 2 D 2 = XY 1 Y 2 + XY 1 Y 2 + XY 1 Y 2 Z = XY 1 Y 2 Gate Input Cost = 22 Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X D1D1 D2D2 Z

Chapter 5 - Part 2 10 Find Flip-Flop Input and Output Equations: Example 2 – Gray Code Assignment Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X Assume D flip-flops Obtain K-maps for D 1, D 2, and Z: D1D1 D2D2 Z

Chapter 5 - Part 2 11 Optimization: Example 2: Assignment 2 Performing two-level optimization: D 1 = Y 1 Y 2 + XY 2 Gate Input Cost = 9 D 2 = X Select this state assignment to Z = XY 1 Y 2 complete design in slide Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X Y2Y2 Y1Y1 X D1D1 D2D2 Z

Chapter 5 - Part 2 12 One Flip-flop per State (One-Hot) Assignment Example codes for four states: (Y 3, Y 2, Y 1, Y 0 ) = 0001, 0010, 0100, and In equations, need to include only the variable that is 1 for the state, e. g., state with code 0001, is represented in equations by Y 0 instead of Y 3 Y 2 Y 1 Y 0 because all codes with 0 or two or more 1s have dont care next state values. Provides simplified analysis and design Combinational logic may be simpler, but flip- flop cost higher – may or may not be lower cost

Chapter 5 - Part 2 13 One-Hot Assignment : A = 0001, B = 0010, C = 0100, D = 1000 The resulting coded state table: State Assignment – Example 2 (continued) Present State Next State x = 0 x = 1 Output x = 0 x =

Chapter 5 - Part 2 14 Optimization: Example 2: One Hot Assignment Equations read from 1 next state variable entries in table: D 0 = X(Y 0 + Y 1 + Y 3 ) or X Y 2 D 1 = X(Y 0 + Y 3 ) D 2 = X(Y 1 + Y 2 ) or X(Y 0 + Y 3 ) D 3 = X Y 2 Z = XY 3 Gate Input Cost = 15 Combinational cost intermediate plus cost of two more flip-flops needed.

Chapter 5 - Part 2 15 Library: D Flip-flops with Reset (not inverted) NAND gates with up to 4 inputs and inverters Initial Circuit: Map Technology Clock D D C R Y2Y2 Z C R Y1Y1 X Reset

Chapter 5 - Part 2 16 Mapped Circuit - Final Result Clock D D C R Y2Y2 Z C R Y1Y1 X Reset

Chapter 5 - Part 2 17 Sequential Design: Example Design a sequential modulo 3 accumulator for 2- bit operands Definitions: Modulo n adder - an adder that gives the result of the addition as the remainder of the sum divided by n Example: modulo 3 = remainder of 4/3 = 1 Accumulator - a circuit that accumulates the sum of its input operands over time - it adds each input operand to the stored sum, which is initially 0. Stored sum: (Y 1,Y 0 ), Input: (X 1,X 0 ), Output: (Z 1,Z 0 )

Chapter 5 - Part 2 18 Example (continued) Complete the state table State Assignment: (Y 1,Y 0 ) = (Z 1,Z 0 ) Codes are in gray code order to ease use of K-maps in the next step Z1Z0Z1Z0 Y 1 (t+1), Y 0 (t+1) A (00)0001X1000 B (01)0110X (11)XXXX11 C (10)1000X0110 X1X0X1X0 Y1Y0Y1Y0

Chapter 5 - Part 2 19 Example (continued) Complete the state diagram: B/01 C/10 A/ Reset

Chapter 5 - Part 2 20 Example (continued) Find optimized flip-flop input equations for D flip-flops D 1 = D 0 = D0D0 D1D1 Y0Y0 Y1Y1 X1X1 X0X0 Y0Y0 Y1Y1 X1X1 X X0X0 X X X X X X X X X X X X X

Chapter 5 - Part 2 21 Circuit - Final Result with AND, OR, NOT Clock D C R Y0Y0 D C R Y1Y1 X1X1 Reset Z1Z1 X0X0 Z0Z0

Chapter 5 - Part 2 22 Other Flip-Flop Types J-K and T flip-flops Behavior Implementation Basic descriptors for understanding and using different flip-flop types Characteristic tables Characteristic equations Excitation tables For actual use, see Reading Supplement - Design and Analysis Using J-K and T Flip-Flops

Chapter 5 - Part 2 23 J-K Flip-flop Behavior Same as S-R flip-flop with J analogous to S and K analogous to R Except that J = K = 1 is allowed, and For J = K = 1, the flip-flop changes to the opposite state As a master-slave, has same 1s catching behavior as S-R flip-flop If the master changes to the wrong state, that state will be passed to the slave E.g., if master falsely set by J = 1, K = 1 cannot reset it during the current clock cycle

Chapter 5 - Part 2 24 J-K Flip-flop (continued) Implementation To avoid 1s catching behavior, one solution used is to use an edge-triggered D as the core of the flip-flop Symbol D C K J J C K

Chapter 5 - Part 2 25 T Flip-flop Behavior Has a single input T For T = 0, no change to state For T = 1, changes to opposite state Same as a J-K flip-flop with J = K = T As a master-slave, has same 1s catching behavior as J-K flip-flop Cannot be initialized to a known state using the T input Reset (asynchronous or synchronous) essential

Chapter 5 - Part 2 26 T Flip-flop (continued) Implementation To avoid 1s catching behavior, one solution used is to use an edge-triggered D as the core of the flip-flop Symbol C D T T C

Chapter 5 - Part 2 27 Basic Flip-Flop Descriptors Used in analysis Characteristic table - defines the next state of the flip-flop in terms of flip-flop inputs and current state Characteristic equation - defines the next state of the flip-flop as a Boolean function of the flip-flop inputs and the current state Used in design Excitation table - defines the flip-flop input variable values as function of the current state and next state

Chapter 5 - Part 2 28 D Flip-Flop Descriptors Characteristic Table Characteristic Equation Q(t+1) = D Excitation Table D 0 1 Operation Reset Set 0 1 Q(t1) + Q(t+1) D Operation Reset Set

Chapter 5 - Part 2 29 T Flip-Flop Descriptors Characteristic Table Characteristic Equation Q(t+1) = T Q Excitation Table No change Complement Operation 0 1 TQ(t1) Q(t) Q(t) + Q(t + 1) Q(t) 1 0 T No change Complement Operation Q(t)

Chapter 5 - Part 2 30 S-R Flip-Flop Descriptors Characteristic Table Characteristic Equation Q(t+1) = S + R Q, S. R = 0 Excitation Table OperationS R No change Reset Set Undefined 0 1 ? Q(t+1) Q(t) Operation No change Set Reset No change S X Q(t+ 1) Q(t) R X 0 1 0

Chapter 5 - Part 2 31 J-K Flip-Flop Descriptors Characteristic Table Characteristic Equation Q(t+1) = J Q + K Q Excitation Table No change Set Reset Complement OperationJ K 0 1 Q(t +1) Q(t) Q(t) Q(t + 1) Q(t) Operation X X 0 1 K 0 1 X X J No change Set Reset No Change

Chapter 5 - Part 2 32 Flip-flop Behavior Example Use the characteristic tables to find the output waveforms for the flip-flops shown: T C Clock D,T QDQD QTQT D C

Chapter 5 - Part 2 33 Flip-Flop Behavior Example (continued) Use the characteristic tables to find the output waveforms for the flip-flops shown: J C K S C R Clock S,J Q SR Q JK R,K ?