Figure 7-34 showed how to build a. T. flip-flop with enable using a. D Show how to build a flip-flop equivalent to the 74×109 positive-edge-triggered. J-K …

646

Chapter 7

Sequential Logic Design Principles

F i g u re X 7 2

F i g u re X 7 3

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
Drill Problems
71 72
S R

Many CAD environments for digital design include a graphical statediagram entry tool Unfortunately, these typically support only traditional state diagrams, making it very easy for a designer to create an ambiguous description of next-state behavior As a result, my personal recommendation is that you stay away from state-diagram editors and instead use an HDL to describe your state machines We mentioned the importance of synchronizing sequences in connection with state-machine test vectors Theres actually a very well developed but almost forgotten theory and practice of synchronizing sequences and somewhat less powerful homing experiments, described by Frederick C Hennie in Finite-State Models for Logical Machines Wiley, 1968 Unless youve got this old classic on your bookshelf and know how to apply its teachings, please just remember to provide a reset input in every state machine that you design

Give three examples of metastability that occur in everyday life,
other than ones discussed in this chapter Sketch the outputs of an S-R latch of the type shown in Figure 7-5 for the input waveforms shown in Figure X72 Assume that input and output rise and fall times are zero, that the propagation delay of a NOR gate is 10 ns, and that each time division below is 10 ns

Repeat Drill 72 using the input waveforms shown in Figure X73 Although you may find the result unbelievable, this behavior can actually occur in real devices whose transition times are short compared to their propagation delay

Figure 7-34 showed how to build a T flip-flop with enable using a D flip-flop and combinational logic Show how to build a D flip-flop using a T flip-flop with enable and combinational logic Show how to build a J-K flip-flop using a T flip-flop with enable and combinational logic

Copying Prohibited

Drill Problems

647

76 77

710 Repeat Drill 79, swapping AND and OR gates in the logic diagram Is the new state/output table the dual of the original one? Explain 711 Draw a state diagram for the state machine described by Table 7-6 712 Draw a state diagram for the state machine described by Table
7-12 713 Draw a state diagram for the state machine described by Table 7-14 714 Construct a state and output table equivalent to the state diagram in Figure X714 Note that the diagram is drawn with the convention that the state does not change except for input conditions that are explicitly shown
A X B
Z1 Z2 11 Z1 Z2 10

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
Show how to build an S-R latch using a single 74×74 positive-edge-triggered D flip-flop and no other components Show how to build a flip-flop equivalent to the 74×109 positive-edge-triggered J-K flip-flop using a 74×74 positive-edge-triggered D flip-flop and one or more gates from a 74×00 package Show how to build a flip-flop equivalent to the 74×74 positive-edge-triggered D flip-flop using a 74×109 positive-edge-triggered J-K flip-flop and no other components Analyze the clocked synchronous state machine in Figure X79 Write excitation equations, excitation/transition table, and state/output table use state names AD for Q1 Q2 0011
X Z
D

Q Q

CLK

Figure X79

CLK

Figure X714

X Y

Z1 Z2 01

Z1 Z2 00

Z1
Z2 10

Z1 Z2 11

X Y

Z1 Z2 00

Z1 Z2 01

Copying Prohibited

648

Chapter 7

Sequential Logic Design Principles

F i g u re X 7 15

F i g u re X 7 16

F i g u re X 7 17

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
D Q D Q D Q CLK CLK CLK

715 Analyze the clocked synchronous state machine in Figure X715 Write excitation equations, excitation/transition table, and state table use state names AH for Q2 Q1 Q0 000111
Q2 Q1

CLK

716 Analyze the clocked synchronous state machine in Figure X716 Write excitation equations, excitation/transition table, and state/output table use state names AH for Q1 Q2 Q3 000111
Q1 Q2

Y X

Q Q

CLK

717 Analyze the clocked synchronous state machine in Figure X717 Write excitation equations, transition equations, transition table, and state/output table use state names AD for Q1 Q2 0011 Draw a state diagram, and draw a timing diagram for CLK, X, Q1, and Q2 for 10 clock ticks, assuming that the machine starts in state 00 and X is continuously 1
Q1

Q Q

CLK

718
Analyze the clocked synchronous state machine in Figure X718 Write excitation equations, transition equations, transition table, and state/output table use state names AD for Q1 Q0 0011 Draw a state diagram, and draw a timing diagram for CLK, EN, Q1, and Q0 for 10 clock ticks, assuming that the machine starts in state 00 and EN is continuously 1 Copying Prohibited

Drill Problems

649

719 Analyze the clocked synchronous state machine in Figure X719 Write excitation equations, excitation/transition table, and state/output table use state names AD for Q1 Q2 0011
X

CLK

720 All of the state diagrams in Figure X720 are ambiguous List all of the ambiguities in these state diagrams Hint: Use Karnaugh maps where necessary to find uncovered and double-covered input combinations
b W X W

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
EN MAX
J Q Q

JK1

Q Q

CLK

Figure X718

Figure X719

EN T

Q Q

EN T

Q Q

Figure X720

X Z

X Y

X Y Z

W Y
Z

X Y

X Z

W X Y

W X Z

X Y

Copying Prohibited

650

Chapter 7

Sequential Logic Design Principles

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
Exercises
F i g u re X 7 2 7
D C Q QN

721 Synthesize a circuit for the state diagram of Figure 7-64 using six variables to encode the state, where the LALC and RARC outputs equal the state variables themselves Write a transition list, a transition equation for each state variable as a sum of p-terms, and simplified transition/excitation equations for a realization using D flip-flops Draw a circuit diagram using SSI and MSI components 722 Starting with the transition list in Table 7-18, find a minimal sum-of-products expression for Q2, assuming that the next states for the unused states are true dont-cares 723 Modify the state diagram of Figure 7-64 so that the machine goes into hazard mode immediately if LEFT and RIGHT are asserted simultaneously during a turn Write the corresponding transition list

724 Explain how metastability occurs in a D latch when the setup and hold times are not met,
analyzing the behavior of the feedback loop inside the latch 725 What is the minimum setup time of a pulse-triggered flip-flop such as a master/ slave J-K or S-R flip-flop? Hint: It depends on certain characteristics of the clock 726 Describe a situation, other than the metastable state, in which the Q and QN outputs of a 74×74 edge-triggered D flip-flop may be noncomplementary for an arbitrarily long time 727 Compare the circuit in Figure X727 with the D latch in Figure 7-12 Prove that the circuits function identically In what way is Figure X727, which is used in some commercial D latches, better?

728 Suppose that a clocked synchronous state machine with the structure of Figure 7-35 is designed using D latches with active-high C inputs as storage elements For proper next-state operation, what relationships must be satisfied among the following timing parameters? tFmin, tFmax tCQmin, tCQmax tDQmin, tDQmax tsetup, thold tH, tL Minimum and maximum propagation delay of the next-state logic Minimum and maximum clock-to-output delay of a D latch Minimum and maximum data-to-output delay of a D latch Setup and hold times of a D latch Clock HIGH and LOW times

729 Redesign the state
machine in Drill 79 using just three inverting gates–NAND or NOR–and no inverters Copyright 1999 by John F Wakerly Copying Prohibited

Exercises

651

730 Draw a state diagram for a clocked synchronous state machine with two inputs, INIT and X, and one Moore-type output Z As long as INIT is asserted, Z is continuously 0 Once INIT is negated, Z should remain 0 until X has been 0 for two successive ticks and 1 for two successive ticks, regardless of the order of occurrence Then Z should go to 1 and remain 1 until INIT is asserted again Your state diagram should be neatly drawn and planar no crossed lines Hint: No more than ten states are required 731 Repeat Exercise 730, but write the state diagram in ABEL 732 Design a clocked synchronous state machine that checks a serial data line for even parity The circuit should have two inputs, SYNC and DATA, in addition to CLOCK, and one Moore-type output, ERROR Devise a state/output table that does the job using just four states and include a description of each states meaning in the table Choose a 2-bit state assignment, write transition and excitation equations, and draw the logic diagram Your circuit may use D flip-flops, J-K flipflops,
or one of each 733 Repeat Exercise 732, but do the design using ABEL and a GAL16V8 PLD 734 Design a clocked synchronous state machine with the state/output table shown in Table X734, using D flip-flops Use two state variables, Q1 Q2, with the state assignment A 00, B 01, C 11, D 10
X

735 Repeat Exercise 734 using J-K flip-flops 736 Write a new transition table and derive minimal-cost excitation and output equations for the state table in Table 7-6 using the simplest state assignment in Table 7-7 and D flip-flops Compare the cost of your excitation and output logic when realized with a two-level AND-OR circuit with the circuit in Figure 7-54 737 Repeat Exercise 736 using the almost one-hot state assignment in Table 7-7 738 Suppose that the state machine in Figure 7-54 is to be built using 74LS74 D flipflops What signals should be applied to the flip-flop preset and clear inputs? 739 Write new transition and excitation tables and derive minimal-cost excitation and output equations for the state table in Table 7-6 using the simplest state assignment in Table 7-7 and J-K flip-flops Compare the cost of your excitation and output logic when realized with a two-level AND-OR circuit
with the circuit in Figure 7-56 740 Repeat Exercise 739 using the almost one-hot state assignment in Table 7-7

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
Ta bl e X 7 3 4
S B

D B A

0 0 1 0

C B B

C D

Copying Prohibited

652

Chapter 7

Sequential Logic Design Principles

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
Copyright 1999 by John F Wakerly

741 Construct an application table similar to Table 7-10 for each of the following flipflop types: a S-R; b T with enable; c D with enable Discuss the unique problem that you encounter when trying to make the most efficient use of dontcares with one of these flip-flops 742 Construct a new excitation table and derive minimal-cost excitation and output equations for the state machine of Table 7-8 using T flip-flops with enable inputs Figure 7-33 Compare the cost of your excitation and output logic when realized with a two-level AND-OR circuit with the circuit in Figure 7-54 743 Determine the full 8-state table of the circuit in Figure 7-54 Use the names
U1, U2, and U3 for the unused states 001, 010, and 011 Draw a state diagram and explain the behavior of the unused states 744 Repeat Exercise 743 for the circuit of Figure 7-56 745 Write a transition table for the nonminimal state table in Figure 7-51a that results from assigning the states in binary counting order, INITOKA1 000110 Write corresponding excitation equations for D flip-flops, assuming a minimalcost disposition of the unused state 111 Compare the cost of your equations with the minimal-cost equations for the minimal state table presented in the text 746 Write the application table for a T flip-flop with enable 747 In many applications, the outputs produced by a state machine during or shortly after reset are irrelevant, as long as the machine begins to behave correctly a short time after the reset signal is removed If this idea is applied to Table 7-6, the INIT state can be removed and only two state variables are needed to code the remaining four states Redesign the state machine using this idea Write a new state table, transition table, excitation table for D flip-flops, minimal-cost excitation and output equations, and logic diagram Compare the cost of the new
circuit with that of Figure 7-54 748 Repeat Exercise 747 using J-K flip-flops, and use Figure 7-56 to compare cost 749 Redesign the 1s-counting machine of Table 7-12, assigning the states in binary counting order S0S3 00, 01, 10, 11 Compare the cost of the resulting sumof-products excitation equations with the ones derived in the text 750 Repeat Exercise 749 using J-K flip-flops 751 Repeat Exercise 749 using T flip-flops with enable 752 Redesign the 1s-counting machine of Table 7-12 as an ABEL state diagram Try to find a state assignment that minimizes the total number of product terms, assuming that you can use either polarity of output equations How many different state assignments must you examine? 753 Redesign the combination-lock machine of Table 7-14, assigning coded states in Gray-code order AH 000, 001, 011, 010, 110, 111, 101, 100 Compare the cost of the resulting sum-of-products excitation equations with the ones derived in the text 754 Find a 3-bit state assignment for the combination-lock machine of Table 7-14 that results in less costly excitation equations than the ones derived in the text Hint: Use the fact that inputs 13 are the same as inputs 46 in the required
input sequence Copying Prohibited

Exercises
n flip-flops

653

CLOCK

755 What changes would be made to the excitation and output equations for the combination-lock machine in Section 746 as the result of performing a formal multiple-output minimization procedure Section 438 on the five functions? You need not construct 31 product maps and go through the whole procedure; you should be able to eyeball the excitation and output maps in Section 746 to see what savings are possible 756 The output of a finite-memory machine is completely determined by its current input and its inputs and outputs during the previous n clock ticks, where n is a finite, bounded integer Any machine that can be realized as shown in Figure X756 is a finite-memory machine Note that a finite-state machine need not be a finite-memory machine; for example, a modulo-n counter with an enable input and a MAX output has only n states, but its output may depend on the value of the enable input at every clock tick since initialization Show how to realize the combination-lock machine of Table 7-14 as a finite-memory machine 757 Synthesize a circuit for the ambiguous state diagram in Figure 7-62 Use the state assignment
in Table 7-16 Write a transition list, a transition equation for each state variable as a sum of p-terms, and simplified transition/excitation equations for a realization using D flip-flops Determine the actual next state of the circuit, starting from the IDLE state, for each of the following input combinations on LEFT, RIGHT, HAZ: 1,0,1, 0,1,1, 1,1,0, 1,1,1 Comment on the machines behavior in these cases 758 Suppose that for a state SA and an input combination I, an ambiguous state diagram indicates that there are two next states, SB and SC The actual next state SD for this transition depends on the state machines realization If the state machine is synthesized using the method V p-terms where V 1 to obtain transition/excitation equations for D flip-flops, what is the relationship between the coded states for SB, SC, and SD? Explain Copyright 1999 by John F Wakerly

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
IN
D Q D Q D Q CK CK CK

combinational logic

OUT

Figure X756

n flip-flops

finite-memory machine

Copying Prohibited

654

Chapter 7

Sequential Logic Design Principles

BUT
flop NBUT gate

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
X1 X2 Q1 Q2 X1 X2 Q1 Q2

759 Repeat Exercise 758, assuming that the machine is synthesized using the method V p-terms where V 0 760 Suppose that for a state SA and an input combination I, an ambiguous state diagram does not define a next state The actual next state SD for this transition depends on the state machines realization Suppose that the state machine is synthesized using the method V p-terms where V 1 to obtain transition/ excitation equations for D flip-flops What coded state is SD? Explain 761 Repeat Exercise 760, assuming that the machine is synthesized using the method V p-terms where V 0 762 Given the transition equations for a clocked synchronous state machine that is to be built using master/slave S-R flip-flops, how can the excitation equations for the S and R inputs be derived? Hint: Show that any transition equation, Qi expr, can be written in the form Qi Qi expr1 Qi expr2, and see where that leads 763 Repeat Exercise 762 for J-K flip-flops How can the dont-cares that are possible in a J-K design be specified? 764 Draw a logic
diagram for the output logic of the guessing-game machine in Table 7-18 using a single 74×139 dual 2-to-4 decoder Hint: Use active-low outputs 765 What does the personalized license plate in Figure 7-60 stand for? Hint: Its the authors old plate, a computer engineers version of OTTFFSS 766 Analyze the feedback sequential circuit in Figure 7-19, assuming that the PR_L and CLR_L inputs are always 1 Derive excitation equations, construct a transition table, and analyze the transition table for critical and noncritical races Name the states, and write a state/output table and a flow/output table Show that the flow table performs the same function as Figure 7-85 767 Draw the logic diagram for a circuit that has one feedback loop but is not a sequential circuit That is, the circuits output should be a function of its current input only In order to prove your case, break the loop and analyze the circuit as if it were a feedback sequential circuit, and demonstrate that the outputs for each input combination do not depend on the state 768 A BUT flop may be constructed from an NBUT gate as shown in Figure X768 An NBUT gate is simply a BUT gate with inverted outputs; see Exercise 531 for the
definition of a BUT gate Analyze the BUT flop as a feedback sequential circuit and obtain excitation equations, transition table, and flow table Is this circuit good for anything, or is it a flop? 769 Repeat Exercise 768 for the BUT flop in Figure X769

Figure X768

Figure X769

Copying Prohibited

Exercises

655

770 A clever student designed the circuit in Figure X770 to create a BUT gate But the circuit didnt always work correctly Analyze the circuit and explain why 771 Analyze the feedback sequential circuit in Figure X771 Break the feedback loops, write excitation equations, and construct a transition and output table, showing the stable total states What application might this circuit have?

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
74×139
1

1G 1A 1B

A1 B1

2 3

1Y0 1Y1 1Y2 1Y3

4 5 6 7

74×04

Figure X770

2Y0 2Y1 2Y2 2Y3

11 10 9

A2 B2

2A 13 2B

74×04

F i g u re X 7 7 1

Copying Prohibited

656

Chapter 7

Sequential Logic Design Principles

DO NOT COPY DO NOT COPY DO NOT
COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
Q forcing term holding term Q

772 Show that a 4-bit ones-complement adder with end-around carry is a feedback sequential circuit 773 Complete the analysis of the positive-edge-triggered D flip-flop in Figure 7-86, including transition/output, state/output, and flow/output tables Show that its behavior is equivalent to that of the D flip-flop in Figure 7-78 774 We claimed in Section 7101 that all single-loop feedback sequential circuits have an excitation equation of the form

775

776

777 778 779

780

Why arent there any practical circuits whose excitation equation substitutes Q for Q above? Simulate the latch circuit of Figure 7-88b under the conditions described in the text on page 616, either using a simulator in unit-delay mode or by hand assuming that each gate has a delay of 1 ns Does the circuit behave as claimed in the text? Replace the inverter in the circuit with three inverters, repeat the simulation, and explain the results What would you expect to happen in the real circuit? Design a latch with two control inputs, C1 and C2, and three data inputs, D1, D2, and D3 The latch is to be open
only if both control inputs are 1, and it is to store a 1 if any of the data inputs is 1 Use hazard-free two-level sum-of-products circuits for the excitation functions Repeat Exercise 776, but minimize the number of gates required; the excitation circuits may have multiple levels of logic Redraw the timing diagram in Figure 7-90, showing the internal state variables of the pulse-catching circuit of Figure 7-100, assuming that it starts in state 00 The general solution for obtaining a race-free state assignment of 2 n states using 2n-1 state variables yields the adjacency diagram shown in Figure X779 for the n 2 case Compare this diagram with Figure 7-97 Which is better, and why? Design a fundamental-mode flow table for a pulse-catching circuit similar to the one described in Section 7102, except that the circuit should detect both 0-to-1 and 1-to-0 transitions on P

C2 110

D2 111

F i g u re X 7 7 9

B1 010

B2 011

A1 000

A2 001

C1 100

D1 101

Copying Prohibited

Exercises

657

781 Design a fundamental-mode flow table for a double-edge-triggered D flip-flop, one that samples its inputs and changes its outputs on both edges of the clock
signal 782 Design a fundamental-mode flow table for a circuit with two inputs, EN and CLKIN, and a single output, CLKOUT, with the following behavior A clock period is defined to be the interval between successive rising edges of CLKIN If EN is asserted during an entire given clock period, then CLKOUT should be on during the next clock period; that is, it should be identical to CLKIN If EN is negated during an entire given clock period, then CLKOUT should be off constant 1 during the next clock period If EN is both asserted and negated during a given clock period, then CLKOUT should be on in the next period if it had been off, and off if it had been on After writing the fundamental-mode flow table, reduce it by combining compatible states if possible 783 Design a circuit that meets the specifications of Exercise 782 using edgetriggered D flip-flops 74×74 or J-K flip-flops 74×109 and NAND and NOR gates without feedback loops Give a complete circuit diagram and word description of how your circuit achieves the desired behavior 784 Which of the circuits of the two preceding exercises is are subject to metastability, and under what conditions? 785 For the flow table in Table X785, find
an assignment of state variables that avoids all critical races You may add additional states as necessary, but use as few state variables as possible Assign the all-0s combination to state A Draw an adjacency diagram for the original flow table, and write the modified flow table and another adjacency diagram to support your final state-variable assignment 786 Prove that the fundamental-mode flow table of any flip-flop that samples inputs and changes outputs on the rising edge only of a clock signal CLK contains an essential hazard

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
XY

00
B B F

01
C E

10
A B

Tab l e X 7 8 5

A B

C D E F

C F

D F

E F

Copying Prohibited

658

Chapter 7

Sequential Logic Design Principles

DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY DO NOT COPY
Copyright 1999 by John F Wakerly

787 Locate the essential hazards in the flow table for a positive-edge-triggered D flip-flop, Figure 7-85 788 Identify the essential hazards, if any, in the flow table developed in Exercise
781 789 Identify the essential hazards, if any, in the flow table developed in Exercise 782 790 Build a verbal flip-flop–a logical word puzzle that can be answered correctly in either of two ways depending on state How might such a device be adapted to the political arena? 791 Modify the ABEL program in Table 7-27 to use an output-coded state assignment, thereby reducing the total number of PLD outputs required by one 792 Finish writing the test vectors, started in Table 7-35, for the combination-lock state machine of Table 7-31 The complete set of vectors should test all of the state transitions and all of the output values for every state and input combination

Copying Prohibited

Source:ddpp.com