AMAZON multi-meters discounts AMAZON oscilloscope discounts
In Part I we presented basic design tools and introduced components used to build digital systems at the MSI level of complexity. The fascinating part of digital design lies before us. We now consider how we may assemble a complete system from building blocks. It is in this area that the designer can create elegance and beauty, or chaos and headaches. In Part II we present methods of designing systems of moderate complexity, using the fundamental integrated circuit building blocks. In Part III we will introduce programmed control of complex digital systems, using microprogramming and conventional microcomputers. The methods of Part II serve to support independent designs and to provide the "glue" required to design systems with programmed control.
To some extent, digital design is an art form. Most designers have had to develop a style of digital design by trial and error, and their efforts often have not converged to an efficient and aesthetic style. On the other hand, there are underlying principles that can be immensely useful to designers. Our goal in this book is to start you down the right path, and to take you far enough so that you can develop your own designs with a solid sense of good style.
Design style is a curiously neglected subject, perhaps because a traditional study of logic design emphasizes the microscopic transistor and gate aspects of the subject. We emphasize a macroscopic view of digital systems by starting from the original problem. The result is a top-down approach to design.
ELEMENTS OF DESIGN STYLE
Here are the guidelines for good design style:
(a) Design from the top down.
(b) Maintain a clear distinction between the controller and the controlled hardware (the architecture).
(c) Develop a clearly defined architecture and control algorithm before making detailed decisions about hardware.
Top-Down Design
A design starts with a careful study of the overall problem. At this stage, we deliberately ignore details and ask such questions as: (a) Is the problem clearly stated? (b) Could we restate the problem more clearly or more simply? (c) If we are working with a subsystem of a larger system, what is its relationship to its host? Would a different partitioning of the entire system yield a simpler structure? At this stage our concerns are global, and we must stay at that level until we have hammered out a sensible statement of the problem and have digested the problem to the point where we understand what we must solve. This is essential, since any difficulties at this level are serious. No amount of wizardry with components can remedy errors in the understanding of the problem.
After we have clearly specified the problem at the global level, we seek a rational way to partition the problem into smaller pieces with clearly defined interrelationships. Our goal is to choose "natural" pieces in such a way that we can comprehend each piece as a unit and understand the interaction of the units. This partitioning process proceeds to lower levels until finally we choose the actual integrated circuits.
Unfortunately, many designers reverse this process by rushing to integrated circuit data books to find the chip that will "solve" their problem. Often they find a circuit that solves a slightly different problem. Thus enters the infamous "patch" to force the problem, which is itself not well defined in the designer's mind, to the integrated circuit. This process proceeds from the bottom up, often in a divergent manner. Many commercial designs bear unmistakable traces of this method of design.
Separation of Controller and Architecture
One of the first steps in a top-down design is to partition the design into (a) a control algorithm and (b) an architecture that will be controlled by this algorithm.
The top-down analysis will suggest a rough preliminary version of the system's architecture, involving abstract building blocks such as registers, memories, and data paths. Since the architecture is specific to the particular design, there is no general prescription for writing down this preliminary architecture. The main guidelines are to make the architecture natural to the problem and to design with high-level units rather than with chips and voltages. The examples of design in Section 6 will illustrate the art of specifying the rough architecture.
Next, we work out the details of the control algorithm at an abstract level.
The control algorithm is often surprisingly independent of hardware. For example, if you were designing a computer, what operations would you expect your control algorithm to accomplish?
(a) Get the next instruction.
(b) Test to see if operands are needed and get the operands if required, making any necessary indirect memory references to indirectly addressed operands.
(c) Execute the individual instruction.
As you will see in Section 7, we may specify a complete flowchart (algorithm)
for operations like this with almost no knowledge of the specific hardware.
You should explore the construction of the control algorithm until you have a clear understanding of your approach to the solution. The exploration may go through several iterations, but eventually you will complete the process, at which time you should turn your attention to the hardware for the architecture that is suggested by the control algorithm. The algorithm will guide you to the hardware. Note how powerful this concept is. We have a tool that allows us to solve a problem in a rational way instead of randomly looking at integrated circuits and wondering if they will fit into the design.
We can formalize the controller-architecture separation with the diagram in FIG. 1. The controller issues properly sequenced commands to the controlled device. These commands make the architecture perform the actions dictated by the control algorithm. Usually, the controller will need status information from the architecture that serves as decision variables for the control algorithm. As the design matures, the controller's command outputs and status inputs go from abstract concepts of control to Boolean variables, and finally to voltage representations of the Boolean variables.
Consider the following example. A problem requires that a word be written into a memory. The preliminary architecture for the problem is just a black box for the memory, the details of its inner construction being deferred until later.
The memory will require four items of input: a memory address MA to tell where to write the data, a word of DATA for input, a line R/W to tell whether to read or write, and a GO signal to start the read or write operation. The only status returned by the memory will be memory cycle complete CC.
FIG. 1. The structure of a state machine.
FIG. 2 is the functional diagram corresponding to this analysis. The command lines are:
MA (n lines)
DATA (m lines)
R/W (1 line)
GO (l line)
The parameters nand m are determined by the characteristics of the memory needed by the problem. For instance, a 1,024-word by 8-bit memory would have n = 10 (1,024 = 210 ) and m = 8 (each word of memory has eight bits). The status line is CC.
FIG. 2. A diagram of a memory write machine.
We now have a good idea of what signals the controller and architecture must generate and accept, even before we know what hardware we will use to build the controller or what the memory box is like inside. We choose the memory command lines by realizing that we must have data to write into memory and a location where it must be written. The structure in FIG. 2 is not affected by the actual type of memory.
We can say something about the nature of the control algorithm that initiates a memory write operation, without knowing exactly how we will translate that algorithm into hardware. The algorithm must look something like FIG. 3. The· purpose of the first step STW is to issue a GO signal to the memory, along with the necessary data and commands to initiate a writing operation. The next step WAITs until the memory has finished the writing.
We can accomplish an amazing amount of the design by a general consideration of the problem. Carry the top-down analysis as far as you can, because decisions at this level are more easily altered than they will be once the hardware has intruded.
FIG. 3. Algorithm for writing to a memory.
Refining the Architecture and Control Algorithm
We are now ready to move down one level. We have sketched out the algorithm by ignoring the hardware as much as possible; instead we were trying to reduce our problem to high-level, abstract statements of control and architecture. The only consideration about hardware introduced thus far were general ones that we could state from a knowledge of the variables required for the operation of abstract building blocks such as memories, registers, and arithmetic units. We now begin to refine the control algorithm by introducing more detail.
As we refine algorithm, we need a more detailed knowledge of the architecture of the system. We therefore begin to elaborate the architecture as a set of building blocks, moving carefully through a set of high-level building blocks toward a selection of the major hardware. We choose the architectural elements by asking what specific building blocks the developing control algorithm requires; we do not select elements by looking in a data book and saying, "Hey, this is a neat chip-I must fit it into my next design." A good architecture will be simple, clear, and easy to control. If it is not, there is no way to rescue the resulting mess with exotic integrated circuits or Boolean algebra. If the architecture is clear and simple, the rest of the design will be relatively straightforward. This step-the first introduction of hardware is an important point in the design.
After we choose the major building blocks, we know what control signals they will require. At this point, we tabulate these signals and then quit worrying about the hardware. In fact, we suppress consideration of the hardware lest it capture our thought processes and cause us to lose sight of the algorithm we are trying to develop. Let the algorithm drive the design process as much as possible. Now we can continue with an elaboration of the algorithm, whose function is to provide a properly sequenced set of commands to the architecture.
Spend a large fraction of the total time for the project on the detailed algorithm architecture phase.
After we have completely specified the algorithm, we can reconsider the architecture and our choice of building blocks. The detailed construction of the algorithm will usually reveal areas of the design that we can simplify or speed up by using slightly different architectural components. We incorporate these changes into the architecture and make the corresponding changes in the algorithm.
At this point the process should have converged to a final solution. We should have:
(a) The architecture. This should include a detailed set of components and data paths for the controlled device-usually a specification of the actual integrated circuits for the major components such as registers, ALUs, and memories, and a statement of the command signals that these components require and the status signals that they produce. Our specification of the architecture does not include any logic required to generate these commands, since the generation of commands is assigned to the control algorithm.
(b) The algorithm. This will produce a properly sequenced set of command signals to make the architecture perform the original problem. It does not include the hardware to implement the algorithm. We can derive the hardware from the algorithm in a straightforward and mechanical way, as you will see later in this section.
If by this time the process has not converged to a stable solution, you probably had trouble at an earlier stage of the design process. In such circum stances, proceeding further is fruitless; you should go back to the beginning and start over. Do not "kludge" your solution. You have not yet wrapped any wires or drawn any hardware circuit diagrams, so beginning anew is relatively painless.
And now, a secret: whether in hardware or software, no one designs a system strictly from the top down. A knowledge of low-level components and techniques always influences the design, even at the highest levels. The best top-down hardware designers have an intimate knowledge of hardware, and this knowledge tempers and guides the high-level design decisions. As their under standing of the design expands, good designers use their knowledge of lower level technology to avoid unproductive approaches. The designer dips repeatedly into lower and more detailed levels for short excursions, but invariably returns to the present top level. The top-down approach has the great virtue of providing the discipline that keeps one thinking at the highest useful level. We like to imagine that a complex design proceeds linearly from the top to the bottom, but that is rarely so. But whenever you dip down, your top-down training will pull you back up as soon as possible.
ALGORITHMIC STATE MACHINES
The control algorithm plays a major role in a digital design, so we need a good notation for expressing hardware algorithms. The notation should assist the designer in expressing the abstract algorithm and should support the conversion of the algorithm into hardware. There are several ways of describing the control.
For synchronous circuits, the ASM chart technique is the superior notation.
ASM stands for algorithmic state machine. * The name is appropriate, since all controllers are state machines, and we are trying to translate algorithms into controllers. The ASM chart is a flowchart whose notations superficially bear a strong resemblance to the conventional software flowchart. The ASM chart expresses the concept of a sequence of time intervals in a precise way, whereas the software flowchart describes only the sequence of events and not their duration.
States and Clocks
An algorithmic state machine moves through a sequence of states, based on the position in the control algorithm (the state) and the values of relevant status variables. The concept of a state implies sufficient knowledge of present and past conditions to determine future behavior. It is the task of the present state of the system to produce any required output signals and to use appropriate input information to move at the proper time to the next state. In most of this book we are dealing with synchronous systems whose state times are determined solely by a master clock. The most convenient form of clock is a periodic square-wave voltage:
The clock event that triggers the transition from one state to another and other actions of the system is called the active edge, and in synchronous systems is usually the rising (L --> H) edge of the clock. In a synchronous system, the clock will thus have T = H. Commonly, the clock period T ranges from 20 nanoseconds to several microseconds. The frequency f of the clock is its number of oscillations per second. Frequency and period are related by the expression
The unit of frequency is the hertz (Hz), which is defined as one oscillation per second. Convenient units for fast waveforms are kilohertz (KHz = 10^3 Hz) and megahertz (MHz = 10^6 Hz).
[* T. E. Osborne developed the ASM chart notation and C. R. Clare describes the method in his book, Designing Logic Systems Using State Machines (New York: McGraw-Hill Book Co., 1973). ]
The clock's frequency may vary, and the clock may even stop-desirable during the debugging phases of a design. Within reasonable limits, the duration of the high portion of the clock waveform in relation to the total clock period (the duty cycle) is unimportant. The crispness and reliability of the active clock edge is of extreme importance, and designers of systems pay close attention to the production and distribution of an excellent clock signal.
ASM Chart Notations
States. Each active transition of the clock causes a change of state from the present state to the next state. The ASM chart describes the control algorithm in such a way that, given the present state, the next state is determined un ambiguously for any values of the input variables. The symbol for a state is a rectangle with its symbolic name enclosed in a small circle or oval at the upper left corner:
We would represent a purely sequential algorithm as an ASM chart of a sequence of states, as in FIG. 4. The corresponding division of the time axis would be ...
A sequence is an inherent property of an ASM chart; state Y follows state X, and so on. It is cumbersome to show time relations with a timing diagram such as the above; therefore, you should learn to think of time as rigorously implied in the ASM chart notation.
FIG. 4. A purely sequential ASM.
Outputs. The function of a controller is to send properly sequenced outputs (voltage command signals) to the controlled device according to some algorithm.
To indicate an output, we place the command description within the appropriate state rectangle. In this book we use several notations for outputs. Depending on our depth of understanding of our design and on the level of detail we wish to convey, we may use informal expressions of actions or detailed statements of particular output operations. FIG. 5 contains some examples. In state PRINT.LINE, the expression "Start print cycle" represents a set of actions, as yet not fully elaborated, that initiates a printer cycle. The arrows in the next two lines imply actions that are to be consummated at the end of this state; at that time LINE is to be loaded into PRINTBUF, and the AC register is to be cleared. The fourth line, MOVING, calls for the assertion of the signal MOVING (making MOVING true) during this state. The last line means that the output variable STATUS is to have the value of the variable ERRFLAG (T or F) during this state. Other output notations may be useful; improvising notations is fine as long as you define your terminology.
FIG. 5. ASM output notations.
Branches. Purely sequential ASMs are of little interest because they are usually not powerful enough to describe useful algorithms. We need some way to express conditional branches so that the next state is determined not only by the present state but also by the present value of one or more test (status) inputs.
Our symbol is the same as in conventional flowcharts for software: the diamond or diamond-sided rectangle
We incorporate this symbol into the ASM chart by appending it to a state rectangle, placing the description of the test input inside the diamond, as in Fig. 6. In this case a portrayal of the time line would be
FIG. 6. An ASM with a conditional branch.
The decision to jump to one of the two states B or C is made during state A, and the jump occurs at the end of state A. In hardware implementations the voltage representing input X must be stable for some time before the decision.
Ideally, X should be stable for the entire clock period of state A, for then the hardware that decides to jump to B or C has the maximum time to settle. It is important to realize that a test does not require a separate clock period-it is done "in parallel" with the actions of the parent state rectangle and thus is part of the parent state.
We are not limited to two-way branches from a state. We may draw sequences of test diamonds or we may have more than two paths coming from the same diamond. Two ways of representing a three-way branch are shown in FIG. 7. The test structure in FIG. 7a is a diagrammatic representation of a truth table in which neither P nor Q appears to dominate. FIG. 7b conveys the feeling that the test of variable P is of higher priority than the test of Q. Which form is preferable depends on the designer's thought process. Use the ASM notations that best describe your design.
FIG. 7. Alternative representations of a three-way branch.
Conditional outputs. A command written within a state rectangle indicates that the controller is to produce the output whenever the algorithm is in that state. Sometimes we want a command to occur only when some other condition also exists. We call such a command a conditional output and specify it within an oval, as in FIG. 8. Command CMDI will appear for one state time whenever the ASM is in state P. The command CMD2 will occur during one state time whenever the ASM is in state Q, but when the ASM is in state P, CMD2 will occur only if test input Z is false. In this example, CMD2 is an unconditional output in state Q and a conditional output in state P. *
FIG. 8. An ASM with a conditional output.
Test inputs may serve two functions in ASM charts: they may help specify the next state and they may control the issuing of conditional outputs. Ovals for conditional outputs and diamonds for tests of inputs belong to the parent state, since the activities will occur during the same state time. A state thus consists of its rectangle, which is always present, and any test diamonds and conditional output ovals associated with that state. Unconditional outputs are a function only of the parent state; conditional outputs depend on both the state and the path within that state. It would be appropriate to draw a dashed line around the entire structure for each state, but we usually do not do this because the chart defines each state without this aid.
[* An ASM with only unconditional outputs is equivalent to the Moore machine of traditional sequential circuit theory; the traditional Mealy machine has conditional outputs. The ASM formulation subsumes both traditional cases. ]
This is the entire ASM chart notation. Our goal is to use it to help us build digital circuits. In the following sections we emphasize the design phase, the difficult part of our work. Once we have an architecture and a control algorithm, we must then implement them. In this section we next present some standard and systematic methods for realizing any ASM chart control algorithm.
REALIZING ALGORITHMIC STATE MACHINES
Once we have expressed the control algorithm as an ASM chart, it is a simple job to express the flow of control as hardware. We describe four methods-a traditional technique and three style-driven methods.
Our task is to construct a state generator for a given ASM. In any state machine, the concepts of present state and next state are vital. The state generator's task is to record the present state and generate the next state. State machines are sequential circuits, and to keep track of the present state we need a memory.
In this part of the book, we use flip-flops as the state memory. There are two ways to express the present state in a flip-flop memory. We may assign a binary number to each state and express the present state as an encoding, using its binary number. In this scheme, n flip-flops will encode up to 2D states. We may describe a state by its name or by its number in binary or in decimal, as we find convenient. Alternatively, we may avoid the encoding by assigning one flip flop to each state. We will use each of these approaches.
FIG. 9. A simple ASM with a state assignment.
Traditional Synthesis from an ASM Chart
The traditional technique for state generation is to use an encoded representation of the present state and compute the code for the next state. The bits of the code are the state variables: n state variables describe up to 2n states. The term state variable used in this way is unfortunate, since there is a more important use for this term--to specify the name of a logic variable for each state. Nevertheless, in this section, we use the term in the traditional way. We make an arbitrary state assignment of binary state variable values to states. On the ASM chart, we show the binary assignment for each state above its state rectangle on the right-hand side. We might choose the state assignment shown in Fig. 9 . We need not label the test diamond or the conditional output oval since they are part of state 00. The state assignment is arbitrary. There may be more hardware associated with one state assignment than another, but this is not an important factor. The two state variables B and A in FIG. 9 specify an address that points to the present state. If we could compute the next address and put it into the state flip-flops, we would then be pointing at a new state. As you might guess, we can use gates to build a combinational circuit to compute the next address. FIG. 10 is the model of this process. This figure displays only the control portion of the digital system, not the architecture.
We can use either JK or D flip-flops for the state variables. JK flip-flops usually result in less combinational logic than D flip-flops, but they also require twice as many input lines. The JK form is more compact but yields more obscure results. In this example, we use D flip-flops to provide a more direct comparison with the methods to follow.
For the ASM chart in FIG. 9, the state generator model of FIG. 10 has one status input Z, two command outputs CMDI and CMD2, and two state flip flops Band A. The combinational logic must compute the value of the next state address:
The condensation of rows on variable Z arises because the move from states 10 or 11 does not depend on Z.
FIG. 10. A model of an encoded ASM state generator.
The state assignment 01 is a possible pattern of the flip-flop's outputs but does not label any state in the algorithm of FIG. 9. Hardware is perverse and may get into this state, for example during power-up, when flip-flops may settle into random values. In our example, pathological behavior would result if the next-state logic computes 01 whenever the present state is 01. We would be locked into state 01 and could not get out unless we did something drastic, such as shut off system power. Clearly, if we ever get into state 01, we must get back to the main algorithm loop. Thus, we have arbitrarily chosen to go to state 00. We must always take into account all unused state assignments in encoded designs of state generators.
We may write the equations for state flip-flop inputs B(D) and A(D) by inspecting the logic table above. They are
B(D) = BoAoZ + BojfoZ = BoA
A(D) = BoA oZ
When we are designing more complex state machines, K-maps may help to simplify the expressions for the state flip-flop inputs.
This completes our discussion of the design of the state generator. But the purpose of the algorithm was to produce properly sequenced outputs. An examination of FIG. 9 yields these equations for the outputs:
CMDI = STATE.P = BoA (5-1)
CMD2 = STATE.poZ + STATE.Q = BoA oZ + BoA (5-2)
The hardware for the ASM is shown in FIG. 11.
Comments. The approach we used in this section-to compute the code for the next state-is a traditional method. JK flip-flops used to store the state variables may lead to somewhat more compact next-state logic than D flip-flops, since the JK flip-flop is the more flexible device.
Unfortunately, the traditional method results in no obvious correspondence between the hardware for the state generator logic and the algorithm it represents.
This is true of D flip-flops, and even more true of JKs. Every change in the algorithm, no matter how minor, requires a fresh design of the next-state combinational logic. The traditional approach violates our goal of clarity in design.
Next-state generation is the standard implementation process associated with ASM charts, and we would like both the synthesis and the analysis of our state generators to be as straightforward and mechanical as possible. The next technique, while using the same structure for expressing states with encoded state variables, differs dramatically in the method by which the next-state combinational logic is generated.
FIG. 11. Traditional synthesis of the ASM in FIG. 9.
The Multiplexer Controller Method for ASM Synthesis
Here is a simple method of synthesizing the combinational logic for any controller.
The method has several desirable attributes:
(a) It produces a design having a direct correspondence with the algorithm that generated it.
(b) It is a standard method that can be applied to any ASM chart.
(c) It forces the designer to complete the ASM chart before the hardware is constructed.
(d) It is easy to learn.
The design progresses in the traditional way through the state assignment: we select an appropriate number of D flip-flops for the state variables and we make an arbitrary assignment of binary values to the states in the ASM chart.
Now consider the model of state generation in FIG. 10. Given the code for the present-state address and the status variable inputs, we must produce the code for the next state.
The traditional way is to use gates to compute the next-state code. An alternative way is to look up the next-state code in a table. Rather than compute each bit of the next-state code, in this simplified method we will look up the value of each bit. In Section 3, we described the multiplexer as our table-lookup building block.
The multiplexer controller method uses a mux for the input to each state flip-flop. Each mux produces the new input to its state flip-flop. The assembly of multiplexers, each providing the input to its respective flip-flop, yields the code for the next state. We choose a multiplexer wide enough to have an input for each state of the ASM. The present-state address code, which is the ordered output of the state flip-flops, feeds into the select inputs of each multiplexer, where it selects the mux input appropriate for the present state of the system.
Our design task is to see that for each present state the mux inputs provide the 1 or 0 necessary to produce the next-state code. In effect, we have, for each present state, a table entry that produces the code for the next state.
Let's use the multiplexer controller method for building the state generator for the simple ASM in FIG. 9. A four-input multiplexer produces the input to each state flip-flop Band A. We prepare TABLE 1, showing the conditions for reaching any possible next state from each present state. For present state 0 (state P), look at the column for the next value of state variable A. If the ASM is in state 0, the A-mux must produce truth (1) only when Z is true. Thus the equation for this multiplexer input is
MUXA(O) = Z
For present states 1, 2, or 3, the table shows that the A-mux inputs are always false; we always produce a 0 for the A bit of the next-state code from these states.
TABLE 1. STATE TRANSITION DATA FOR THE ASM IN FIG. 9
FIG. 12. A multiplexer controller for the ASM in FIG. 9.
FIG. 13. A more complex ASM.
Now consider the B-multiplexer. In present state 0, the required expression for the input is
MUXB(O) = Z + Z = T
In the remaining states 1, 2, and 3, the B-mux inputs are again all 0, as they were in the A-mux. FIG. 12 shows the resulting state generator. Equations for the outputs CMD1 and CMD2 are the same as in the traditional method: Eqs. (1) and (2).
This was a fairly simple illustration. With some familiarity with the multiplexer controller method, you could have read off the mux inputs directly from the ASM chart without using the table. Let's do a more complex example-the ASM in FIG. 13. This four-state machine will require two state flip-flops B and A. Again, two four-input multiplexers will provide the proper table-lookup environment for the inputs of the state flip-flop.
TABLE 2 contains the ASM chart information in a convenient form for the preparation of the multiplexer inputs. From the table, we derive these equations
MUXA(0) = X Y + X = X + Y
MUXA(1) = F
MUXA(2) = F
MUXA(3) = Z
MUXB(O) = X-Y + x = x + y
MUXB(1) = W
MUXB(2) = F
MUXB(3) = Z-X+Z = X+Z
TABLE 2. STATE TRANSITION DATA FOR THE ASM IN FIG. 13
FIG. 14 shows the completed state generator for this ASM.
FIG. 14. A multiplexer control for the ASM in FIG. 13.
This example has four outputs-two unconditional and two conditional.
We may write equations directly from the ASM chart:
OUT1 = P (eqn. 3)
OUT2 = Q (eqn. 4)
OUT3 = Q W (eqn. 5)
OUT4 = S Z X (eqn. 6)
To make use of these equations, we need implementations of the logic variables P, Q, and S, which correspond to states P, Q, and S, respectively. We may expand these logic variables in terms of the state variables B and A, as we did in the earlier example. A more systematic, and therefore usually better, technique is to use a decoder with inputs B and A to produce the individual logic variables for each state. The outputs of the decoder will be, in order, P, Q, R, and S. The generation of Eqs. (3) through (6) for the ASM outputs proceeds easily, using standard mixed-logic techniques. You will see examples of this use of a decoder at several points in this book.
Comments. The multiplexer controller method provides a systematic, easily documented, and easily altered way of implementing ASM controllers.
We prefer this method to the traditional method in virtually every case. How big a system will this method handle? The number of multiplexers, being the same as the number of state flip-flops, increases only as the logarithm of the number of states, whereas the size of each mux increases linearly. For example, systems with five to eight states require three 8-input multiplexers, nine to sixteen states require four 16-input multiplexers, and 17 to 32 states must have five 32 input muxes. Commercial muxes with up to 16 inputs are available; we may fabricate larger multiplexers from smaller components, using the methods in Section 3. In our experience, for systems of 17 to 32 states, the method is practical but unwieldy. For systems of up to 16 states, the mux method provides a comfortable approach.
The traditional method, using either D or JK flip-flops, becomes a pile of spaghetti beyond eight states and gives none too clear a result in smaller systems.
Most of the systems we wish to handle with the methods of Part II have fewer than 17 states. What do we do about the occasional system with more states? Our last method of state generation provides a way of extending the useful range of hardware state generators to more states than the mux method will handle easily. NEXT>>
Related Articles -- Top of Page -- Home