AMAZON multi-meters discounts AMAZON oscilloscope discounts
Developing the Algorithm
FIG. 20 is a possible ASM for our lock problem. The essence of this chart is to test each fixed bit of the combination in. a separate state and end up in either a correct state or an error state. Some states loop back to themselves while waiting on a human action. During the looping, these states must detect any erroneous actions and also any attempt to reset the system. For example, while the loop in state BIT 1. OK waits for the READ signal, it must provide loop exits for an erroneous TR Y signal and for a RESET signal. (Why is this important?) State BIT3.0K, which paves the way for a success, loops on TR Y, and must recognize a READ signal as an error.
This is a fairly boring ASM chart. The only interesting part is the state assignment. Since so many paths lead to an error state, we give state BAD a state assignment of 000. The multiplexer controller uses gates to evaluate those paths that lead to state assignments containing 1 'so By making the largest number of paths lead to a state with all O's, we can sometimes simplify the multiplexer inputs.
This ASM chart has two objectionable features:
(a) The combination is built into the chart by the bit tests. Altering the bit pattern of the combination requires a tedious reexamination of the ASM chart and modification of the gate structure of the control mux system.
Changing the number of bits in the combination is a major undertaking distinctly poor design.
(b) Tests of the reset signal appear in every state and clutter up the ASM chart.
Let's rework the algorithm to try a more elegant approach.
FIG. 20 An ASM for a primitive combination lock.
An Elegant Combination Lock ASM
The reset tests in FIG. 20 are correct but unpleasing. A reset is often a cataclysmic action that is intended to throw the system into a known state, regardless of the present state and independent of the ASM's clocking. Although our intended reset action is not quite this dramatic, the result is much the same.
Any time the operator hits Reset, the machine should go to the initial state and start the lock algorithm anew. Nothing needs to be saved in the ASM. In this problem, we may make one of our few standard uses of asynchronous signals: treat the reset as an asynchronous event that will blast the ASM into the initial state. By doing this, we can remove the synchronous tests of RESET and replace them with a master asynchronous entry to the initial state by means of the signal RESET*.
If we intend to reset the state flip-flops asynchronously, we must choose a state assignment that lets the initial state conform to the results of the reset.
Usually, we assign 000 to the destination of the asynchronous reset.
Meeting the other objection, the fixed nature of the combination, requires a more subtle and more significant answer. First, we will get rid of the wired in combination. Instead of branches such as
we could compare the current value of the toggle switch with a reference value supplied by the architecture and not by the ASM chart itself. If we call this reference value for a particular bit REF, then the ASM chart would contain
FIG. 21 An ASM for an elegant combination lock.
Now, by altering the reference bits we may change the lock's combination easily.
Next, we will put the bit test in a loop. The number of bits in the combination will determine when the loop terminates. Clearly, a 3-bit lock is not very safe, since the probability of opening it in one try is 2 - 3 = i. It would be much nicer to have a 10-bit lock, which would reduce the probability to 1/1024. Our modification will easily support such a change.
The new ASM, incorporating the proposed changes, is shown in Fig. 21. This is a much better algorithm. By coincidence, it has the same number of states as before, yet it is able to handle a combination of M bits as easily as three. Furthermore, we have regularized the branch out of the bit test-branching occurs only when the input BIT is not equal to the reference bit. This systematic feature allows us to embed the test inside a loop.
We have to pay something for the increased power of this algorithm:
(a) We now need a loop counter.
(b) We now need a table of reference bits-in other words, the combination.
Can we find hardware for this algorithm? The counter is no problem, since it is one of our standard building blocks. For example, the 74LS163 Four-Bit Programmable Binary Counter is able to support clearing, loading, and counting, and can handle lock combinations with up to 16 serial bits. The combination lookup table could be in a ROM (read only memory), a PLA (programmable logic array), or a multiplexer. (Remember the discussions of building blocks in Sections 3 and 4.) The multiplexer is the cheapest solution for short tables.
We use CNT as the table index to find the current bit. For a combination of 10011110, the table lookup suggests an eight-input multiplexer:
Notice the great similarity of our hardware algorithm in FIG. 21 to a flowchart loop in software programming. All the ingredients are there; initialization of the loop counter, the loop body, the test of the loop counter, and the modification of the counter. Although we must refrain from drawing too close an analogy with software, it is gratifying to find, in good hardware design, many of the same concepts as software.
It is worthwhile considering the effect of placing the loop-counter incrementing step in different locations in the ASM. What is wrong with putting the counter modification operation into state LOOP? (Hint: The loop has an embedded loop.) Why not put the INCR state at the head of the loop instead of at the end? (Hint: Consider the table-lookup's indexing.) Architecture
Normally, the operator of a digital system will follow the progress of the work by observing status responses such as lights or motor noises; the operator can thus determine when to perform various actions. In our combination lock, we wish the machine to be quiet, yielding no information except lighting an Open light following a successful Try. If the machine's clock is faster than human reactions, we may avoid "handshakes" between the operator and the machine, since the machine will always be ready to process the operator's input.
The clock speed of our lock machine may be as slow as 0.2 sec or 5 Hz.
If we are driving our machine with batteries, for instance in a car, we would use an oscillator of perhaps 100 Hz for our clock. (We discuss this technology in Section 12.) Our ASM chart tests the TRY and READ signals, which originate from debounced pushbutton signals TRY* and READ*. We will pass these signals through a single pulser to achieve synchronization and to assure that only a single ASM action results from the push of a button. The single-pulser outputs are TR Y and READ. The bit-entry switch for the serial combination may be a plain toggle switch BIT. (Why does it not need to be debounced or synchronized or single-pulsed?) The specifications call for a Reset pushbutton with the output RESET*. The sole output of the machine is a light, Open, so we include a black box in the architecture to drive the lamp.
Buried within our hardware, inaccessible to the operator, will be a binary counter with output CNT to control the loop count. A 74LS163 Four-Bit Programmable Binary Counter will do nicely; CNT will then consist of 4 bits, CNT3 CNTO. The architecture will also contain a multiplexer, with an output REF(CNT), of sufficient size to provide an indexed table lookup for the bits of the combination.
For our illustration, let's use an 8-input mux such as the 74LS151. We do not really need to commit ourselves to particular chips this early. All we need at this point is a knowledge of what operations will be easily possible with each building block.
Last, we may include a black box with output (CNT==M) and inputs CNT and M to determine when the loop count CNT has reached the terminal value
M. Since the loop starts with a count of zero, M must be one less than the number of bits in the combination. We must build this black box. If we think it unlikely that the number of bits in the combination will change, we could implement the output (CNT=M) with a simple gate. For example, in an 8-bit combination, M would be 7, and we would have
mT3H~ CNT2.H (CNT:M) L CNT1.H . CNTO.H
However, a more elegant approach is to allow the black box's input M to vary. Then we would use one of our standard building blocks, an arithmetic magnitude comparator such as the 74LS85 Four-Bit Magnitude Comparator.
With 4-bit inputs CNT and M, this circuit can provide a signal (CNT=M) when the input values are identical. We could then complete the architecture by including assemblies of tiny toggle switches for M (4 bits) and for the combination (8 bits). We would hide these switches inside the combination lock machine, away from prying eyes.
FIG. 22 is the architecture of our elegant combination lock.
Implementing the Control
There are few outputs in our ASM, and the equations are simple:
CNT(CLR) = INIT CNT(COUNT) = INCR OPEN = OK
All the ASM test inputs are available in the architecture except for (BIT=REF(CNT)). How do we determine if one arbitrary logic signal is equal to another? In Section 3, we introduced the logic function COINCIDENCE, which produces truth if and only if its two inputs are the same. We may express the bit test as
(BIT=REF(CNT)) = BIT 0 REF(CNT)
Now for the state generator. We use the multiplexer controller method and the state assignment given in FIG. 21. The destination of the ASM asynchronous reset has state assignment 000 to allow easy use of an asynchronous clear input on the state generator flip-flop assembly. Table 2 contains the state transitions required by our ASM. The six states require a 3-bit code. A 4-bit D register with asynchronous clear, such as the 74LS175, and three 8-input multiplexers, for example the 74LS151, will support the structure.
To provide the three state signals INIT, INCR, and OK required by the ASM output equations, we may use a 74LS42 Four-Line-to-Ten-Line Decoder.
This one-chip solution is more convenient than constructing the three signals from gates.
FIG. 22 The architecture for an elegant combination lock.
FIG. 23 is the state generator's structure. FIG. 24 shows implementations
of a few of the mux inputs. You should draft the rest.
DESIGN EXAMPLE 7: THE BLACK JACK DEALER
As our last example in this section, we will design a machine to simulate the dealer's actions in a blackjack game. Blackjack is a familiar card game involving a dealer and one or more players. The players can exercise their judgment but the rules specify what the dealer will do with each new card he receives.
Table 2 ELEGANT COMBINATION LOCK ASM STATE TRANSITIONS
FIG. 23 A state generator for an elegant combination lock.
FIG. 24 Some control mux inputs for an elegant combination lock.
The Rules of Play for the Dealer
The cards have values of 1 (ace) to 10 (10 and face cards). An ace may have the value of 1 or 11 during the play of the hand, whichever is advantageous.
The dealer deals himself cards one at a time, counting ace as 11, until his score is greater than 16. If the dealer's score does not exceed 21, he "stands," and his play of the hand is finished. If the dealer's score is greater than 21, he is "broke" and loses the hand. The dealer must revalue an ace from 11 to 1 to avoid going broke but must then continue accepting cards ("hits") until the count exceeds 16.
Stating the Problem
These rules understood, we may state our hardware design problem. With a human operator to present cards to the Black Jack Dealer machine, play the dealer's hand to produce Stand or Broke.
Digesting the Problem
We will call the hardware device Dealer. The basic questions we might ask in our first stab at an architecture are: How will the operator present cards to Dealer? How will the operator know what the result of each card is? We can see that the operator interacts closely with the machine:
(a) Dealer must signal the operator when to deal a new card.
(b) The operator must signal Dealer when the new card's value is ready for processing.
(c) Dealer must tell the operator if Dealer stands, went broke, or if the hand is still in progress.
(d) When Dealer stands, the operator must be able to see the point value of Dealer's hand.
These thoughts suggest that an important aspect of Dealer's design is the interaction between the machine and the human. Assuming that the operator knows the binary number system, we choose a set of four toggle switches to hold a card value of from 1 to 10 in binary. These toggle switches will act as a register for the input data. A set of five lights is a simple way to display Dealer's score, which cannot exceed 21. To control the interaction, we can give the machine a set of status lights: Hit, to tell the operator when to enter a new card for Dealer; Stand and Broke, to inform the operator of the final results of the hand. We could provide a New.Game status light to show when to begin a new hand, but this is unnecessary, since either Stand or Broke must be signaled when the previous hand is complete, and thus the operator knows when a new game may begin without a special New.Game light.
We must not forget to give the operator a way to tell Dealer when to process a card; therefore, we will specify a pushbutton switch Card.Ready which the operator can press.
At this point we have a fairly good idea of the interface between Dealer and the human operator. FIG. 25 shows the general plan. This is an important step in our design, for at this point we may go to our potential operators and describe how they will use the Dealer machine. Presumably, the operators don't much care what Dealer is like inside, but they will be interested in the operating instructions-the user's manual. Talking to users at this stage in the design can help avoid agonizing redesign later, in case we have misunderstood the problem.
FIG. 25 The Black Jack Dealer's interface with the operator.
Most of the architecture is not yet specified-only the interface signals.
Now we can begin work on the control algorithm. To gain a clear understanding of the problem, it is useful to write a "software" version of the algorithm. This suppresses most of the machine details, including the detailed state timings that we must eventually specify. If we don't understand the problem at an operational level, we surely cannot build a correct machine! Here is a high-level statement of the dealer's algorithm. The variables have obvious meanings, except for acellflag, to remember if the algorithm has valued an ace as 11 points.
Operational Algorithm for the Black Jack Dealer:
A1: (*prepare to start a new game*) score := 0; acellflag := false; stand := false; broke := false;
A2: (*make a hit*) accept a card; score := score + card value; (*check for ace*) if card = ace and acellflag = false then
{score := score + 10; acellflag := true}
A3: (*check for hit*) if score --> 16 then goto A2 else (*check for stand*) if score --> 21 then
{stand := true; display score; goto AI} else (*check for broke*) if acellflag = true then
{score := score - 10; acellflag := false; goto A3} else (*indicate a broke*) {broke := true; goto AI}.
Initial ASM for the Black Jack Dealer
With the operational algorithm as a guide, we may propose a hardware algorithm, using the ASM notation. As usual, our design will be synchronous, running from its own internal clock at a speed independent of the human operator's actions. As we develop the ASM, we will gain insight into the internal architecture required by Dealer. FIG. 26 is a first attempt to describe an ASM for Dealer.
The ASM assumes the following architectural elements:
(a) Memory flip-flops for the HIT, STAND, and BROKE signals.
(b) A register to hold the current card value.
(c) A register to hold SCORE.
(d) A flip-flop for ACEIIFLAG.
(e) A black box to add, subtract, and clear the SCORE.
(f) A black box to report if CARD = ACE, if SCORE> 16, and if SCORE > 21.
Reducing the Number of States
Our ASM has quite a few states, and you may wonder if this is desirable. States are the fundamental element of a hardware control algorithm, but they may have two undesirable side effects:
(a) Each state requires a clock cycle to execute.
(b) In a hardwired design such as this, excess states can enlarge the state generator's circuitry.
In the Black Jack Dealer machine, neither of these objections to states is apt to be serious. It is likely that the human operator is much slower than the clock, so superfluous clock cycles will not cause difficulty. Also, we have straightforward methods of developing state generators from ASM charts of any reasonable size.
Nevertheless, as practice in dealing with more complex and demanding designs, we will attempt to reduce the 10 states to a smaller number. Our basic technique is to introduce conditional outputs into an existing state, to replace the unconditional outputs of a separate state. States are candidates for collapse into the previous state if the state's activities (particularly its outputs) do not need to follow the activities of its predecessor state sequentially. Such state saving moves do not necessarily save hardware. Although the number of flip flop memory elements for states may decrease, the command output logic usually becomes more complex. Experience shows that a moderate effort to save states is worthwhile, as long as we maintain clarity in our design.
FIG. 26 A primitive ASM for a Black Jack Dealer, with too many states
and an error.
FIG. 27 Converting a four-state ASM into a one-state ASM.
FIG. 28 Equivalent formulations of a cyclic process of N + 1 elements.
--- (a) (N + 1 ) -state cyclic ASM (b) One-state ASM with counter in architecture
Another technique to reduce the number of states is to create new test inputs to direct a single state down several new paths. We encountered this technique in the single-pulser example at the beginning of this section. An extreme example would be to place the entire ASM into a single state: take any ASM and its set of state variables and create a new single-state ASM, using the old state variables as test inputs. FIG. 27 is an example. Obviously, this recasting of the algorithm, although technically equivalent to the original four state version, is neither as clear nor as meaningful. The test inputs B and A are artificial and have no real meaning in the algorithm. Since we want maximum clarity, we reject this particular single-state ASM. There are occasions when saving states through the introduction of new test inputs is helpful. An example is a purely sequential ASM-a cycle of states with no tests, as in FIG. 28a.
A simple state generator uses a binary counter, which counts up to the maximum state value and then resets to o. On occasion, we may increase the clarity by making the counter a part of the architecture, as in FIG. 28b. In both designs, the hardware is the same. Choose the algorithm that seems clearer for your problem. Design Examples 3 and 4 in this section also illustrate this point.
In general, use moderation in eliminating states, having increased clarity as your goal. In the Black Jack Dealer ASM, we may easily incorporate the outputs of states LIGHT.STAND, LIGHT.BROKE, and CANCEL.ACE=l1 into conditional outputs within state ANALYZE. We may also eliminate the NEW. GAME state.
Errors in the Algorithm
The ASM in FIG. 26 contains two errors. Can you find them? They are both in the interface with the operator, and you have seen both earlier in this section.
Consider the Card.Ready button and its use. First, we assume by now that you will have debounced the CARD.READY signal. (We always debounce mechanical switch signals that are used to provide test inputs in our ASM.) But CARD.READY changes with the operator's actions and is not synchronized with the ASM's clock. In our ASM, we should therefore label this signal CARD.READY* (* for asynchronous). We hope you noticed this error, since asynchronous inputs are a commor; problem and you must be alert to them. Our treatment of this asynchronous test input is immediate and ruthless. Without pausing to investigate whether this asynchronous signal will cause problems, we eliminate it. We synchronize CARD.READY* with a D flip-flop operating synchronously with our ASM. In so doing, we add an element to our architecture. Call the output of the flip-flop CARD.RDY.SYNC. It is this new synchronized signal that the ASM tests in the WAIT .FOR.CARD state.
FIG. 29 A segment of an ASM with a transition race.
Races, Again
Let's again explore the problems introduced when an ASM tests an asynchronous input. Assume that we have allowed the CARD.READY* signal to remain in the ASM and that we have made an encoded state assignment. FIG. 29 is the relevant part of the ASM. In state 0000, when CARD.READY* = F, the state generator logic will be preparing to change the state variable C from 0 to 1. If CARD.READY* becomes true in state 0000, the state generator logic will switch C back to 0, and B and A to 1. If CARD.READY* changes to true very close to the transition point for leaving state 0000, the inputs to the state flip flops will be changing when the clock edge occurs, and the resulting outputs of flip-flops C, B, and A are unpredictable. The next state might be any of eight possibilities: 0000, 0001, 0010, 0011, 0100, 0101, 0110, or 0111! In this particular example, states 0000, 0011, and 0100 would be tolerable, but the rest are clearly erroneous. The situation is a transition race, and you must eliminate it.
By modifying our ASM chart in a straightforward way (but retaining the asynchronous CARD.READY* signal), we can illustrate another type of race, the output race. If we manipulate HIT in conditional outputs in state WAIT.FOR.CARD instead of in separate states, we have the partial ASM in FIG. 30. Should CARD.READY* change from F to T near the clock edge, not only is the next state in doubt, but since the input to the HIT flip-flop is changing from T to F, the HIT output is also uncertain. We may reach the GET.CARD state successfully, but the Hit light may still be on! The output race is characteristic of outputs that are conditional on asynchronous test inputs. You must eliminate these races.
FIG. 30 A segment of an ASM with an output race.
There is a welter of traditional and complex techniques for dealing with the problem of races by manipulating state assignments. The straightforward way, as you know, is to eliminate the cause of the problem! If all test inputs are synchronous with the ASM clock, there can be no races. It is tempting to study your particular ASM to see if a particular asynchronous input can cause trouble. Usually, this is wasteful, mind-cluttering activity. Synchronize the input and move ahead.
This sweeping simplification works because the ASM's action depends on only one (synchronized) input at a time. If the control of the ASM requires the simultaneous synchronization of more than one asynchronous input, no method will produce reliable results. This is bad design of the external interface. Modern practice requires that all relevant inputs be stable (unchanging) at the time the single status signal announces that an event is to occur. For our Black Jack Dealer, we require that the card switches be set prior to the single CARD.READY* announcement.
Process Synchronization
Our problems are not quite over. Suppose the operator presses the Card.Ready button. What happens if, as is likely, the ASM completes its actions in response to the CARD.RDY.SYNC signal and returns to the WAIT.FOR.CARD state before the operator has released the pushbutton? Dealer will process the same card again, since CARD.RDY.SYNC is still true. This is the problem studied in this section's first example, the single-pulser. Because of its importance and the subtlety of some of the implications, we will discuss the subject again, from a different perspective.
Handshakes. The problem is a failure to complete a full handshake between the operator and the dealer. A full handshake is an important mechanism for controlling the activities of two independent but cooperating processes. Frequently one device (A) must issue a request for action to another device (B). Since the speed and state of device B are unknown to device A (and vice versa), we need a general method by which device A can request action of device B and can be certain that device B has recognized the request. The sequence of events in the full handshake is: (1) Device A senses that device B is not still acknowledging a previous request and requests an action (device A extends its hand). (2) Device B senses the request and acknowledges receipt of the request (device B extends its hand). (3) Device A senses device B's acknowledgment and drops its request (device A drops its hand). (4) Device B senses that device A has recognized device B' s acknowledgment and drops its acknowledgment (device B drops its hand). The success of the handshake depends heavily on the sequence of events but does not depend at all on the duration of any step. In our Black Jack Dealer, the operator and Dealer must shake. hands in the process of requesting and entering a new card. HIT requests a new card; CARD.READY* is the operator's acknowledgment of the request. The desired sequence is:
(1) Dealer senses that the (synchronized) CARD.READY signal is false, and asserts HIT, keeping HIT true at least until CARD.READY goes true.
(2) Operator sees the Hit light on, and (after preparing a new card) presses the Card.Ready button, keeping it on at least until the Hit light goes off.
(3) Dealer detects that the (synchronized) CARD.READY signal is true, and drops HIT (and proceeds to process the new card), keeping HIT false at least until CARD.READY goes false.
(4) Operator sees the Hit light off, and releases the Card.Ready button, keeping it released (and hands off the card switches) at least until the Hit light goes on.
The Single-Pulser Revisited
What is wrong with our preliminary design? The operator's role appears correct (we would, of course, fully describe the rules in the user's operating instructions). The Dealer ASM performs step (1) properly, and most of step (3), but fails to keep HIT false until it detects that the operator's button is released. Dealer is failing to observe the dropping of the operator's hand. We can recast this requirement by saying that Dealer must respond once and only once to each action of the operator. Earlier in this section you studied several ways of describing and handling this common phenomenon of "once and only once." Here, let us express the solution yet another way. We incorporate the one-state single-pulser algorithm (FIG. 3) directly into the ASM, so that we may add our own specialized conditional outputs to the test branches. You have already seen that we will have a CARD.RDY.SYNC flip-flop in the architecture; to accommodate the single pulser we will include another flip-flop with output CARD.RDY.DELAYED. Then in the control algorithm, we explicitly test the values of these two flip-flops in order to isolate one and only one recognition of the operator's button push. The handshake signal HIT arises from a conditional output whenever the pushbutton is up. The relevant part of this ASM is in FIG. 31.
FIG. 31 A specialized single pulser for the Black Jack Dealer.
This algorithm solves the difficulty of accomplishing the full handshake: HIT will only be asserted in the Wait.for.Card branch of state GET. If the button is up, Dealer is happy to request a new card in state GET. Whenever GET detects that the button is pressed, HIT will go false. The first time GET sees the button pressed, the ASM will process anew card. If control returns to GET while the button is still down, the algorithm simply waits (with HIT still false) until the operator releases the button.
FIG. 32 The final ASM for the Black Jack Dealer.
The Final ASM for the Black Jack Dealer
The algorithm for the Black Jack Dealer now seems to be developing nicely.
We have found that we may eliminate some of the states in our original proposal without jeopardizing clarity. We have explored in detail the synchronization requirements of certain inputs and the larger handshaking requirements between the operator and Dealer. FIG. 32 is the improved ASM for Dealer. In this figure, as in FIG. 13, the labels on the conditional output boxes describe conditional output terms-logic terms useful in developing a systematic implementation of a complex ASM. The conditional output terms are not state names; they merely represent positions within their parent state. For instance, the circled label CD on the conditional output in state GET is a shorthand for the label GET. 1. During the implementation of the control algorithm, we will derive equations for the logic variable GET.1 as well as each of the other terms.
FIG. 33 The functional architecture of the Black Jack Dealer.
The Final Architecture of the Black Jack Dealer
FIG. 33 is the functional architecture of Dealer. Along the way, as we developed a more detailed understanding of the problem, we made certain modifications to the original architecture; these are reflected in the figure. The significant modifications or elaborations include the following:
(a) Since the operating procedures stipulate that the card switches are stable throughout the time that Dealer processes the card (in other words, as long as HIT is false), we do not need a separate register to hold the current card value; the card switches themselves will suffice.
(b) The ASM manages the HIT signal directly, without a flip-flop to preserve its value across states.
(c) Our treatment of CARD.READY* introduces two new flip-flops, the components of the single pulser.
(d) We have elaborated on the black box for preparing the input to the SCORE register. There are four operations that modify SCORE: clearing SCORE to 0, adding CARD to SCORE, adding + 10 to SCORE, and subtracting + 10 (adding - 10) from SCORE. A 5-bit adder can add the appropriate value to SCORE if we can select the proper value. You know how to manage selection, so you will probably guess that we will use multiplexers. The important point to realize at this stage is that we can select one input from several, without worrying about the exact chips. With SCORE as one input to the 5-bit adder and the other input selected by a selector black box, the circuit is nearly specified. A judicious choice of the chips for SCORE should allow us to clear this register separately from the register-load operation. On this basis, the original nebulous black box has separated into three components: an adder building block, a selector building block, and a control input for clearing the SCORE register building block.
Surely now we will sit down and define the exact chips to support the dealer architecture. This would be a reasonable step to take at this time, but as a further illustration of the power of the methods you are learning, let's see how far we can carry the implementation of the control algorithm without specifying the exact chips in the architecture.
Implementing the Control Algorithm
It is the task of the ASM to generate the necessary commands (outputs) to control the architecture and to provide the outputs to the external world. In FIG. 34 we show how the ASM controls the architecture. The inputs and outputs of the ASM are still specified at a somewhat abstract level. We will develop the logic equations for each signal, prior to selecting chips. Such a development depends on our understanding of how to convert building blocks into chips, just as implementing a software flowchart requires a knowledge of the programming language. As we have stressed repeatedly, the goal is to think of the problem, not of the chips, for as long as possible.
Our design now involves two tasks: Implementing the flow of the ASM (the state generator), and implementing the outputs (commands). First, we will define the conditional output terms, which will be useful parameters for many of the remaining equations. Reading directly from the ASM, we have the following logic equations
GET. 1 = OET·CARD.RDY.SYNC
GET.2 = GET·CARD.RDY·SYNC·CARD.RDY.DELAYED
GET.3 = GET.2-(STAND + BROKE)
TEST.1 = TEST-SCOREGT16-SCOREGT21
TEST.2 = TEST-SCOREGT16-SCOREGT21-A'=CE=1""1r; FL-;-A"TG~
= TEST-SCOREGT21-ACEllFLAG (by observation)
TEST.3 = TEST-SCOREGT16-SCOREGT21-ACEllFLAG
= TEST-SCOREGT21-ACEllFLAG (by observation)
FIG. 34 The functional control of the Black Jack Dealer.
Next, we implement the state generator. We again choose a multiplexer controller, leaving the one-hot method as an exercise. FIG. 32 shows a suitable (arbitrary) state assignment. Four states require two flip-flops for the encoding of the state variables. A four-input multiplexer feeds each flip-flop.
Table 3 is a summary of the ASM state transitions.
Notice the handy use of the conditional output terms, which results in a simplification of the control multiplexer inputs and achieves a savings of hardware while increasing clarity. For example, the full condition for moving from state GET to state ADD is
FROM.GET.TO.ADD = CARD.RDY.SYNC-CARD.RDY.DELAYED
Table 3 STATE TRANSITIONS IN THE BLACK JACK DEALER ASM
But conditional output term GET.2 is just this expression ANDed with GET. Producing the conditional output in the oval at position GET.2 will require that we implement the conditional output term GET.2, so we know that this term is available in the final circuit. Appending GET to the expression for FROM.GET.TO.ADD has no logical effect, since the expression already implies that the ASM is in state GET. It is therefore permissible, and convenient, to use the conditional output terms as required to develop the state generator logic.
As usual, it is convenient to decode the state flip-flop outputs, producing in this case the four state terms GET, ADD, USE, and TEST. These terms complete the requirements of the logic equations developed thus far.
As a last step in the ASM synthesis, we derive the output signals. Reading almost directly from the ASM, we have
HIT = GET.1
STAND(SET) = TEST.1
STAND(CLR) = GET.2
BROKE(SET) = TEST.2
BROKE(CLR) = GET.2
A CEllFLAG(SET) = USE
ACEllFLAG(CLR) = GET.3 + TEST.3
SCORE(LOAD) = ADD + USE + TEST.3
SCORE(CLEAR) = GET.3
Deriving the controls for the adder selector requires one further set of parameters. We need 3 data inputs to the selector: CARD, +10, and -10. Each data path is 5 bits wide, so five 4-input multiplexers will serve nicely as the basis for this selector, each mux being controlled by the same select signals, S1 and SO. We shall assign + 10 as the input to the O-position of the multiplexers, -10 to the I-position, and CARD to the 2-position. Our task is to derive logic equations for the selector controls S1 and SO. With these specifications and the ASM chart, we develop Table 4. From this tabulation we easily derive the select input equations:
S1 = ADD
SO = TEST.3
Table 4 ADDER INPUT SELECTION FOR THE BLACK JACK DEALER
We now have equations for all the control signals, still without a commitment to specific chips. The last step, hopefully straightforward and bug-free, is to select chips and draft the final circuit diagrams for the architecture, state generator, and output signals. Here is the first point at which voltage enters our design! Using mixed-logic drafting conventions, you can implement the logic equations with whatever gates are handy. JK flip-flops are an obvious choice for the storage elements for those signals requiring controlled setting and clearing: STAND, BROKE, and ACEllFLAG. As you learned in Section 4, you may use either the J or the K input to represent the set condition.
Summing Up
This completes the Black Jack Dealer problem. The methodology is important and well worth your close study. The documentation of this design should include most of the figures and tables developed in this exercise that relate to the final design. Think what a help this high-level documentation would be to you if you were presented with a real, nonfunctioning circuit and told to get it running or to modify it in some way. Once again, note that although our thinking was conditioned by our knowledge of the available types of integrated circuits and their characteristics, it was only at the end of the design that we introduced actual voltages and chips.
RESOURCES
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. Contains numerous system-level examples of design.
GLASSER, LANCE A., and DANIEL W. DOBBERPUHL, The Design and Analysis of VLSI Circuits. Addison-Wesley Publishing Co., Reading, Mass., 1985.
HILL, FREDERICK J., and GERALD R. PETERSON, Digital Logic and Microprocessors. John Wiley & Sons, New York, 1984.
HILL, FREDERICK J., and GERALD R. PETERSON, Introduction to Switching Theory and Logical Design, 3rd ed. John Wiley & Sons, New York, 1981.
HWANG, KAI, Computer Arithmetic-Principles, Architecture, and Design. John Wiley & Sons, New York, 1979.
LALA, PARAG K., Fault Tolerant and Fault Testable Hardware Design. Prentice-Hall International, London, 1985.
LSI Databook. Monolithic Memories, 2175 Mission College Blvd., Santa Clara, Calif. 95954. PALs, memory products, arithmetic units, and system building blocks.
MEAD, CARVER, and LYNN CONWAY, Introduction to VLSI Systems. Addison-Wesley Publishing Co., Reading, Mass., 1980. The first VLSI textbook.
Memory Components Handbook. Intel Corporation, Literature Department, 3065 Bowers Avenue, Santa Clara, Calif. 95051.
MYERS, GLENFORD J., Digital System Design with LSI Bit-Slice Logic. John Wiley & Sons, New York, 1980.
WAKERLY, JOHN F., Logic Design Projects Using Standard Integrated Circuits. John Wiley & Sons, New York, 1976. A good source of laboratory projects.
WESTE, NEIL, and KAMRAN ESHRAGHIAN, Principles of CMOS VLSI Design: A Systems Perspective. Addison-Wesley Publishing Co., Reading, Mass., 1985.
QUIZ
1. Show that any ASM may be expressed as an ASM with only one state. Why do we not do away with state generators by always designing with single-state ASMs? Discuss the advantages and disadvantages of this approach.
2. Using a 60-Hz periodic logic signal, produce a signal that can serve as a I-Hz clock.
3. Although we find that we must debounce manual control switches, we usually do not need to debounce manual data entry switches. Why?
4. Build a fOUf-state ASM that emits one of two BCD number sequences, depending on the value of a control variable NINESCOMP. Each sequence has a cycle of fOUf digits: When NINESCOMP = F, the sequence is 0,1,2,3,0,1, ... . When NINESCOMP = T, the sequence is 9, 8,7,6,9,8, ... .
5. Exercises 1-36 and 2-32 deal with the seven-segment numeric display. Assume that the display integrated circuit requires discrete signals for each segment a through g. Build a fOUf-state ASM to repeatedly display the first four prime numbers in proper sequence: 2, 3, 5, 7, 2, 3, 5, ....
6. Using seven-segment decimal display chips, design the two-digit "second" display of a digital clock. The clock must cycle continuously from 00 through 59, except when a signal from a pushbutton forces the display to 00. Assume that a 1-Hz synchronous clock signal is available.
7. Extend the previous exercise to produce a full 24-hour clock display. How will you set the correct time? (Hint: Commercial LSI digital clock units often provide a speed-up mode, in which the displayed time goes through a complete cycle in less than 1 minute.)
8. Add an alarm feature to the digital clock.
9. Design an implementation of FIG. 1 using the formal one-hot method with no simplifications. Show how this implementation may be rigorously transformed into the circuit of FIG. 2.
10. Implement the system clock of Design Example 2 using a JK flip-flop instead of the D flip-flop.
11. Consider Figs. 6-9 and 6-10 of Design Example 3. Show that if you have DATA* with T = L, the mixed-logic circuit diagram notations change but the hardware remains the same.
12. Implement the traffic-light controller of Design Example 5 with PALs.
13. Add a blinking-light feature to the traffic-light controller in Design Example 5.
Assume that a new BLINK signal is available and that, when BLINK is asserted, the highway lights blink yellow and the farm-road lights blink red.
14. Finish the detailed design of the combination lock in Design Example 6. Produce circuit diagrams suitable for actual construction of the lock's electronics.
15. 10 the elegant combination lock of Design Example 6, we used a 74LS163 counter and a comparator to determine when the proper number of combination digits have been entered (see FIG. 22). Eliminate the comparator by using the two's complement of the count and counting down instead of counting up.
16. Complete the detailed design of the Black Jack Dealer of Design Example 7.
Produce circuit diagrams suitable for construction of the electronics.
17. For the Black Jack Dealer, the initial ASM in FIG. 26 required a flip-flop for the output HIT. Show how the further development of the control algorithm led to the elimination of the HIT flip-flop from the architecture. This is a typical example of the algorithm modifying the architecture.
18. In FIG. 29, state variables C, B, and A are all involved in transition races. Why is state variable D not similarly involved?
19. Binary patterns that differ in exactly 1 bit are said to be a unit distance apart.
Consider an ASM state (the "predecessor") that has branch paths to several "successor" states. (Note that one possible successor is the predecessor state itself.) (a) If all successor states have encoded state assignments at most a unit distance from the predecessor, show that no transition races will arise, even if asynchronous test inputs are present in the predecessor state.
(b) Show that the condition in part (a) is not sufficient to preclude output races.
20. In the Black Jack Dealer, the architecture contains black boxes that produce such signals as ACECARD, SCOREGT16, and SCOREG121. For example, see FIG. 33. These black boxes involve only simple combinational circuits. Why do we choose to use the black boxes during the design process, instead of showing the circuits directly?
21. The ASM for the Black Jack Dealer (FIG. 32) tests several signals (ACECARD, SCOREGT16, SCOREG121) that are generated by combinational logic within ar chitectural black boxes. Since these black boxes are not clocked, how do we know that their outputs are synchronous and therefore suitable for testing in the ASM?
22. Convert the algorithm for the Black Jack Dealer (FIG. 32) into an ASM with only one state. Since such a move simplifies the state generator circuitry, why do we not choose a one-state ASM for the Black Jack Dealer?
23. Define carefully the use of a full handshake to synchronize two independent processes.
Show how the need for process synchronization arises whenever a human operator interacts with a machine. lllustrate these concepts with the Black Jack Dealer.
24. To synchronize events in two cooperating but independent processes, designers have used a variety of techniques, many of which we may describe as "incomplete handshakes." For instance, consider the following incomplete handshake: (1) Device A requests an action (device A extends its hand). (2) Device B senses the request and acknowledges receipt of the request (device B extends its hand). (3) Device A senses device B's acknowledgment and drops its request (device A drops its hand). (4) Device B drops its acknowledgment at any time after asserting its acknowledgment (device B drops its hand). This looks like a "complete" handshake, but there are circumstances in which
the handshake may be incomplete. Draw timing diagrams for the possible behaviors of the request and acknowledge signals. Discuss the effectiveness of the above protocol for the following conditions: (a) Device A is a machine; device B is a human being.
(b) Device A is a human being; device B is a machine.
(c) Both devices are machines.
(d) Both devices are human beings.
25. Implement a one-hot state generator for the Black Jack Dealer.
26. In the Black Jack Dealer example, the signals SCOREGTl6 and SCOREGT21 arise from a comparator architectural element. Write logic equations for these two variables. Show by Boolean algebraic manipulation that the term SCOREGT16·SCOREGT21 reduces to SCOREGT21, thus rigorously demonstrating the validity of the simplifications of TEST.2 and TEST.3 performed "by observation" in the text.
27. Design a synchronous digital circuit with the following properties: Inputs: (a) Two 4-bit binary numbers, A and B, in signed magnitude notation (1 sign bit, 3 magnitude bits). (b) A GO signal from a manual pushbutton.
Outputs: (a) A 4-bit binary number C in signed magnitude notation.
(b) A signal EVEN for a display lamp.
Task: (a) Wait for the GO signal to be asserted.
(b) When GO appears, clear the signal EVEN to false, and load the values on the input lines A and B into two 4-bit registers RA and RB. [Hereafter, (RA) means "contents of RA," etc.] (c) Then, produce an output C in register RC, as follows: If (RA) > (RB), then transfer the quotient of (RA)/2 to RC. If (RA) --> (RB), then transfer (RB) to RC. (d) If (RA) > (RB) and the remainder of (RA)/2 is 0, then assert EVEN; otherwise, EVEN remains false.
(e) Return to step (a) to await another GO signal.
28. Construct an ASM that will turn on a light as the first person enters a room, and turn off the light as the last person leaves. Assume that there is a single door fitted with two photocells that generate TTL-compatible outputs. One photocell is on the inner side of the door and the other is on the outer side. Light beams shine on each photocell, producing a false output from the cell; a true output from a photocell arises when the light beam is interrupted. Assume that once a person starts through the door, the process is completed, and that only one person enters or leaves at a time.
29. Design a versatile timer circuit. The circuit has two input codes: (1) A 3-bit code describing the unit of counting: code 0 = 100 nsec, code 1 p.,sec, code 2 = 10 p.,sec, ... , code 7 = 1 sec.
(2) An 8-bit code describing the number of counts.
Asserting an input signal START will cause the timer to begin counting the specified number of counts, each count being of the specified duration. The only output from the timer is a signal TIMES UP, which becomes false when timing begins and becomes true when the specified interval has elapsed. The timer can time an interval from 100 nsec to 255 sec. Use a 100-nsec clock to drive the timer. Consider using the 74LSl62 decade counter as the basic counting element. Use good synchronous design techniques in determining how to clock and advance the decade counters.
Timers similar to this are available as LSI integrated circuits.
30. A popular microcomputer requires a l-lLsec square-wave clock for normal operation.
Advanced modes of operation for high-speed input-output and for refreshing dynamic RAM require that the inactive (false) portion of the clock be stretched as follows: Normal operations: Inactive clock time = 0.5 ILsec Refresh request (RFRQ): Inactive clock time = 1.0 ILsec Input-output request (IORQ): Inactive clock time = 1.0 ILsec Both requests simultaneously: Inactive clock time = 2.0 ILsec The active (true) portion ofthe clock signal is always 0.5 ILsec. Design a microcomputer clock that responds to RFRQ and IORQ as shown above. The clock output must be free of hazards.
31. In high-speed input-output operations on a microcomputer, the input-output device may assert a signal that will put the microprocessor "to sleep," allowing the input output device to have uninterrupted access to the microcomputer's memory until the transfer of data is complete. If the device is faulty, it is possible to put the processor to sleep for an indefinite period. To protect the processor from such faulty behavior, we may introduce a timer that will issue a "wakeup" signal to the processor after a period of memory inactivity. The timer should conform to these requirements:
(a) The timer should be enabled only when the processor is asleep.
(b) Timing should begin whenever the processor goes to sleep, and upon the successful transfer of each data word between the memory and the input-output device.
(c) While the processor is asleep, if no memory read or write occurs for 10 msec, the timer should assert its WAKEUP signal.
(d) The WAKEUP signal should remain asserted until the processor asserts an acknowledge signal ACK. (e) WAKEUP should be synchronous with the microcomputer system clock, and should be free of hazards.
Design the timer. Use a single-shot for the 10-msec delay. Is the poor stability of the single-shot (about 5 percent) a disadvantage in this application?
32. Repeat Exercise 28, using decade counters to generate the 10-msec delay. Assume a l-lLsec microcomputer system clock.
33. In this exercise, you will design a circuit to resolve conflicts in memory accesses.
Two microprocessors driven by the same system clock share access to a single dynamic RAM. The RAM can complete a memory operation in one clock cycle.
Consider three types of memory request: for dynamic RAM refresh (RFRQ), for microprocessor 1 (CPU1RQ), and for microprocessor 2 (CPU2RQ). Memory request conflicts are resolved as follows: (a) RAM refresh has highest priority.
(b) If both microprocessors simultaneously request memory access, the microprocessor that more recently received memory service has the lower priority.
Each device contending for memory access receives a status signal (RFGNT, CPU1GNT, or CPU2GNT) that specifies when memory access is granted to the device.
Design a device that accepts requests and responds with status signals according to the preceding rules.
34. The stack is a software data structure often implemented in hardware. A stack is an ordered set of elements analogous to a stack of plates in a cafeteria. Only the top element (plate) is accessible. Removal of the top element exposes the next to-top element, which then becomes the top. Addition of an element to the stack causes the former top element to become next-to-top; the added element becomes the top. The operation of adding an element to a stack is called push. The removal operation is called pop. These are the only allowed stack operations. A stack is sometimes called a LIFO (last in, first out) memory.
In hardware, we may implement a stack in RAM or with an array of discrete registers.
(a) Using RAM, design a stack that accepts push and pop operations and properly adds or removes an element from the top of the stack.
(b) Design a small five-element stack using MSI registers.
35. Repeat Exercise 34 for a stack that also provides two status signals: EMPTY: Asserted when the stack contains no elements. Your stack should ignore a command to pop an empty stack.
FULL: Asserted when the stack contains a predetermined maximum number of elements. Your stack should ignore an attempt to push a full stack.
36. The queue is a software data structure that is sometimes implemented in hardware.
The queue has a front and a rear, like a line for tickets at a theater. A write operation adds an element to the rear of the queue; a read operation removes the element at the front of the queue. No other operations are allowed. The queue is also called a FIFO (first in, first out) memory. A queue has two status indicators: EMPTY: Asserted when the queue contains no elements. The circuit should ignore an attempt to read an empty queue.
FULL: Asserted when the last available memory location is occupied with a queue element. The circuit should ignore an attempt to write into a full queue.
(a) One approach to implementing a queue in RAM is to maintain two pointers FRONT and REAR as RAM addresses to the extremities of the queue. WRITE increments REAR and adds an element to the rear of the queue; READ extracts the front queue element and increments FRONT. FULL becomes true when REAR points to the highest memory location in the RAM. Design such a queue. You may alter the foregoing suggestions as long as you still implement a queue.
Why is this project more difficult than designing the stack of Exercises 34 and 35? In this implementation, when FULL is true, is all of the memory filled with queue elements? If EMPTY is true, what should be the values of FRONT and REAR? (b) Another approach to a RAM implementation of a queue is similar to that in part (a) but allows the queue to go "around the corner," so that REAR and FRONT may advance from the highest memory address to address zero. Design such a queue. When does FULL become true?
37. Design a controller for an elevator in a six-story building. Your controller must respond to call switches on each floor and floor-select switches within the car.
38. Design a four-way traffic-light controller that will keep traffic moving efficiently along two busy streets that intersect. In this exercise, consider only straight through traffic.
39. Extend Exercise 6-38 to include left-turn signals at each approach to the intersection.
40. Extend Exercise 38 to include pedestrian crosswalk signals.
PREV. | NEXT
Related Articles -- Top of Page -- Home