Fundamentals of Digital Design -- DESIGN METHODS (part 2)

AMAZON multi-meters discounts AMAZON oscilloscope discounts

<<PREV.

The One-Hot Method of ASM Synthesis

In this method of generating states, we use one D flip-flop for each state. There is no encoding of the states, so there is no need to specify a state assignment as we did in the previous methods. Since we must always be in only one state at a time, we must arrange for only one of the state flip-flops to be true during each state time. Therefore, we must compute with combinational logic the value Tor F of each flip-flop's input to provide the one true input required to produce the next state of the system. This property of exactly one flip-flop being true at a time gives the method its name, "one-hot."

We may make exactly one flip-flop true with the aid of a tabular presentation slightly different from the one used in the multiplexer method. Consider the one-hot implementation of the ASM in FIG. 13. For this four-state system, we need four D flip-flops labeled with the states' names. TABLE 3 contains the information needed to produce the inputs to the one-hot flip-flops.

TABLE 3. STATE TRANSITION DATA FOR A ONE-HOT IMPLEMENTATION OF THE ASM IN FIG. 13

The equations for the flip-flop inputs follow from the table:

NEXT.STATE.P = P(D) = Q·W + R + s·z·x

NEXT.STATE.Q = Q(D) = p·x·y

NEXT.STATE.R = R(D) = p·x·y + Q·W + s·x·z

NEXT.STATE.S = SeD) = p·x + s·z

FIG. 15 is an implementation of this controller, assuming that the status inputs W, X, Y, and Z are available in both voltage forms. For the ASM outputs, we may generate Eqs. (5-3) through (5-6) directly, since the logic variables P, Q, and S are available from the one-hot flip-flops.

FIG. 15. A one-hot controller for the ASM in FIG. 13.

Initializing the one-hot controller. The first two methods of generating states require an encoded representation of the present state; the code inherently specifies only one state at a time. In the one-hot method, we must take care to initialize the system in such a way that exactly one flip-flop-representing the starting state-is true and the rest false. Once started, the one-hot controller will propagate from state to state in the proper manner. We can envision any one-hot circuit with a master reset signal built into its design to provide for initializing the state generator. (You will see that virtually all designs should have such a reset facility; resetting is the only routine use of an asynchronous input to our systems.) The implementation of the state flip-flops will usually contain a set of D register chips having a common asynchronous clear input. In our example, we use a 74LS175 Quad D Register to provide the four flip-flops needed for state storage. Asserting the asynchronous "clear" input on this chip will clear the Q outputs to low voltages. We may use our mixed-logic notation to good advantage here, to provide for initializing exactly one flip-flop to true. In FIG. 15, we have assumed that state P is the desired starting state. Note how a master reset signal "clears" the P flip-flop to true and the Q, R, and S flip-flops to false.

This is a routine application of mixed logic; the diagram shows exactly what is happening.

Comments. The one-hot method has the advantages of ease of design and clarity of circuit. The inputs to the state flip-flops directly describe the conditions under which each state is the next state. As you know, the mixed logic notation provides for ease of analysis of circuits, so we may read off the next-state conditions from the circuit diagram. The size of the state generator circuit does not grow rapidly with the number of states. At first you may be horrified at the idea of using a flip-flop for each state instead of the more compact encoded scheme used in the other methods. However, the packaging of MSI integrated circuits gives us four, six, or eight D flip-flops on a chip, so the package count stays low. In medium-size to large designs, the one-hot method compares favorably in total package count with the other methods and usually wins the count.

The main disadvantage of the one-hot method is the need to take great care to initialize the system to a starting state. Also, if the hardware (or the design, heaven forbid!) is faulty, more than one state flip-flop may be true at once. This situation is difficult to debug because the system follows several ASM paths at the same time.

Our preference is to use the multiplexer controller method in systems of up to 16 states and the one-hot method for larger hardwired systems. You will see in Part III that as the systems become complex, involving many states, we shift gears and adopt the method of microprogramming for designing systems rather than using hardwired controllers.

Occasionally, an ASM of a special form will suggest a special type of state generator. For example, a cyclic ASM offers the opportunity to use a binary counter as its state generator. This special form appears in several of the examples in Section 6.

The ROM-Based Method of ASM Synthesis

Our fourth method for synthesizing ASMs is based on table-lookup from a permanent memory such as a ROM, PROM, or EPROM. This method has the advantage that it is highly regular in its approach, but it suffers from a serious explosion in the size of the ROM as the ASMs become more complex. In this method, we use the now-familiar encoded state generator shown in FIG. 10.

The combinational logic box, which produces the next-state address and the ASM outputs, consists of a ROM of suitable size. The inputs to the combinational logic box form the address of the ROM, and the outputs are the outputs of the ROM. To realize an ASM, we must choose a suitable ROM and specify its contents.

TABLE 4. STATE GENERATOR AND OUTPUTS FOR THE ASM OF FIG. 9, USING A ROM

We will illustrate the method by implementing the ASM in FIG. 9. The ROM will have three address inputs-B, A, and Z-so we will need an 8-word ROM. We require 4 bits of output-B(D), A(D), CMD1, and CMD2-so an 8 word x 4-bit ROM is appropriate. The contents of the ROM are listed in TABLE 4, and FIG. 16 is the implementation.

FIG. 16. Implementation of the ASM in FIG. 9, using a ROM.

The synthesis of an ASM using a ROM appears straightforward, systematic, and elegant. There is a problem, however. As the complexity of the ASM grows, the size (number of words) of the ROM increases quickly. The state variables do not present a problem, since their number increases only logarithmically with the number of ASM states, and the ROM's size therefore increases only linearly with the number of ASM states. But the ROM address must contain a bit for each test input in the design, and thus the ROM's size increases exponentially with the number of test inputs. The ASM in FIG. 12, with four states and four distinct test inputs, would require a ROM with 8 address inputs, having 64 words. Complex ASMs with lots of test inputs can require huge ROMs with this method.

Another mildly unpleasant characteristic of the ROM-based method for synthesizing an ASM is the enormous redundancy of information. Since the ROM address is fully decoded, the ROM contains a word for each possible combination of address bits. Each test input tends to be used only in a few states, yet the ROM must contain a word for every combination of all test inputs and state variables. For small systems, this method can be effective; large systems will usually require computer software support to generate the ROM's contents. To sum up: the ROM-based method is attractive because of its regularity, but its use is limited by the exponential growth of the ROM's size as the number of test inputs to the ASM increases.

FIG. 17. A model of a digital system for studying clock skew.

DESIGN PITFALLS

In our study of design, we have made several important assumptions about our systems.

(a) We have assumed that our ASMs are synchronous, with changes in state and other actions governed by a master clock.

(b) We have assumed that at the time of a state change, all inputs to the ASM are stable; in other words, inputs change synchronously with the system clock.

Let's investigate the effect of violating these conditions. Conditions (a) and (b) are design decisions of great importance, violation of which will lead to serious problems. Condition (c) is a subtle matter that we enforce by good construction practices. Let's consider (c) first.

Clock Skew

In a synchronous system, it is important that every clocked element in the system receive its clock edge at precisely the same time. To see why this is so, consider the general model of a controller with just two state flip-flops, shown in FIG. 17. Proper synchronous operation results when the CLKA and CLKB active edges occur at the same instant. In that case, the combinational logic network will compute new values for A(D) and B(D) based on the current values of A and B and the status signals and, a few nanoseconds after the clock edge arrives, A and B will assume new values equal to the old values of A(D) and B(D). The changing flip-flop outputs will throw the combinational logic network into shock as it adjusts to the new inputs and computes new values of A(D) and B(D). The combinational logic outputs will experience hazards and delays caused by the finite propagation time of the gates. A(D) and B(D) may therefore have momentary wrong values but will eventually settle to levels predicted by Boolean algebra and will then wait for the next clock edge to come along.

Now suppose that CLKB is delayed with respect to CLKA. Signal A changes when CLKA fires; this will throw the gates into shock as before, and both A(D) and B(D) may have momentary wrong values for a few nanoseconds.

Suppose that the "late" CLKB edge comes during this time of instability; then B can record a false value. Even more galling: suppose that before CLKB fires the combinational logic stabilizes to "new" values of A(D) and B(D), based on the new value of A and the old (unchanged) value of B. At this time, both A(D) and B(D) can be incorrect. Then, when CLKB fires, an incorrect B is stored, and this change ripples through the logic. This phenomenon, clock skew, occurs when the clock edges do not appear simultaneously at all clock inputs: Clock skew can arise from gates in the clock path or from different wire lengths between the clock source and the clock inputs.

Don't gate your clock. Gating a clock is bad practice because it introduces skew (and may introduce hazards on the clock line). Suppose that flip-flop A responds to a positive clock edge but that we use a different type of flip-flop for B that acts on a negative clock edge. We may be tempted to create the CLKB signal by running an inverter from CLKA, but this is just a case of gate created clock skew. To avoid this type of skew, it is best to drive all flip-flops with the same active clock edge, thereby eliminating the need for inverters in part of the clock system. In all our clocked building blocks for synchronous design, we use positive-edge clocks.

Beware different length of clock paths. It is also desirable to have the clock distribution lines spread radially from the clock source to the separate elements of the system rather than linking them together in one long chain.

When designing large systems you may have to buffer the clock lines to build up sufficient power, as shown in the radial clock distribution system in Fig. 18. This "gating" of the clock lines is acceptable if the three buffers are all of the same kind and, preferably, in the same integrated circuit package, so that they all have precisely the same propagation delays. The distribution wires should also be of the same length, within a few inches, since 8 inches of wire represents about 1 nanosecond of signal propagation time.

FIG. 18. A buffered radial distribution system for the master clock.

FIG. 19. An ASM fragment that illustrates races.

Asynchronous Inputs and Races

Design assumption (b) is that all the inputs to an ASM change synchronously with the master clock. In practice, inputs often arise from sources outside our digital circuit, and the timing of changes in these inputs is beyond our direct control. These inputs are asynchronous, and we usually append an asterisk * to their variable name to indicate their asynchronous nature. To see why asynchronous behavior is troublesome, consider the three-state ASM fragment in FIG. 19. We assume that we have made the (encoded) state assignment shown in the figure and that the sole test input IN* is asynchronous. For the moment, ignore the conditional output.

Transition races. Each state flip-flop requires that its input be stable for a few nanoseconds prior to the clock edge. This allows the input values to circulate through the internal circuitry of the flip-flop and stabilize to await the clock edge. If the flip-flop inputs change during this "setup time," the value of the flip-flop's output after the clock edge will be unpredictable. After settling down, the output will assume either a T or F value, but which value is uncertain.

Now assume that the ASM in FIG. 19 is in state 00, and IN* = T. Then the inputs to both state flip-flops are 0, and the system is preparing to move next to state 00, the same state as before. If IN* changes to F, the inputs to flip-flops A and B will change to 1, in preparation for the move to state 11. If the change in IN* occurs during the flip-flop setup time, we cannot predict the changes in the flip-flops. Thus the next-state code may be 00, 01, 10, or 11, depending on the outcome of the race at the flip-flop inputs. Although we might argue that either state 00 or state 11 is an acceptable next state, clearly to reach states 01 or 10 is a calamity. This situation, in which the next state depends on the exact timing of the flip-flop input changes, is called a transition race. The situation is obviously intolerable and you must be certain that such races do not appear in your designs. Before considering the solution to the problem, let's investigate another type of race.

Output races. Now see what happens to the conditional output CMDI in the ASM of FIG. 19 when IN* changes at an awkward time. For the moment, ignore the possibility of transition races. In state 00, when IN* is true, CMDI is false, whereas when IN* is false, CMDI is true. A change in IN* will cause a corresponding change in CMDI. If IN* changes from T to F late in the state 00 time, CMDI will be true for only a short part of a clock time, before the system moves into state 11. The possibility of a "runt pulse" for CMDI is in itself a serious matter, since the output CMDI may be used in situations that cannot tolerate such a short pulse. This problem is called an output race; it is a direct result of an ASM output being conditional on an asynchronous input.

For example, suppose that the purpose of CMDI is to set a flip-flop that lights a light announcing that we have left state 00. If IN* changes so late in the clock cycle that the flip-flop is not set to true, we will be in state 11 and the light will still be off.

The combination of the transition race and the output race in this ASM may lead to numerous ludicrous results, depending on the exact reactions of the flip-flops to the changing IN* input. We could end up in state 00 with the light on, or in state 01 with the light off, and so on.

Avoiding races. Asynchronous inputs are at the root of the problem of races. Asynchronous inputs are fatal, dangerous, or at best difficult to use safely.

There is no way to avoid output races except to avoid conditional outputs that depend on asynchronous inputs. The engineering literature is full of elaborate methods for skirting around the transition race problem by tinkering with the state assignments. The proper approach for good design style is to eliminate the cause of the problem-the asynchronous input. We may do this by syn chronizing the input using a D flip-flop clocked by the system clock. The ASM will test the output of this flip-flop, and since this output only changes synchronously with the clock, there will never be a race in the ASM caused by that input. So we have a golden rule for synchronous design:

Don't allow dangerous asynchronous inputs into your ASM chart.

You must be alert to identify asynchronous inputs-they have a habit of sneaking into the design. In our example, the input was easy to detect, since we had added an * to the signal name, but in practice, adding the asterisk is your responsibility, whether or not the original name was so equipped. Many useful synchronous integrated circuit chips have asynchronous control inputs for clearing, setting, or loading. The only routine use that we make of such inputs is as a master clear signal to be asserted when power is first applied or when the system "hangs up." In the one-hot controller method you saw an illustration of this usage; most controllers will require one such master clear signal. In other circumstances, avoid using asynchronous control signals.

Asynchronous ASMs

Our ASMs have all been synchronous, with a master clock to define the times for state transitions. It is possible to build asynchronous state machines, which depend not on a clock but on changes in the inputs themselves to create transitions between states. Troubles abound in this form of design, primarily because of these factors: (a) All inputs must be clean, with no glitches, since any instability or noise on the input signals may induce spurious state transitions.

(b) The theory of asynchronous circuits is complex and diverse, involving numerous special cases and usually invoking unacceptably restrictive design conditions.

We will not instruct you in the theory of asynchronous circuits, beyond the microscopic view we took in Section 4. Rather, we wish you to avoid this mode of design wherever possible. In Section 9 you will encounter a form of asynchronous ASM used to connect a peripheral device to a minicomputer, but this special case is as far as we will take the subject. If at some later stage in your design career you wish to investigate asynchronous circuits, you will find a rich literature. However, we wager that, after your investigation, you will still refrain from designing circuits in this mode.

Sidestepping the Pitfalls

Getting into trouble in digital design is easy. Asynchronous methods constantly expose the control algorithm to every signal change, intentional or accidental.

Designing each circuit to be secure against such an unceasing attack requires enormous effort. Asynchronous control, despite its tempting generality, is too tedious to use as a major tool in design.

Synchronous methods ease the pressure on the designer by isolating the sensitive periods into small, regular intervals preceding clock edges. Expressing problems synchronously effectively moves the asynchronous difficulties away from the algorithm into the clock. This is a great simplification. We must work hard to make the synchronous clock system reliable, but the procedure is the same for all designs. In return, we gain breathing room in the algorithm. Syn chronous design causes specialization of the hardware, where extreme versatility is rarely needed, yet it decreases the number of special cases in the process of algorithm design, giving designers valuable systematic methods.

As you saw in Section 4, the problem of metastability in the outputs of sequential circuits is inherent in every design. Wherever two or more inputs may change at the same time, metastability is possible. In asynchronous design, virtually every input may present this problem. In synchronous design, the asynchronous external inputs, which we routinely run through synchronizing circuits, are trouble spots. By synchronizing these inputs we have greatly simplified the internal structure of our control algorithm, but we have not eliminated the possibility of metastability. In Section 12 we offer recommendations for dealing with this irritating issue.

Debugging Synchronous Systems

Not only do synchronous methods ease the designer's worries, but they also support a powerful debugging technique. The system clock controls the speed of a synchronous design. Consider the benefits of a design that will behave properly not only at high clock speeds but also at slow speeds, even at zero speed. We are particularly interested in the zero-speed case, because with this feature we may freeze the system in any state by stopping the system clock.

We may then debug the logic at leisure. Compare this technique with a system that requires a closely controlled clock frequency. Error conditions may be observable for only one clock cycle. If maintenance engineers cannot slow or stop the machine at will, they must troubleshoot it in real time. Debugging systems at high speed is much more complicated than freezing the machine in the erroneous state.

Synchronous designs that work at a variety of clock speeds, including zero, are called static. The benefits of static systems are so great that we should strive to use this technique whenever possible. After you have debugged a few dynamic (nonstatic) systems, you will better appreciate the beauty of static designs. In Section 6, we develop a system clock module for use in static designs.

CONCLUSION

This ends our exposition of basic design methods. We have covered the basic building blocks and there were remarkably few types. Next, for expressing algorithms, we described a language that contained only three constructs: the state box, the conditional output oval, and the conditional branch diamond. With these simple tools we can create digital systems limited only by our imagination.

The basic elements of style emerge from a desire to achieve understandable designs. We have discovered through bitter experience that opaque designs are enormously expensive in the long run. A good designer will use a design approach that always promotes clarity. We mention three important aspects of such an approach:

(a) Good documentation. It is tempting to avoid the drudgery of documentation.

After all, the real fun is in the design and debugging. It is hard enough to document a simple design; complex designs are seldom documented well enough for anyone but the designer to understand them. Often, after a few months, even the designer cannot fathom the design. A good designer will adopt techniques that encourage or require good documentation during the design process. Mixed logic, functional building blocks, and ASM charts are powerful aids to documentation, built into the design discipline.

(b) Modular designs. Nearly every design will require small changes during its useful life. Monolithic designs are hard to understand and modify. Our goal is to build more accessible designs, so that we may change part of the complete system without the change rippling through the rest of the design.

Too often, digital designers overlook the cost of servicing digital equipment. Since servicing usually falls to other people, poor designers are not forced to live with their abominations. Hardware will need repair. Digital devices should be simple and modular so that other people can perform the maintenance. The use of functional building blocks and the separation of architecture from control both encourage modular design.

(c) Absence of tricks. Digital design affords unbounded opportunity for clever tricks. Such trickery should not be, but often is, confused with good design.

We can benefit from the experience of computer programmers who, after years of maneuvering bits in clever ways, have come to realize that systematic, clear methods yield far more dividends than cute but obscure tricks.

Perhaps we can sum up good design philosophy in a single phrase: common courtesy. Consider the users and maintainers of your system, and ask yourself what they will need in order to deal efficiently with your creation. Let courtesy be your guide.

Summary of Design Guidelines

Here we bring together the three forms of design guidance presented in this section.

Basic Approach to Solving a Digital Problem (a) Design from the top down.

(b) Separate the architecture from the control.

(c) Refine the design, letting the control algorithm and the architecture influence each other as you converge on the solution.

Technical Design Considerations

(a) Use synchronous (clocked) design techniques.

(b) Avoid asynchronous inputs in the algorithm.

A Courteous Philosophy (a) Develop good documentation during the design.

(b) Keep designs modular and simple.

In Section 6, we will work out several examples of designs. In the process, you will see the design tools in action and study in their proper context a number of common design situations and their handling. In Section 7, we will embark on the construction of a complete minicomputer, using top-down techniques at the MSI level of complexity. Finally, in Part III, we will introduce the powerful techniques of microprogramming and software control for managing complex design problems.

So now begins the actual design!

RESOURCES

CLARE, CHRISTOPHER R., Designing Logic Systems Using State Machines. McGraw-Hill Book Co., New York, 1973. The original exposition of the ASM approach.

DIETMEYER, DONALD L., Logic Design of Digital Systems, 2nd ed. Allyn and Bacon, Boston, 1978. Section 13: traditional asynchronous design.

ERCEGOVIC, MILOS D., and TOMAS LANG, Digital Systems and Hardware/Firmware Algorithms. John Wiley & Sons, New York, 1985. Good treatment of sequential systems.

FLETCHER, WILLIAM I., An Engineering Approach to Digital Design. Prentice-Hall, Englewood Cliffs, N.J., 1980. Uses ASMs.

HILL, FREDERICK J., and GERALD R. PETERSON, Introduction to Switching Theory and Logical Design, 3rd ed. John Wiley & Sons, New York, 1981. Good traditional treatment of sequential circuits.

MALEY, G. A., and J. EARLE, The Logic Design of Transistor Digital Computers. Prentice Hall, Englewood Cliffs, N.J., 1963. An influential early work; you can see how difficult design can be without systematic methods.

MANO, M. MORRIs, Digital Design. Prentice-Hall, Englewood Cliffs, N.J., 1984. Presents ASM charts as an alternative to traditional techniques.

MEALY, G. H., "A method for synthesizing sequential circuits," Bell System Technical Journal, Vol. 34, September 1955, page 1045. The Mealy state machine.

MILLER, RAYMOND E., Switching Theory. Vol. 2, Sequential Circuits. John Wiley & Sons, New York, 1966. An important early work.

MOORE, E. F., "Gedanken experiments on sequential machines," in Automata Studies, edited by C. E. Shannon and and J. McCarthy. Princeton University Press, Princeton, N.J., 1956. The Moore state machine.

WIATROWSKI, CLAUDE A., and CHARLES H. HOUSE, Logic Circuits and Microcomputer Systems, McGraw-Hill Book Co., New York, 1980. Uses ASMs. Sensible treatment of asynchronous ASMs.

QUIZ and EXERCISES

1. Sketch a general method for the top-down solution of a digital problem.

2. How does the ASM chart differ from a software flowchart? Using FIG. 8 as an illustration, explain the fundamental differences in viewpoint.

3. What is meant by "active clock edge"?

4. What is a state time? In a synchronous system, what determines the duration of the state time?

5. Draw diagrams to illustrate the following: (a) A four-state cyclic (sequential) ASM. (b) A three-state ASM with a fixed sequence of states containing a conditional output.

(d) A four-state ASM that can produce this sequence of states: SI, S3, S2, SI, S4, S2, SI, SI, SI, ....

6. Explain the difference between an ASM input and an ASM output.

7. What is the difference between an ASM conditional branch and an ASM conditional output? Does one imply the other?

8. In a synchronous ASM, an unconditional output is stable for virtually the entire duration of the state. For what period is a conditional output stable?

9. Produce ASM charts that perform each of the following software operations: (a) If X = N, then ... . (b) If X f. N, then ... ; else ... . (c) For X from A to B step C, do ... . (d) While X = Y, do ....

10. Here is a two-state ASM:

(a) Convert the ASM into a form that has a single decision box of the form below, with eight branches:

[D, M, R]

(b) Implement the original ASM and your modification. From the viewpoint of the implementer, which form is best?

11. Using timing diagrams, show the difference between these two ASMs:

12. In many instances, we may remove a conditional output from an ASM by creating a new state dedicated to generating the old conditional output (see the diagrams in Exercise 11). Under what circumstances will this translation produce difficulties?

13. A conditional output is a function of both state and path. In a logic equation for a conditional output, what logic operator connects the state term with the path term? In other words, what logic operator corresponds to the box in the equation

Conditional.output = State[?] Path

14. The ASM notation can be used to indicate that "A assumes the value of B at this time." Show that this notation may be viewed as a shorthand for an ASM state that contains a test and a conditional output.

15. Consider the following fragments of an ASM chart. Carefully state what, if anything, is wrong with or objectionable about these notations.

16. What is a state generator? With an encoded state assignment, how many states can four state variables specify?

17. Some older design methods lump the controller and architecture of FIG. 1 into the combinational logic of FIG. 10. Why is this poor practice?

18. Design a one-hot controller for FIG. 8.

19. Produce a realization of the ASM in FIG. 9 that is equivalent to FIG. 11 but with the state assignment P = 00, Q = 01, R = 10. Is there any difference in hardware complexity?

20. Can you make a state assignment in FIG. 9 that will simplify the hardware for generating CMD1?

21. Design a traditional state generator for the ASM in FIG. 20, using D flip-flops.

22. Design a multiplexer controller for the ASM in FIG. 20.

23. Design a one-hot controller for the ASM in FIG. 20. What special precaution must you take when using the one-hot method?

24. Design a ROM-based controller for the ASM in FIG. 20. Tabulate the contents of the ROM.

FIG. 20.

25. Devise implementations, including circuit diagrams, for the synchronous ASM in FIG. 21, using each of the state-generation techniques given below.

(a) Multiplexer controller, using SSI- and MSI-level components.

(b) Multiplexer controller, using PALs.

(d) One-hot controller, using SSI- and MSI-Ievel components.

(e) One-hot controller, using PALs.

26. Perform Exercise 25 for the ASM in FIG. 22. Generate W with a JK flip-flop and N with an enabled D flip-flop. The notation "Z : Y" implies "Z assumes the value of Y at this time" (see Exercise 14).

27. The logic equation for an ASM output has terms involving distinct logic variables for each ASM state in which the output appears.

(a) For a state generator with encoded state assignments, show a standard and systematic method of transforming the state code into logic variables for each state, using a decoder.

(b) Instead of using a decoder, we can generate ASM outputs with AND gates to decode the required logic variables for states from the state code. Demonstrate this method. When would you use this method in preference to the method of part (a)?

28. In the one-hot state generator method, show how logic equations are generated for conditional and unconditional outputs. Is output signal generation simpler with the one-hot method than with the multiplexer method?

29. Use two 8-input priority encoders to detect when more than 1 bit is true in an 8 bit quantity. (Hint: Connect the input signals to each of the encoders, but in opposite order.) Can this design be extended to more than 8 bits? Show a use of this circuit in the design of one-hot controllers.

FIG. 21.

FIG. 22. A "loaded" ASM for practice in implementing.

30. Consider the following eight-state cyclic ASM:

Design state generators for this ASM as a multiplexer controller, a one-hot, and a binary counter. Which method is simplest in this special case?

31. Consult a TTL data book, and design a state generator equivalent to FIG. 14, using 74LS00, 74LS02, 74LS04, 74LS175, and 74LS352 integrated circuits. Draw a complete circuit diagram, including pin numbers. How many chips are required?

32. Why is the clock such an important element in a synchronous design?

33. What is meant by "gating the clock"? Why is this practice dangerous?

34. For the ASM in FIG. 19, show with a timing diagram how the asynchronous input IN* can cause a transition race.

35. Using FIG. 19, demonstrate an output race.

36. How may you avoid races in your designs?

37. Suppose that, contrary to our basic design approach, you must deal with a synchronous ASM that tests an asynchronous input T2*, as shown below. The logic-level timing diagram shows the condition of three signals over a period of six state times.

Complete the logic-level timing diagram for the signals OUT1, OUT2, and OUT3.

38. In FIG. 11, assume that the propagation delay of gates and flip-flops is tp.

(a) How much clock skew is tolerable between flip-flops A and B during the transition from state 11 to state 00? (b) Repeat part (a) for the transition 10 --> 00. (c) Repeat part (a) for the transition 01 --> 00.

PREV. | NEXT