S4 Sequential Circuits without a Clock

END-OF-CHAPTER EXERCISES  

We return to the topic of sequential circuit design, and now consider a broader category, one without the restriction that outputs change only on a clock edge. While §6 on synchronous design allowed for systems with several inputs, one "input" was always special and played the role of clock. Now we revert back to un-clocked flip flops, and we give each input a chance to change system outputs as soon as it arrives. To bring some order to this broad generality, we will create a couple of new restrictions, chief among them being the requirement that only one input at a time can change, and that the circuit be allowed to stabilize before another input change occurs.
Our main effort in this chapter will be to work through three examples, which illustrate the various concepts and techniques of asynchronous design. First some preliminaries.

mention data flow machines  

S4 / 1 Motivation & Cautions

In Chapter 6 we designed sequential circuits by ganging all flip flops to one clock. Flip flop outputs changed only on active clock edges. Our chpt. 6 sequencers could have had inputs other than clock but the effects of the other inputs would have had to wait for active clock edges before flip flop outputs would change. If a sequential circuit lacks a master clock then it is called asynchronous. The inputs to asynchronous circuits can change the circuit outputs as fast as propagation delay will allow, and in regard to speed, an asynchronous circuit may have advantages over a clocked circuit, which, we repeat, must wait for the next clock pulse before changing its output. Like any sequential circuit, asynchronous circuits have feedback. Some of the asynchronous circuits we'll see in this chapter will be designed with SR flip flops, but synchronous circuits can be "designed from scratch" with Karnaugh maps, ending up with feedback around combinational logic gates, much like the design the first SR flip flop in Ch. 5.

Asynchronous methods are to be used with caution. "Timing problems," which we will detail later, are more likely in asynchronous circuits than in synchronous ones. But there are some circumstances in which asynchronous designs can make more sense than synchronous ones. For example, think of asynchronous design when there are several external inputs, each with a low rate of activity, and when none of the inputs occur at the same time. Such might be the case for a vending machine's inputs, where only one coin at a time can be inserted in a slot.
In general, each of several external inputs would increase the size of the truth tables to be realized by the synchronous method of § 6, but, since we will stipulate that only one input at a time can be active, some economies can be achieved by the asynchronous approach.

Should we call the circuits in this § "asynchronous sequencers"? We saw an example of an asynchronous sequencer when we considered ripple counters in §7. However, the set of asynchronous circuits includes circuits which don't step through a fixed sequence, but instead wait for new input and adjust their internal states accordingly. Many asynchronous circuits have the quality of electronic locks, wherein only one correct sequence of inputs can cause the output to change state. In a way then, many asynchronous circuits are the opposite of clocked sequencers--asynchronous circuits look for input sequence, while synchronous circuits generate output sequence.
But asynchronous circuits are not combinational circuits whose outputs depend only on present input; asynchronous circuit output depends on present input + internal state; internal state is determined by history of input. One state may be the result of different input histories, so we can't in general make the stronger statement that state represents history.

By their nature, synchronous circuits place an emphasis on the clock input. Compared to §6, where we learned to design synchronous sequencers with clocked JK and D flip flops, the present chapter will be more concerned with external input, and its influence on the circuit at hand. As such S4 can be considered the first stop on a tour through the realm of interface--how different systems can be made to work together.

In this chapter we will develop two methods for designing asynchronous circuits. One will be a systematic method, and it will start with a specification and timing diagram, leading to a state transition "flow" table, then Karnaugh maps hardware realization in SR or T flip flops. At the level of maps, and their external + internal inputs, the systematic method will have much in common with the synchronous design method learned in §6.
The other is a more intuitive approach, which considers asynchronous circuits as "locks" to which a "combination" must be found. The key-in-lock* approach will start with active output ("open lock", then work back to input sequences which give rise to the active output. Again, we will use SR or T flip flops as the basic design elements.

S4 / 1 / 1 The restriction of the fundamental mode.

With more than one input to a sequential circuit, we have to be careful about when the inputs occur. The restriction of the fundamental mode is this: Only one input at a time can change, and after the input change the circuit must be allowed time to stabilize before the next input changes. In the diagram below either INA or INB causes OUT to toggle. At the right the two inputs occurs too closely together for OUT to react to the first before the second comes along. The fundamental mode restriction is violated.



We could have started with the even more restrictive pulse mode, in which only one input at a time is allowed to be active. In fact one of our examples, the electronic lock, will be designed with a circuit which enforces a pulse mode restriction but most of what we say in this § will apply to fundamental mode design.
What can go wrong if two or more inputs change simultaneously, or if the second input changes before the circuit has time to stabilize? "Timing problems." We saw an example of a timing problem in un-clocked SR flip flops in chapter 5, when we justified the evolution of the clocked flip flop. As you will see, we will design asynchronous circuits with the assumption that an input change directs the circuit to a new state; if during the time the circuit is changing to the new state, another input arrives, unpredictable mis-directions of flip flop outputs may occur.
What we want to enforce is a time separation between input changes that is greater than the longest propagation time through the circuit. Input combinations will never be allowed to move more than one Karnaugh map square at time without letting the circuit stabilize before another input change occurs.
Below are the possible input combinations of C, B, A. From state S below, only the transitions shown by the arrows are allowed, at any one time:



A change from CBA = 001 to CBA = 010 would mean two inputs shifted "simultaneously."
What do we mean by stabilize? That all changes in the circuit have ceased. To repeat: The wait between changes must be at least as long as the longest propagation delay through the circuit, from input to output.
Inputs to some improperly designed "pathological" circuits may start the output oscillating, so that the circuit never stabilizes and can never properly accept another input (see end-of-§ exercises).

discuss VIOLATION of SET-UP AND HOLD TIMES as means of fundamental mode failure

Independent inputs never do change exactly simultaneously anyway; one input would always be a few nano or pico-seconds earlier than the other. An attempt to make a jump from input AB=00 to AB=11 would invariably pass through either AB=01 or AB=10 for a brief amount of time. And which of the two intermediate states were passed through might make a difference in circuit performance.
Later, in the first design example of this chapter we will explore what could go wrong with a circuit if the fundamental mode restriction were violated.

S4 / 1 / 2 State

State is now external input plus "internal variables." When we designed clocked sequencers in chapter 6 we considered the state of the (Moore) circuit to be the outputs of all the flip flops at a particular time between clock edges. But asynchronous circuits have no clock to cause all flip flops to change state at once. External inputs, and their sequence of occurrence, will play a big role in describing asynchronous circuits.
Therefore we broaden our definition of state to include the values of the external inputs and all the flip flop outputs in the circuit. In fact, as we'll see, asynchronous circuits can be designed with feedback around various combinational sub-circuits, with no obvious flip flops in place. We should really broaden the definition of state to include external and internal feedback variables. As we design asynchronous circuits in this § the need for defining states will become more apparent. Some conditions declared to be states may turn out to be equivalent to other states, and the equivalent states can be merged. Again, the three major examples in this chapter will clarify these notions.

[Note--An SR flip flop itself is example of an asynchronous circuit: 
designed without flip flops]

S4 / 1 / 3 The Good, The Bad and The Ugly

Asynchronous circuits have certain good features, chief among them are (1) "instant" response to changes in any input, without having to wait for a clock, and (2) economy of design, such as no need for a clock. These benefits can come at considerable cost, particularly proliferation of bad "timing problems." The general design procedure for asynchronous circuits, when first encountered, can seem "ugly", but only in the sense of the ugly duckling; with sufficient perseverance you will see asynchronous design for the swan that it is.

S4 / 2 Example 1-consecutive states detector

A circuit output is required to be 1 only when X is 1 just after X and Y have both been 0. By this specification OUT may be 1 when the input XY = 10, but not always; a combinational circuit won't solve the problem. A timing diagram of possible X, Y, OUT waveforms is shown below, including two cases of XY = 10.


Because of the limitation that only one input at a time can change, one of the XY = 10 's occurs after XY = 00 (case 1), the other after XY = 11 (case 2). Notice at * that OUT can be 1 when both X and Y are 1, as long as X gets to 1 first.

What circuit could produce the correct OUT in the waveforms above? Let's gain some confidence about asynchronous circuits by trying out the informal key-in-lock approach. First, notice that active output occurs when input XY=10, and after XY had been 00. So if XY=00 occurs, we need to remember it, in case XY=10 occurs after. Let's SET an SR flip flop when XY=00 occurs:


Next, let's AND the output Q of the SR flip flop with X to form the required output.


What about RESET? By a restriction placed on SR flip flops in chapter 5, RESET can't be 1 at the same time SET is 1, but otherwise when do we want to reset? We need to fill in the RESET part of the following truth table:



Suppose the flip flop Q has been set by an occurrence of XY=00. Then if X = 1, we don't need to reset. Only when XY=01--when the input has gone to a condition which requires it to return to XY=00 before OUT can become 1--is a reset necessary. Therefore



so RESET can be realized by RESET = X·Y.
A hardware realization now looks like,


We have finished a design, with no clock, and "instant" response to the sequence YX=00, XY=10. [We may want to add the stipulation for this circuit that when power is first turned on we expect Q=0.] Considering that two NOR gates can make an SR flip flop, our design requires 5 gates altogether; it has the look of a Mealy circuit, because OUT is a combination of flip flop output and external input X.
There were two phases to this informal design--
(1) Find input sequence(s) which lead to active output and mark the sequence with a series of SR flip flops SETs.
(2) Look for conditions which cancel the main sequence and use these conditions to RESET the flip flops in the path. Don't be tempted to just stick an inverter between S and R; for one thing, the inverter will cause times to occur when SR=11 transiently.

If different states represent OUT=1, then you must account for each separate path from start to OUT=1.

S4 / 2 / 1 Violation of fundamental mode restriction.

What if we violate the fundamental mode restriction about non-simultaneous inputs and try the transition XY = 00 ! 11? Suppose the inverter bubble for X on the AND gate causes a brief delay, and that the NOR gate has shorter propagation delay than the AND gate. Then the flip flop may RESET and OUT will stay at 0. If the inverter bubble doesn't have any delay, then the flip flop will stay SET and OUT will go to 1. Draw out the timing diagrams, with exaggerated delays, to see for yourself that output resulting from two "simultaneous" input changes may depend on relative propagation delays of gates, and not on logic in a truth table. The changes won't really be simultaneous, and errors--either transient glitches or permanent switches--may result.

S4 / 2 / 2 A systematic method for designing asynchronous circuits.

The next method will remind you, at the end, of our design technique for clocked sequencers. As we explain it, the systematic method will be applied to Example 1. We assume at the start that a specification in words is given. The specification will say what the inputs are, and what sequence of input will generate output. Following the specification, the following sequence of tasks will result in an asynchronous design:
-> draw out timing diagram
-> extract primitive states
-> construct initial flow table connecting the states
keep in mind the fundamental mode restriction on changing inputs
-> simplify by merging states together
-> generate Karnaugh maps for S and R input;
[this part will remind you of the clocked sequencer design method.]
-> combinational logic synthesis for S and R inputs.
-> Check for timing problems, in the form of races and hazards.

For Example 1 we already have the word specification and a start on a timing diagram; let's include more possibilities in an expanded timing diagram:


Notice that we obey the restriction of the fundamental mode--inputs change once-at-a-time. Propagation delays are not shown; we assume the fundamental mode stipulation that the circuit "stabilize" after each input change. In the next diagram each different episode of input-output is labelled with a lower case letter, a-f, signifying primitive state. You can err on the side of too many state labels; later in the design process redundant states will be merged.


Let's go over the labelling of states. The system starts with inputs X & Y and output Q all at LO; call that state a. After input X goes HI, then OUT goes HI, because the requirement of X going HI after XY=00 has been met; call that state b. Next, during state c, Y has gone HI at the same time X is still HI; OUT stays HI. After Y drops back to LO, the system returns to state b. After a fall to state a, a new state d arises when Y goes HI before X. Next, during another new state e, both X and Y are HI, but OUT stays low. Compare state e to state c; in both states inputs X and Y are HI, but only in state c is OUT HI also. The final different state is f, which occurs after e, when input Y falls to LO, while X stays HI. Compare states b and f; again, same input, different output. The timing diagram continues, with other sequences of the states a-f. The timing diagram, it turns out, is complete enough to account for all pairs of transitions from one state to another, given the restriction of the fundamental mode.

We call a-f primitive states because we haven't tried to minimize or consolidate states. Before we merge states, we need to show under what conditions the system can shift from one state to another. We'll mark the states on a 2-D surface and use the timing diagram to show state transitions.

We could just plop the state letters a-f down anywhere we like on a sheet of paper, but let's give them more organization, as shown on the map below. The map is called a primitive flow table and each state receives a separate row. Each column is a different combination of inputs, YX. OUT is listed with each row; only states b and c have output OUT = 1.
The columns of a primitive flow table look like the start of a Karnaugh map, but the rows are arranged haphazardly to accommodate one state after another. Once the rows become labelled by flip flop outputs, we'll be on the same page as the synchronous design method of §6



Next we show with arrows the possible input changes from each state. Since there are two inputs, X & Y, there must be two arrows from each state. Consider starting in state a, where YX = 00; if input X then changes from 0 to 1, the system moves to state b, as shown. On the other hand, if the input changes YX = 00 to YX = 10, then a transition to state d must occur. Both of these transitions can be seen in the timing diagram.

A transition from YX = 00 to YX = 11 is not possible because it would violate the fundamental mode restriction that only one input at a time can change.



Fill in the rest of the ten state transitions, again by reference to the timing diagram:



For this problem, you'll know you're finished with the primitive flow table when each state has two arrows leaving. States a and d have 3 arrows entering, and states c and f have only one arrow entering, but that's OK; all we care about is finding two arrows leaving each state for other states (or for itself).

Before proceeding to turn the primitive flow table into hardware, we need to make a remark about the squares on the diagram which the arrows pass through on their way from one state to another. Consider the circled "state" in the diagram above, shown in isolation below:


Because of propagation delay from input to output, there will be a brief amount of time when the system is in the state QYX = 001; such a state can be called an unstable state or a transient state. In fact, our design method will take advantage of the system's brief stay in a transitory state to guide the system to the next stable state, in this case state b. All of the states labelled a-f are stable states. When the system passes through more than one transitory state, it is said to be in a cycle. The transition from a to d looks like a cycle, but actually passes only through state QYX = 010 on its way from a to d.
A system with a limited number of stable states is a FINITE STATE MACHINE, and our primitive flow table is a finite state machine description.

Before we merge states together to streamline the final design, we should pause to note that our primitive flow table can be used to generate a hardware solution with SR flip flops. Each primitive state will represented by a different SR flip flop, six in all. If we want to ignore the don't care's in the SR excitation table, we can let R = S for each FF. But what a waste! Six flip flops where we know one will do! The wasteful design is started below, for states a and b:



Also stuck in the wasteful design are the annoying inverters between S and R.

S4 / 2 / 3 Merging states

Merging is Step 4 of the design method outlined above. After merging we will have reduced the number of rows in our primitive state table; then we will need to label what flip flops will represent which states. When can two rows be merged?
To better visualize the possibilities of merger, mark each transient state with the name of the stable state it will become. We show the first two rows, below. Transient state QYX=001 is labelled with a "b" because stable state b is the destination of the arrow from a after the change from YX=00 to YX=01. The other three transient states are similarly labelled. There are two don't-care states, which can't be entered because of the restriction of the fundamental mode.


For each pair of rows, consider one column at a time. Two rows can be merged if-
(1) The stable states for each row may be differently labelled, however in the same column each state of each row projects by input changes to the same other state(s).
(2) The state labels in each column of the two rows being considered are the same, or a don't-care is in one of the column squares.
If any column fails the test, the two rows can't be merged.
Care must be taken with system output. Two states with different outputs can't normally be merged unless the output condition is adjusted, as seen in the example below.

We'll use condition (2) for example 1. Example 2 will make use of condition (1).
In the case of the first two rows,
for input column YX=00, state a is the stable result for both rows,
for input column YX=01 state b is the stable result for both rows
for input column YX=11 the first row is a don't care and the second row goes to state c
for input column YX=10 the second row is a don't care and the first row goes to state d.
Thus all four columns satisfy the condition for merging the first two rows.

There are 15 pairs of states to inspect for merging. It may take you some time to work through by hand each pair, but after you do a merger table, as shown below can organize information about the pairs of states; Y=yes the the states can be merged, N=no.




Look at one of the pairs which can't be merged--a and e. Isolate the two rows, label the transient states with their destinations, and the don't-cares with X's:


The column governed by external inputs YX=01 has a transient b for row a and a transient f for row e, so the two rows cannot be merged.

marriage metaphor: two people in one house...merging 

Given the merger table of row pairs, which states should be merged with which? A general method for merging states in an optimal way is hard--NP-hard in fact [Ward & Halstead, 1991]. See McCluskey (1986, §9.2, page 388) for a definitive treatment of flow table simplification. Let's proceed slowly, and pick a couple pairs for merger, then repeat the merger table process. The table says it's all right to merge states b & c and states e & f. Our not-so-primitive flow table now looks like



We could stop here, and use two flip flops to represent the four rows of the flow table. But in fact we can go through another round of merging. Look at the third and fourth rows, which can be labelled as



There are no conflicts in any of the columns, so rows 3 and 4 can be merged. Now look at the first and second rows, where, again, we've labelled the
destinations of transient states with non-bold state letters.



There are no conflicts in any of the 4 columns, but OUT is different for the the two rows.

We can still merge the two rows if we keep in mind that this system output will then not be just the output of a flip flop. By studying row 2, we can see that OUT is true only when external input X is true and state bc is true. On the other hand we could keep rows 1 and 2 separate; then a Moore circuit will result, with a combination of flip flop outputs as the output.

need to justify the change of output...

Our second round of merging results in



where we have replaced row label OUT with Q, to signify that OUT is to be formed as a combination of X and Q, where Q is a flip flop output. Notice that we can't merge the two rows above; there are conflicts in the middle two columns.
Our merged flow table is about to become a Karnaugh map. Maps for what? In this case, maps for S and R of the flip flop which Q is the output of. Remember from §6 that in synchronous circuits flip flop outputs were fed back to become input steering controls. It happens again. In asynchronous circuits made from un-clocked flip flops, the flip flop outputs can feed back to become combinational inputs which steer S & R, or T or D. This circuit is like one we saw for synchronous design, except there is no clock here.




Instead of a clock to separate the times when QNOW differs from QPREVIOUS, we now rely on the delay of signals through the forward path of the circuit. Thus for a few gate delays worth of time after X and/or Y change, Q stays the same on the combinational logic input.
Back to our specific problem: How are states abc and def associated with flip flop output Q? Consider the row where Q=0. If the flip flop output is to be 0, during the time when state abc is stable, then abc should be 0. Likewise, def should represent a stable 1 for the flip flop.



Stable states, in which QNOW = QNEXT, are circled. Why is there a 1 for QNOWYX=010? Because YX will have just changed from either 00 or 11 to 10, and the system will want to change the output Q to 1; for a brief delay QNOW, the present value of Q, will still be 0, so the input condition QNOWYX=010 will cause Q to change from 0 to 1. Let flip flop Q be an SR flip flop. To make the 0 to 1 change, we need to use the SR excitation table.

Question: How are the 1s and 0s decided upon for the table above? 

Now our asynchronous method converges with the synchronous method of chapter 6. In ch. 6 we used the excitation table for JK flip flops to fill in maps for J and K of each flip flop. Here we're using SR flip flops, so recall from chapter 5 the excitation table of the SR flip flop, with its two don't care's for no-change transitions:



a 0 ! 1 output transition, such as we have in the right hand column of the map, requires that SR = 10. Place the 1 and 0 in separate maps for S and R, in the upper right corner:


Fill in the rest of the K-maps, using the SR transition table in conjunction with the stable state map-


where Q is the output of the flip flop.
What would happen if we were lazy and only made a map for S, then let R = S?

Use the Boolean expressions for S and R to turn the flow table into hardware.


We're not done, because OUT must be formed from Q AND X


All that work and we end up with the same result as our informal key-in-lock design!
Much ado about something...

We can make our systematic design even simpler than the key-in-lock design by realizing a circuit directly from the stable state map, re-drawn below,


Now the circuit has no explicit flip flop; but there is feedback (shown in bold), creating a specialized sequential gate, much as we created the original SR flip flop from a K-map in §5. Like its SR flip flop cousin, this circuit has six stable states--the three zeros in row 1 and the the three 1s in row 2. When QNOW = QNEXT the circuit is stable.

We choose not to emphasize this non-flip flop "from the ground up" realization in order to compare the role of SR flip flops in synchronous, key-in-lock, and systematic asynchronous design methods. Besides, the non-flip flop design has an internal timing problem (static hazard, which can be analyzed in an E-O-§ exercise). When a transition from YX=11 to 10 occurs, we expect that Q will stay at 1, but in fact, because of the extra delay through the inverter from X to the top AND gate, Q will transiently go to 0. This timing problem does not occur with the SR flip flop realization, because SR=00 is a no-change condition. Actually the timing problem on Q does not affect OUT because OUT is gated by X, which goes to 0 anyway.

Our next example extends the sequence of example 1 to a specification which requires two SR flip flops for realization.

(Edit this paragraph...) This example suggests that states associated with different outputs, (here Q=0 for state a, Q=1 for state b) can be merged, and that is true. However, a more conservative approach would prohibit merging states with different outputs. If different output states are kept separate, then the final design can be a Moore circuit, where flip flop outputs represent output. Otherwise a Mealy circuit is needed; in the case above, OUT = Y·X·Q, where external inputs Y and X must combine with output Q to form the correct output of 1 when state b is entered.

What should our circuit do when power is first turned on? It would be good if the circuit went to state QRS = 000; but we may need additional hardware to insure that a desired ground state, (state a in this example) is entered at power-on.

We'd be lazy to send S to R; the extra delay can cause transient states in which SR=11. But for this design would it hurt us?

Why not make the electronic lock out of clocked D flip flops? (1) an asynchronous input pulse A-D may be too brief compared to the clock, or violate set-up or hold times (2) clock really not needed, as the design above shows. (are we cheating with the counter?)

Other examples of asynchronous circuits are
1.individual SR flip flops
2. oscillators, which can be thought of as asynchronous circuits with unstable modes;
3. one-shots, which we will analyze later in this §, and which produce one pulse of a specific width in response to a particular input waveform edge.
4. electronic locks;
5. vending machines;
6. data flow networks.

S4 / 3 Example 2--Window discriminator

S4 / 3 / 1 analog comparator

For example 2 we need to introduce a new interface element, the analog comparator. Analog comparators have digital (0 or 1) outputs, and so their outputs can be inputs to a logic circuit.


The two inputs to a comparator, however, can be any voltages within the limits of the device. Let the inputs be called V+ and V-.
The analog comparator output goes to logic HI if V+ > V- and otherwise is LO.
The analog comparator will be seen again in §B, on analog-to-digital conversion, where it will be revealed as a 1-bit A-D converter. Problems with analog comparator inputs almost equal to each other will be addressed in §B.
We emphasize the new element is an analog comparator, not to confuse it with combinational circuit digital comparator, which we saw in §2-4, and which has two multi-bit digital inputs compared for equality by AND and OR gates. The digital comparator can also have HI-LO outputs for "greater than" and "less than."

Now let's put the analog comparator to use. Imagine a continuously changing voltage, for example the "electroencephalogram" EEG signal waveform recorded from an electrode on a patient's scalp.


The EEG voltage is fed into a system which has two level detectors, one which responds to any voltage above threshold "qH" and the other to any voltage above threshold "qL." The level detectors are analog comparators. The outputs of the level detectors are fed as digital signals into our logic system (and we henceforth refer to the digital outputs of the two analog comparators as U and L). As a consequence of their thresholds and common analog input, only UL combinations 00, 01, 11 are possible, and the restriction of the fundamental mode is enforced automatically; it's not possible to go from UL=00 to UL=11 without first going through UL=01.



Here's how the two thresholds are used to specify when a circuit output occurs:


The "window discriminator" will respond when the EEG waveform goes above level L, then returns below L without going above U. In other words if the waveform pulse height stays in a "window" between L and U, then an output results. See below for 2 successful pulses, marked by *s.


OUT comes on after the successful pulse is over, and stays high until the EEG waveform crosses the lower threshold again.

If we wanted simply to know when the waveform were between levels L and U, then
U  L would do the job. However, for what is required, the combinational solution
OUT = U  L, is not acceptable; it's HI during the waveform's stay in the UL=01 region, not after the return to UL=00.
The window discriminator needs memory of whether the waveform was previously below L or above U in order to produce a correct output at a fall in detector output U.

S4 / 3 / 2 Attempt at "key" design

Before starting a systematic solution with flow tables and row mergers let's try solving the problem with SR flip flops, by looking for a key sequence to the output "lock." See diagram below. First of all, a successful input sequence will always start out below level L, so let's have a flip flop SET to remember a start at UL = 00. Next, The system should remember that it got to UL=01 after UL=00; the second flip flop SETs to remember the excursion into the UL window. Finally, if the system returns to UL=00 and Q2 is still set, then OUT will go HI. The SET path of our key is shown below.


So far so good. If the waveform starts below L, crosses above L, then re-crosses below L again, OUT will go HI. OUT will drop to LO again as soon as the input exceeds L again. But we haven't dealt with RESETs on the the flip flops, and OUT will go HI even if the waveform goes above U before returning below L. What to do? We know that if UL=11, then the system must be made to wait again for a return to UL=00 before trying to "un-lock" the OUT. Let UL=11 reset both flip flops.


Are we done? It looks good. But do we really need the line from U to the RESET AND gate? The circuit is a Mealy circuit again, with two flip flops and OUT a combination of FF-2 output and U-L input. There is "feedback" only from Q1 to the S2 logic. Save this "lock-and-key" solution and recall it after we finish the systematic design.

S4 / 4 Systematic design of window discriminator

S4 / 4 / 1 Timing diagram

We have a start on a timing diagram with the analog waveform plus OUT graph above. Just translate the L and U crossings into logic levels; if the waveform is above level L, detector L is HI; if the waveform is above level U detectors L and U are HI.


Primitive states are labelled, with lower-case letters, at the bottom of the figure. Have we forgotten any transitions? Made any mistakes in state labelling? Forget states? We'll find out when we try to fill in the primitive state table. Did we create too many states? We'll find out when we try merging.

S4#1--circuit which counts two pulses

S4 / 4 / 2 Primitive flow table.

Now form a table in which the columns are different input UL combinations and the rows are the primitive states. Combination UL=10 is shaded because it is impossible to reach. All entries in column UL=10 can later be marked don't-care. In each row of the primitive flow table only one box can represent a stable state.
Draw arrows from one state to the next, as set forth in the timing diagram above. For example draw an arrow from state c to state d. The timing diagram with its state labels also suggests that there should be a label from state c to state b. Both are drawn in, with a question mark.



Only state c is associated with OUT = 1. Combinations in columns 00 and 11 can make a transition only to column UL= 01, since combination 10 is not allowed. Even at that something seems to be missing from the primitive flow table; we don't have a transition arrow for state b going to input combination UL=11; maybe we didn't make a complete timing diagram; let's say state b goes to state d if input changes to UL=11. And what about state d when the input changes to 00? it must go back to c. There's also a problem with where state c projects to--it looks confused about states b and d. We have too many state labels! We'll clear up the confusion in the next paragraph.

S4 / 4 / 3 Merging

Compare every pair of rows. Recall the first merging condition, that if the stable states for each row are different labels but in the same column, AND each state projects by input changes to the same state(s), then the two rows can be merged.

State c goes to both states b and d so merge rows 2 and 4 (states b and d) to begin with. States b and d meet the merging condition. So do rows 5 and 7 (e and g). Notice that the output is 0 for all cases except state c.
States b and d are stable in column UL=01; both project to e when input changes to UL=11, and both project to c when input changes to UL=00. States b and d are the same state in different disguises! Same for states e and g, which both project to f for an input change. What about a and c? They both project to b, but only c is associated with OUT=1. Unlike example 1, we can't ignore the output difference between a and c, because they're in the same column, and we have no way to distinguish between the two. Rows 1 and 3 can't be merged.

Now let's use merge condition (2). For each pair of rows, look in each of the three possible input columns, and check if the pair agree on state, either stable or transient.
First inspect all the row 1 pairs.
Start with rows 1 and 2 (a and b); they can't be merged because for column UL=00 row 1 wants to be a while row 2 wants to go to c. Rows 1 and 3 can't be merged because they disagree on what the state should be for input column 00. Rows 1 and 4 can't merge because we know row 2 and 4 are the same state, and rows 1 and 2 can't merge. What about rows 1 and 5? No again! because of column UL=01. Ditto for rows 6 and 7.
State a will be on its own in the final design!
Form a merger table and fill in the information gathered so far.



As an exercise, complete the rest of the table.
After a first round of merging, our state diagram looks like,


A second round will allow for eg and f to merge, since the last two rows have no conflicts in their columns. Also, states bd and c can merge, if we remember to let the input condition UL=00 decide when OUT=1.
See below.


Can we get it down to two rows (and therefore a 1-flip flop design) by merging states a and efg? No; they conflict for input column UL=01. Since we are stuck using two flip flops, maybe we shouldn't merge states bd and c. If c is one state, then no Mealy combination for OUT will be needed. Let's work with the 4-state system, on the left, above.

S4 / 4 / 4 Hardware for the window discriminator logic

Now our work is "merging" with the synchronous design method. We assign two flip flop outputs (Q1 and Q0) to the four states.


OUT will be true when both Q1 and Q0 are true. As with example 1, let Q1 and Q0 be the outputs of SR flip flops. Keep in mind that this asynchronous circuit does not depend on a clock, but on the delay between input change and output change to provide intervals between states.

The arrows on the state transition map above will guide our choice of S and R for the two flip flops, keeping in mind the SR excitation table:



All of input column UL=10 can be marked with don't-care X's. There are a couple more apparent don't-care's, such as Q1Q0UL=0011, which have to be more carefully scrutinized after our design is tested. Fill in the four maps as shown below.


Gather 1's and form Boolean expressions (for the choices circled above)

S0 = U · L · Q1
R0 = U
S1 = U + L · Q0
R1 = L · Q0 + U · L · Q0
Both S1 and R1 contain the same minterm, L · Q0 .

A logic diagram for the circuit is


This time the design is 2 gates more complicated than the result from our "key-in-lock" design effort. And, where the backward arrows are shown above, we have feedback from the flip flop outputs to the SR steering logic.
[Recall now the key-in-lock design. As we drew it, the design appeared to have no feedback; however, if we re-drew the key-in-lock circuit with one flip flop above the other, the connection from Q1 to Q2 would appear to be a feedback path.]
At any rate, we entered the schematic above in our logic simulator, and it worked, except for a brief output glitch on the first occurrence of U going HI-LO--that is, when the bd-to-efg state change occurs. We need to get rid of the glitch, shown below.



S4 / 4 / 5 A race condition in the map

Let's take a closer look at the transition from bd to efg. After the bd-efg transition is over, Q1Q0 will have changed from 01 to 10--both Q's will have changed. By the way we've drawn the arrow from bd to efg in the diagram, we are assuming that Q1 will change before Q0, so that Q1Q0 = 11 will be a transient state on the way from bd to efg. It must be during this transient state that the output glitch occurs, since
OUT = Q1Q0 = 11. If two flip flops in an asynchronous circuit are trying to change simultaneously, then the flip flops are in a race.


Due to slight variations in the actual flip flops [or to the sequence of code execution in a simulator] one of the flip flops will "win" the race and the flip flops will pass transiently through another state on the way to the stable state. Races are not necessarily bad, for example if the transient state is of no consequence, but otherwise races in asynchronous circuits are to be avoided. In the case we're considering, Q1Q0 = 11 must be a transient state in the race, and passing through the transient state Q1Q0 = 11 generates our unwanted glitch (remember that OUT = Q1Q0 = 11 ). Because our race cycle passes through an un-wanted state, it's a critical race.
How to find races? Look for cycles, which are state changes which move over more than one square from beginning state to end state. The bd to efg change is a cycle.

need another example here, to illustrate exactly what a cycle is

What to do about our glitch? One fix--place more delay on the output of Q1, and yes, that does work, in the simulator, to remove the glitch, by sending the circuit through state 00 instead of 11 on the way to 10. But inserting extra delay into a circuit to re-route a critical race is generally an unsatisfactory solution; you can't count on the extra delay always being great enough...you end up building a circuit and hoping a few nanoseconds of deliberate delay makes the difference between success and failure.
What else? We could add a third flip flop to the system, and give ourselves extra states to step through, to avoid the OUT = 1 condition; but is there a way to avoid adding another flip flop? In this case, yes--arrange in the K-map for S1 that state Q1Q0 = 00 is entered after the change from UL=01 to UL=11, then send the circuit to Q1Q0 = 10. The map for S1 now looks as shown below, with the changes shown in bold.


We eliminated the critical race by specifying a one-Q-at-a-time change path, as shown above, which skirts around Q1Q0=11.
The same logic expression can be used for R1; what's a new expression for S1?
A new expression for S1 was entered into the logic simulator, and it worked; no glitch on the first transition of bd to efg.

Why is the key-in-lock design result different from the systematic design? As requested in one of the end-of-§ exercises, you can work back from the logic of the Ss and Rs of the key-in-lock design, to the K-maps, then use the excitation table for SR flip flops, and find out which states correspond with what flip flop outputs. If you do this "reverse engineering" you'll discover that the key-in-lock solution merges states bd and c, as the systematic approach had a chance to do. Then the states are labelled,





Basically, the difference is a matter of merging and state labelling more effectively, although the key-in-lock method doesn't require you to think about merging.
In fact the systematic method could have been used to realize the hardware directly in gates with feedback, and been more competitive with the informal SR design of key-in-lock.

S4 / 5 Stable circuit before input change

When testing window discriminator logic designs on the simulator it's possible to find input sequences which result in bursts of oscillations on the output (looks like a "dynamic hazard"); in all cases the input sequences cause problems when changes occur too rapidly; the circuit doesn't have time to stabilize before the next input change. Remember one of the restrictions of the fundamental mode--the circuit must be allowed time to stabilize before the next input is changed. Inputs which change within a couple chip propagation delays of each other generally don't satisfy that requirement.

Some arrangements of SR flip flop inputs and output can result in oscillations, as shown below.



An oscillating circuit never reaches a stable state, so if certain input to an asynchronous circuit causes oscillation, then, by the restriction of the fundamental mode, new input can never be applied! (See problem at end of § for more examples).

S4 / 6 Edge detectors and one-shots

For example 2 we introduced a new device, the analog comparator, to help provide digitized input to the sequence-detecting logic. Example 3 will require another new "gate," the 1-shot. A 1-shot provides a fixed-width pulse output in response to a rising or falling edge input. Thus an input which changes level, after passing through a 1-shot, will show only a pulse change to the system. One-shots can convert an asynchronous system from fundamental mode to pulse mode.

We've already seen 1-shot-like circuits. In §5 (Flip Flops) we described combinational circuits which would take advantage of chip delay to turn an edge into a pulse. For example, a rising-edge detector would be:



What's the difference between this "glitch generator" and a 1-shot? The pulse width D of the glitch is rather brief, equal to the 10 nanoseconds or so propagation delay of the inverter, and it isn't adjustable. In fact, if the glitch detector were an input to a 1-shot, the 1-shot could become a pulse-stretcher:


where the wider pulse on the output of the 1-shot is a stretched version of the glitch input. During the time the 1-shot pulse is active, a second input glitch will be ignored by the 1-shot. A hand-held logic probe has a pulse-stretching circuit to light a "pulse" LED in response to a brief glitch on the probe's input.

How is the width of the 1-shot pulse adjusted? By an RC circuit attached to the chip. As you may know, the unit of resistance x capacitance is time; a 1MW resistor and a 1mF capacitor have a time constant of 1 second (when placed properly in a circuit).*


A capacitor acts somewhat like a reservoir, storing charge. How long it takes to fill or empty the reservoir through a pipe representing resistance is a measure of the time constant of the system. The most common reservoir in daily life is the tank of a toilet. The toilet even has a level-sensitive switch to shut off the flow of water refilling the tank!

A version of the following RC circuit will be used in our 1-shot design:


To start building a 1-shot, a glitch generator can be the "front end," setting a flip flop. See below.



where the RESET action will end the pulse started by SET.

Let Q throw a switch which discharges a capacitor C through resistor RD


With a time constant of 1 second, the voltage on the capacitor will fall, due to current flow through RD and the switch, to ground.
Now, what should reset the flip flop, sending Q to LO, and turning off the switch?
The falling voltage, Vcap(t) !
By a feedback path--
with an inverter between Vcap(t) and R, in order to reset with active-high logic.

Notice that the inverter is driven by an analog voltage, Vcap. That's OK here; all that's needed is for the inverter to respond properly to Vcap dropping below VIL, or rising above VIH.

Where does the 1-shot pulse come out?
From Q, which stays HI after SET as long the Vcap stays above VIL.


How long will the RESET action last? As long as it takes to charge the capacitor back up to +5v. As soon as the switch opens in response to a RESET, RD has no access to ground and current flows through RC to the capacitor.
[The switch in this circuit is normally a transistor.]

Here's how the 1-shot works--the switch is normally OFF, and the capacitor charged up. Both S and R are LO. When input makes a transition from LO to HI, the glitch circuit sends a pulse into SET, causing Q to go HI and the switch to close. The capacitor discharges through RD until Vcap is less than VIL, at which time a RESET pulse causes the switch to open again. With the switch open, the capacitor re-charges through RC. After Vcap reaches VIH, the RESET pulse ends and the circuit is ready to accept another rising edge. These words are explained with the timing diagram below:



The width of the 1-shot pulse is determined by t = RD·C; in the case shown, t = 1 sec.
The width of the pulse on Q is not exactly equal to t , but for our purposes is close enough.
What should RC be? Time constant C·RC determines how long the RESET pulse lasts. For our purposes C·RC might as well be as small as possible to reduce the amount of time until the capacitor is fully charged again.

What happens, in our present design, if another SET pulse comes along during the active RESET, creating the condition SR=11? If the SR flip flop is made with two NOR gates, the condition SR=11 causes Q = LO. Q is already LO because of RESET, so the design is OK. Even if the unexpected SET outlasts RESET, all that will happen is the immediate production of another full-length pulse.
But if SR=11 leads to Q=1, then a new pulse may be started without Vcap fully re-charging to 5 volts. The new 1-shot pulse will be abnormally short.
What can we do to make our 1-shot design air-tight?
If we want to patch up our design, then we can arrange that reset have priority over set, by the following circuit:


Now when R is HI, it will inhibit anything from getting through to S, and prevent the unwanted SR = 11 state. There are more elegant designs for 1-shots*

; see the schematic for chip74123, for example. But what we have done is OK; in fact it's a lot like what you'd get if you made a 1-shot with the 555 timer chip. One-shots come in two varieties: rising-edge triggered and falling-edge triggered. And normally they have two outputs, Q and Q.

Let's make something with 1-shots; ironically, we can start by making an oscillator with a pair of falling edge triggered 1-shots. In our schematic we show a block diagram symbol for a 1-shot, with a down-pointing arrow on the input to signify falling-edge triggering.



Either Q can be the output. The circuit will have a timing diagram like:



The oscillations can be stopped by forcing both Q's to LO; in fact the circuit may need a "start pulse" if, when power is turned on, both Q's are LO.
If each 1-shot pulse is 10 msec in duration, what is the frequency of oscillation? 50 Hz.
Would the circuit work if the 1-shots were rising-edge triggered?

See Horowitz and Hill (ed.I) precautions on 1-shots, page 355, ...some 
of their warnings are for "rare events" 

One-shots are tempting to use in asynchronous circuits. Suppose we want one cause to result in two effects, for example a coin registering in a vending machine causing a door-open signal, then, after a pause, issuing a door-close signal. We could use three 1-shots, to create a "2-shot" with internal delay:



a timing diagram would look like:



Outputs Q1 and Q3 can be OR'd together for a 2-shot output.

Warning about 1-shots: 1-shots look like a painless, ad hoc, way to design clock-less sequencers. Beware, however, that use of 1-shots is accompanied by a couple problems:
(1) Non-systematic design technique; 1-shots are just stuck in circuits where it looks like they might fix something...
(2) 1-shots can pollute circuit power lines with noise spikes. For example, the 1-shot design on a previous page will suck up lots of power supply current for the brief interval in which it is rapidly re-charging the capacitor. Such an action my cause a "spike" to propagate on the power supply wires of the circuit, and disturb, gremlin-like, the action of nearby logic chips.
Bottom line: 1-shots may create more timing problems than they solve.
1-shots are the "ugly" of asynchronous design, but sometimes, in simply turning edges into pulses, to create a pulse-mode circuit, 1-shots have a legitimate place in digital design, as we'll see in the next example.

S4 / 7 Example 3-Electronic lock

Specification: Given 4 buttons of input, labeled A, B, C, & D, create a circuit which will generate a HI UNLOCK signal if and only if the buttons are pressed one after another in the sequence B-D-C-A.
This example will literally be a case for the key-in-lock approach!

S4 / 7 / 1 Key-in-lock solution

Start with the OUT, which will go HI when the last item in the sequence, input A, is active and the memory of the sequence B-D-C is present. What comprises the memory of B-D-C? A flip flop must have been set. See diagram below to follow output back to beginning of unlocking input sequence.


The chart above can be converted into hardware, with SR flip flops,
albeit with no reset action yet,



where the final output depends on the presence of input A.
We could put in a 4th flip flop to sustain the output after a pulse from A disappears.

What about RESET? The key-in-lock solution requires that we think about each flip flop in the pathway, and decide when it must be reset. Let's start with the second flip flop, which has output Q2. Imagine FF-2 has been set by B, then D, being pressed.
· If D is pressed again we can leave FF-2 alone, as a "de-bounce" courtesy;
· If C is pressed we can leave FF-2, since C is the correct next input;
· If, however, A or B is pressed, then FF-2 should be reset; neither A nor B was responsible for setting FF-2 or will be the next correct entry:


OK, but what if D and A or B are pressed simultaneously? Yes, we could put 1-shots on all the inputs and go into pulse mode, but let's delay that for a while. What we could do here is give RESET priority over SET,


What about resetting FF-1? By the same reasoning we used on FF-2, we can say that inputs B and D should not reset, since they are part of the correct sequence around FF-1; otherwise inputs A or C should reset FF-1:


By similar reasoning, FF-3 should be RESET by B or D; the last element of the key-in-lock solution looks like:



But once the correct sequence is entered and OUT = HI, OUT will flicker in time with repeated presses of A, and perhaps worse, pressing C won't re-lock; in fact the only way to re-lock to the beginning is to press B or D then C or A. Actually the specification for the electronic lock didn't say what should be done for re-locking, so perhaps the design in the last two figures is OK. Our lock is almost as hard to re-lock as it is to un-lock! (I think I had a gym locker like that in high school).
Some students complain that the sequence B-D-C-B-D-C-A will unlock, but after "C" the correct sequence had to be entered anyway, so it is not a disqualifying sequence.

What if the systematic method for asynchronous design with timing diagram, primitive state table, merging, etc is tried? If we allow fundamental mode operation, a real mess results; a successful design is possible, but it would take more pages than have already been used up by this §. Instead, let's explore the benefits of switching to pulse mode:


Now there are many fewer possible input "combinations"--5 vs 16, in fact.


There are, however, still too many sequences of inputs to deal with easily.
Each input will appear as a pulse during which time no other input can be active.
We can start a timing diagram like,



but it is a quotidian result.

Can we bypass the timing diagram and still come up with states to assign flip flop outputs to? Yes. We know from the specs that four pulses are required to open the lock. Let's attach a state to each of the 4 unlocking steps, and include a RESET state.
Let a one-change-at-a-time flip flop code assign flip flop outputs to the 5 states:



We may not need the RESET or step 4 states, but let them tag along for now.
Since our inputs to the lock will be pulses, let's design with T-flip flops, because T's can accept pulses on their clocks.

S4 / 7 / 2 State diagram




The excitation table for a T flip flop is



where the pulse symbol means that the flip flop was "clocked"; in the pseudo-K-map below the pulse symbol is replace with a "1" to avoid cluttering the diagram.
To steer the 3 T flip flops to proper transitions, we need maps for each T input--T2, T1, T0. Three such maps are shown below. To understand how the 3 maps were filled out, start with the first row for T0, and input B, circled below. Q2 Q1 Q0 = 000 for the first row, labelled RESET. Only if input B pulses do we want a change, and then only for Q0; the "1" in column B for T0 represents the change from 0!1 for Q0; all the others are no-change 0!0's.


We're doing our best here to deal with a seven variable map--4 inputs and 3 FF outputs-- fortunately the pulse mode restriction limits input "combinations" to 4 columns. However there is no AND relationship between columns, as we'd expect in a regular K-map. There are some repetitions, such as the state combinations circled

Each column is a separate expression to be OR'd with the other columns of a given TX.
To start the process, form the Q combinations for each of the 5 states. Here are the states in a regular K-map, where RESET state has been labelled #0:



The 5 state combinations look like


S4 / 7 / 3 Toggle flip flop hardware for electronic lock

Now combine the 5 state outputs with the pulse inputs. By reading down each column map, we can find what states AND with each input. There are 4 inputs per TX. First consolidate the repeated state expressions, circled above, by reading off the K-map for states--
#2 + #4 = Q2·Q1·Q0 + Q2·Q1·Q0 = Q1 · ( Q2  Q0 ) = EX1
#3 + #4 = Q2·Q1·Q0 + Q2·Q1·Q0 = Q2·Q1 = EX2 and note that
#2 + #3 + #4 = Q1·Q0 + Q2Q1 = EX1 + EX2
Now here are Boolean expressions for each of the 3 TX's
[Example: The left-most column shows that, for T2, D is active when state #3 OR state #4 is active; the T2 D column is identical to the T2 B column and part of the T1 D column. The reduced expression is called "EX2" for short ]
# #
T2 = D · EX2 + C · EX1 + B · EX2 + A · #4
T1 = D · ( #1 + EX2 ) + C · #4 + B · (
Q1·Q0 + Q2·Q1 ) + A · EX1
T0 = D · #3 + C · #1 + B · ( #0 + Q1·Q0 ) + A · ( Q2·Q0 + Q1·Q0 )


With some Boolean reduction (not shown), we're done. Whew!
Perhaps the T's could be realized with a PLA (§4).
Without showing every wire, the toggle flip flop realization of the electronic lock looks like


We entered the (hierarchical) schematic into our logic simulator, and yes, it works. No glitches, unless input pulses arrive faster than it takes for the circuit to stabilize.
Compared to the key-in-lock design, the toggle design has a better RESET; after un-locking, any button push will send the system back to state #0. This improvement is at the expense of more hardware for the design.
What if the combination of the lock must be changed? It should be just a matter of re-routing the wires from the 1-shots to the combinational circuit, in the T FF design above...easier than with the key-in-lock version.



S4 has taught about asynchronous design primarily through three examples. The emphasis has been on design, not analysis, of asynchronous circuits. One of our design recipes requires careful attention to ingredients, while the other allowed more improvisation. Even so, it's been Asynchronous Lite. Particularly with regard to merging, and identifying timing problems in the form of races and hazards, we have not filled you up. By attempting a few exercises from the end-of-§ menu, you'll get more of a flavor for asynchronous design. If you check your designs on a logic simulator, or build them in hardware (TTL chips, etc), you may even feel like your appetite has been satisfied.
The main hardware ingredients in our S4 designs have been un-clocked flip flops, SR and T. It would be possible with the systematic design method to push the design down to the level of combinational gates in the midst of feedback paths.
We had seen such a design in Chapter 5, when we built the first SR flip flop from a K-map with delay output as one of the map inputs. As with §6, synchronous design, one of the key ideas in S4 is that a system's current output can be used, in conjunction with new input, to determine the next output.
Two new "chips" were introduced in S4--the analog comparator and the 1-shot. Both are useful in interface--the analog comparator between analog signals and digital logic, and the 1-shot between logic levels and logic pulses. Caution was issued in the indiscriminate use of 1-shots to "solve" problems in asynchronous design.
The text chapter 9 on serial transmission will discuss further how separate systems, each with their own clocks, can be made to communicate through asynchronous "handshake" circuits.

S4 / 8 Summary





Further reading on asynchronous design--

JD Lab Manual +, Lab 11, "Asynchronous shepherd." The specifications for Lab 11 follow the progression started with examples 1 and 2 in S4. and

(1) W.I. Fletcher, An Engineering Approach to Digital Design, Prentice Hall, 1980. See chapter 10.

(2) Breeding, K.J., Digital Design Fundamentals, Prentice-Hall, 1989. See chapter 5, "Asynchronous sequential circuits".

(3) Johnson & Karim, Digital Design--A Pragmatic Approach. PWS, Boston, 1987. See chapter 8, "Design of pulse-mode circuits" and chapter 9, "Design of fundamental-mode circuits".

(4) Peter H. Beards, Analog and Digital Electronics, 2nd Edition, Prentice-Hall, 1991. See Chapter 15, "Asynchronous sequential circuits".

(5) Edward J. McCluskey, Logic Design Principles, Prentice-Hall, Englewood Cliffs, NJ, 1986. A more advanced text. See chapters 7-9.


*The phrase key-in-lock is borrowed from biochemistry-the attachment of one protein to another-
the subject of protein-ligand binding, referred to as lock and key binding. see for example discussion inHubbard, S.J., S.F. Campbell & J.M. Thornton, "Conformational analysis of limited proteolytic
sites and serine proteinase protein inhibitors." J. Molec. Biol. 220: 507-530 (1991).