While ASIC houses and "good engineering practices" emphasize synchronous-design techniques, the increasing use of clock speeds as fast as 50 to 200 MHz is forcing designers to implement asynchronous logic circuits, instead. Unfortunately, although most digital design engineers are familiar with combinatorial and synchronous sequential-logic circuits, the world of asynchronous sequential logic design remains obscure. Transition maps can guide designers through this unfamiliar world to reach reliable asynchronous designs.

The journey begins with some basic concepts and definitions. Digital circuits can be classified as either combinatorial or sequential. Combinatorial circuits are those with output values that depend exclusively on the input signal levels. Sequential circuits have output values and present-state values that depend not only on the present input values, but also on the circuit’s previous state.

You can group sequential circuits into two types: synchronous and asynchronous. In synchronous circuits, the present state changes on the edge of a clock (Fig 1a). The present state in asynchronous circuits changes upon a transition in one or more input variables followed by the circuit’s propagation-delay period (t_pd).

When creating sequential asynchronous logic circuits, pay careful attention to the propagation delays through the circuit. Otherwise, undesirable output glitches or even permanent undesirable states can occur. To avoid the hazards of asynchronous circuits, designers opt for synchronous implementations more often than necessary.

Synchronous circuits, however, also have inherent problems. Designers must synchronize input signals to the state- machine clock to avoid metastable conditions. Further, changes in input values affect the output values only after the synchronizing clock occurs, increasing the time needed for the circuit to react (ie, latency). Clocking latency and the need for input-signal synchronization can seriously degrade a system’s performance.

Fig 1b is a block-diagram model for an asynchronous sequential-state machine. The model consists of a combinatorial logic block with output signals that determine the next-state values. The block’s input variables are the external input signals and present-state variables. The model assumes that the combinatorial logic has no propagation delay and that the present-state variables take on the next-state variable’s values after a settling time. The settling time equals the longest propagation delay (t_pd) that can occur in the real combinatorial logic block.

When the circuit is stable (defined as having variables that remain the same for a period equal to or longer than t_pd), the present- and next-state variables have the same values. Sometimes, however, the state variables take on several intermediate values before the present- and next-state variables reach stable state. These intermediate values represent unstable states, whereby the output variable values keep changing for a given combination of input values. In extreme cases, the circuit oscillates.

Because the various signal paths through the circuit have different propagation delays, simultaneous changes of two or more input signals could cause unpredictable state transitions. To avoid uncontrolled behavior, therefore, a design should allow only one input variable to change at a time. Further, the time interval between consecutive input-signal changes should be longer than the time necessary to reach a stable state. When these restrictions are enforced, the circuit operates in "fundamental mode."

It’s possible that a circuit implementation can allow two or more state variables to change concurrently as a result of input-signal transitions. Such circuits possess race conditions, with circuit behavior depending on which state variable changes fastest. If, after several temporary state transitions the stable state the circuit achieves is the same, no matter which state variable is faster, the circuit has noncritical races. If the final states differ, the circuit has critical races. A good design must operate in the fundamental mode and avoid critical-race conditions.

Latches hold present-state values

In synchronous-state machines, a flip-flop is the memory element that holds the present-state value. In asynchronous-state machines, the memory unit is the latch; Fig 2a shows such a latch circuit. The product term (A&B) is called the START term. When this term is true, output Z is true. The product term (B&Z), in which one of the input variables is the feedback from the output, is called the HOLD term. Once START is true longer than t_pd, output Z remains set for as long as the HOLD term remains true.

Fig 2b illustrates a model of the asynchronous latch. Assume the primitive gates to have zero delay and that the output of the combinatorial circuit (Z*) is the next-state variable. Output Z takes the value Z* after a time equal to the propagation delay (t_pd) through the circuit. The next-state variable Z* can be expressed as a Boolean equation: Z*(t)=A&B+B&Z(t). The output Z (present-state variable) is Z(t+t_pd)=Z*(t). Except for the block delay, this circuit model can be analyzed as combinatorial logic; therefore, you can study its behavior using a Karnaugh map type called the transition map. Fig 2c shows the transition map for the latch model.

Each column of the transition map represents a combination of the external input variables, and each row represents a combination of the present-state variables. The combinations are arranged so that adjacent rows or columns differ by a change in only one variable. The squares defined by the rows and columns contain the corresponding next-state values (Z*) for the circuit. In Fig 2, because A and B are the external input variables and Z is the only present-state variable, all you need to determine the behavior of this latch is a map of four columns and two rows.

This map contains a number of reference marks that aid in understanding the corresponding circuit’s behavior. Underneath each input-variable name lies a horizontal bar that covers those squares for which the variable is true. Squares have numbers in their corners for convenient reference. The angled arrows between columns on top of the map indicate the level transitions of Z—if any—due to input transitions.

If you define the circuit’s total state as the current combination of input and present-state variables, each square of the transition map has a unique correspondence with a total state of the circuit. Moving from square to square within the map corresponds to changes in the circuit’s total state. When the circuit reaches a square whose next-state value coincides with its respective row value, the circuit has reached a stable state. The transition map shows all stable states circled. The remaining squares represent unstable states.

Transition maps track circuit changes

At this point, note that the state of an asynchronous circuit changes almost immediately after an external input changes, instead of following the edge of a clock as in a synchronous circuit. When analyzing the behavior of an asynchronous circuit using transition maps, remember that when an input variable changes, the circuit’s state change corresponds to an immediate horizontal transition to the column representing the new input combination. If the new value of the next-state Z' coincides with present-state Z, the new state is stable. Otherwise, vertical transitions subsequently occur until the circuit reaches a state for which Z*=Z.

Analyze the map in Fig 2c, which illustrates this behavior. Assume that the input- and output-variable values are AB=00 and Z=0, respectively; then, square 0 represents the circuit’s state and gives the next-state value, Z*=0. Because Z* and Z are the same, the output remains stable. If B changes to "1," the present state is still "0," although square 1 represents the total state. If A now changes to "1," the next-state Z* becomes "1’’ and no longer equals Z. The circuit state moves to square 3. This state is unstable, forcing the latch present state to move vertically to the stable state at square 7, because AB remains "11." In a similar fashion, analyze the next state of the latch each time the input values change.

The analysis also applies to circuits with more than one state-memory element. Fig 3a shows a logic diagram, for which you can deduce by inspecting the corresponding Boolean equations and Karnaugh maps in Fig 3b. The transition map, Fig 3c, is a combination of the two Karnaugh maps, formed by concatenating the corresponding values of Z* and Q*. The values on top of the map represent the present values of the circuit-input variables A and B. The values to the left of the map represent the present-state values (ZQ) of the circuit. The stable states, the squares with next-state values that coincide with the corresponding row values, are circled.

Assume that the system starts in the state corresponding to square 1 (ABZQ=0100). If A then changes to "1," the total state moves to square 3, which shows a next state of "10." The state at square 3 is unstable because ZQ and Z*Q* are different. The circuit state, therefore, moves to square 11, where the next state is "10." This is a stable state (ABZQ=1110) because the present and next states are the same. The circuit stays in this stable state (ABZQ=1110).

If B then changes to "0,’’ the system moves to square 10, showing a next state of "11." Because this state is unstable, the system state moves to the stable state (ABZQ=1011) at square 14. Similarly, you can continue analyzing the rest of the transition map. Refer to Fig 3c for all possible transitions.

For this circuit, each time A sets, Z sets, and when B sets, Z resets. This behavior describes the characteristic of a set/reset flip-flop, whose output depends on the input edge transitions.

Maps chart race conditions

Transition maps provide a valuable tool for analyzing race conditions, which occur when two or more next states change concurrently as the result of an input-value transition. The following examples help illustrate the usefulness of transition maps as an analysis tool:

Case 1: In Fig 4a’s circuit, assume an initial state (ABZQ=1101). As the transition map (Fig 4b) indicates, the present-state variables ZQ and the next-state variables Z*Q* are "01." If the input-variable A changes to "0’’ (AB=01), the next-state Z*Q* becomes 10. Both Z and Q change concurrently, which sets up a race condition. If the path delays for Z and Q are equal, the circuit undergoes the following transition: 01->10->00.

Because the path delays for Z and Q are usually different, however, the transition from 01 to 10 does not occur directly but rather by one of two potential sequences: 01->11->10->00 or 01->00. In this example, the circuit reaches the same stable state "00’’ either way, which illustrates a noncritical race. The time needed to settle in the final state, however, remains uncertain because it depends on the path delays.

Case 2: In Fig 5a’s circuit, assume a starting state of (ABZQ=1101). As the map in this fig shows, when A changes to "0," the following sequences are possible: 01->10->00, 01->00, or 01->11. Thus, two different final stable states are possible for the input transition. This is an example of a critical race. Circuit designs with critical races should be avoided because the outcome of the transitions is unpredictable.

Case 3: The logic diagram in Fig 6a and transition map (Fig 6b) correspond to an unstable circuit. When AB changes from 11 to 01, ZQ transits between the unstable states "01’’ and "11’’ indefinitely, ie, the output Z oscillates for as long as AB=01. Avoid this behavior in the map of a stable circuit.

From analyzing these three cases, it’s evident that, for proper operation and predictability of the circuit behavior, it’s necessary to ensure that only one next-state variable changes for any given input transition.

Use maps to plan designs

Transition maps are useful not only for analyzing asynchronous circuits, but also for synthesizing a design. For example, consider designing a circuit whose output Z follows A’s transitions when B is high and remains stable when B is low. The output Z can be either "0’’ or "1’’ for any given combination of AB values. The circuit cannot be simple combinatorial logic. It must be sequential because the output value depends on the values of the present inputs and on the previous states. The timing diagram for such a circuit appears in Fig 7a.

The first step in designing this circuit is to draw the transition map, assuming that you can implement the circuit with a 2-state-variable state machine. The output Z is one of the present-state variables; Q is the second present-state variable. Because the circuit has two input variables and two present-state variables, the transition map comprises 16 squares (Fig 7b). Each square identifies one combination of input and present-state variables.

The arrows above the transition map indicate desired transitions of Z. As shown, Z’s changes follow the transitions of A when B is "1;" ie, Z changes from "0’’ to "1’’ if Z is not already "1," when AB changes from "01’’ to "11." Z changes from "1’’ to "0’’ if Z is not already "0" when AB changes from "11’’ to "01." No other input transition causes Z to change.

The second step is to fill in the squares with appropriate values of the next-state variables Z*Q*. Remember that Z' and Q* are values that Z and Q take, respectively, after the propagation delay through the circuit. Z* and Q* are actually fictitious variables that serve as an aid to understanding the circuit’s transitional behavior; Z and Q have no physical reality.

Fill out the transition map by following a few rules:

1. Each time an input variable changes, the circuit makes an immediate horizontal transition to the column that identifies the new input combination; ie, a horizontal transition indicates an input change.

2. If the new next-state value coincides with the row value, the circuit has reached a stable state.

3. If the new state is not stable, the circuit moves within the same column until the next- and present-state variables are the same. A vertical transition indicates an output change. Each vertical state transition takes one propagation delay, therefore, to maximize circuit performance, your design should have a minimum number of vertical-state transitions before reaching a stable state.

4. To avoid race conditions, only one next-state variable should change as the result of a state transition.

To begin filling in the map (Fig 7b), assume that the circuit is in the state that square 5 (ABZQ=0101) indicates and that the system is stable at this location. Because this represents a stable state, the next-state equals the present state, so you can write "01’’ in the square and draw a circle around it.

If A now changes to "1," Z should also be "1’’ because B=1. The circuit transits horizontally one square to the right to square 7, where you write "11," showing the change in Z while Q remains the same. In this state, Z*Q*=11 does not match ZQ=01; therefore, the circuit moves vertically (keeping AB=11) to square 15, where ZQ=11. In this square, the circuit reaches a stable state, so you can write "11’’ and circle it.

If A changes again from "1’’ to "0,’’ Z should be "0." The new next-state is "01.’’ Now, the circuit transits horizontally to square 13, where you write "01." Because Z*Q*=01 and ZQ=11, this state is unstable. The circuit, therefore, moves vertically to square 5, which was the original stable state (ABZQ=0101).

So far, the circuit meets the requirement, that the value of Z tracks A’s transitions while B is true. The remaining requirement is that Z does not change when B is false (B=0). Again, starting at square 5 (Fig 7c), when B changes from "1’’ to "0,’’ the circuit moves horizontally to square 4. The value of Z shouldn’t change, but you may want to identify this transition with a new total state. Therefore, toggle the value of Q, and write "00" at square 4. This is an unstable state, so the circuit moves to square 0 (ABZQ=0000), where it will reach a stable state because Z*Q*=ZQ=00. Write "00,’’ and circle it at square 0.

Avoid state collisions

If A now changes from "0’’ to "1," Z should remain "0’’ because B=0 (remember that Z follows A’s changes only when B is high). The circuit moves horizontally to square 2 (ABZQ=1000) where it reaches a stable state. Fill this square with "00,’’ and circle it. If B now changes to "1,’’ the circuit moves to the stable state at square 3 (ABZQ=1100), so you fill this square with "00’’ and circle it. If A now changes to "0," Z remains "0," and the circuit state moves to square 1.

At this point, assign Q either the value "0’’ or "1." If you designate Q to be "0,’’ Z*Q*=ZQ=00, and the circuit would reach a stable state at square 1. This state assignment, however, presents a problem: If A subsequently changes from "0’’ to "1," then Z should move from "0’’ to "1," which would force square 3 to contain 10 as its next state. Because square 3’s next state is already "00," the assignment Q=0 at square 1 causes a state collision.

To avoid the state collision, you must assign Q=1 at square 1 (Fig 7d). With "01’’ at square 1, the state is unstable and the circuit state moves vertically to square 5 (state ABZQ=0101). In a similar way, go through the rest of the states to complete the map (Fig 7d).

The example’s starting value in square 5 is arbitrary. The state assignments for a given function in a transition map can, therefore, differ, depending on the engineer implementing it. The initial choice does not always work, either. The occurrence of collisions may force you to restart the transition-map state assignment from a different initial stable state. Practice eventually yields an intuitive knowledge of the best state assignment, minimizing the number of transitions before arriving at a stable state and eliminating all potential collisions.

Once you fill out the transition map, the third step in synthesizing a design is to generate the Karnaugh maps from the transition map. The first value of each next-state entry corresponds to the value of Z*; the second corresponds to the value of Q*. Fig 7e shows the Karnaugh maps for the example.

Treat don’t cares carefully

From these maps, infer the corresponding Boolean equations. When selecting product terms for the equations, take care to avoid a circuit that exhibits output glitches. A rule of thumb for avoiding such hazards is to designate enough product terms to cover all minterms, and add redundant product terms so that adjacent product terms overlap.

Likewise, you need to treat "don’t cares" (X) carefully. Assign them values that help simplify product terms. Then, however, take those values back to the transition map, and verify that the assignments do not create potential circuit oscillations such as those Case 3 indicates.

In Fig 7d, square 6 has a don’t care next state. The Boolean equations in Fig 7e assume that Z*=1 and Q*=1 in square 6. If, during power-up, the circuit enters the state corresponding to square 6 (ABZQ=1001), the next state is "11," and the circuit moves to stable-state ABZQ=1011 (square 14).

The fourth (and last) step in design synthesis is to draw the logic diagrams for Z and Q. As the logic diagram in

Fig 7f shows, the implementation comprises a 2-level gate circuit. This type of architecture is very convenient for PAL implementations and ASIC applications; it lets you build convenient special-purpose modules with minimum propagation delay. The present-state variable Z is the actual output of the circuit, and Q is an auxiliary variable. Recall that Z* and Q*are fictitious variables that represent the next-state values in the asynchronous-circuit model. The present-state variables Z and Q are the only variables that physically exist and that appear in the circuit-logic diagram.

By using more complex and formal procedures, transition-map analysis can handle circuits with three or more external input variables. Such cases go beyond the scope of this article, however, which provides a conceptual understanding of asynchronous circuits. In general, synchronous circuits may be easier to understand and design. When speed is a high priority, however, asynchronous logic is the answer. Transition-map analysis can guide you to a reliable implementation.

Thanks to Dung Do for reviewing this article and contributing to the concepts presented in it.