Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 57 ยท State Machines

Asynchronous Sequential Circuits and Races

Learn asynchronous sequential circuits: fundamental mode, flow tables, stable states, critical and non-critical races, with runnable Python simulations.

Every state machine you have designed so far was synchronous: a clock tells the flip-flops exactly when to look at their inputs, and between clock edges everything else is allowed to be messy. That clock is a great simplification, but it is a choice. An asynchronous sequential circuit has no clock. Its memory is the feedback of the circuit itself, the same loops of wire that make an SR latch remember a bit, and its state changes whenever an input changes.

Asynchronous design is harder, but you meet it everywhere: the latches inside every flip-flop are asynchronous circuits, arbiters and synchronizers are asynchronous, and some low-power and very fast systems drop the global clock completely. This lesson explains the vocabulary (fundamental mode, flow table, stable and unstable states), shows an asynchronous circuit in action, and teaches the problem that dominates this kind of design: races.

Synchronous versus asynchronous

Synchronous Asynchronous
Timing a clock decides when state changes any input change can start a state change
Memory flip-flops feedback loops (delays and gates)
Design effort tools and rules make it routine you must manage delays, races and hazards by hand
Speed limited by the slowest path plus margin can run as fast as the circuit allows
Typical use processors, FSMs, counters latches, handshakes, arbiters, clock-crossing

A general asynchronous circuit has combinational logic with some outputs fed back to its own inputs through delays. The fed-back signals are the secondary variables y (the present state), and the signals going into the delays are the excitation variables Y (the next state). The inputs from the outside are x. The circuit is stable when Y = y (the logic is asking for the state it already has) and unstable when Y โ‰  y, in which case y follows Y after a delay and the logic is evaluated again.

Fundamental mode

To analyze such circuits we assume fundamental mode operation:

  1. Only one input changes at a time.
  2. The next input change happens only after the circuit has settled into a stable state.

Under these rules the behavior is a clean sequence: input changes, the circuit passes through zero or more unstable states, and it lands in a stable state, ready for the next input change. A table that lists the next state for each present state and each input combination is called a flow table. In a flow table, a stable entry (where the next state equals the row's own state) is shown circled or in brackets, and an unstable entry tells you where the circuit moves.

The program below builds the flow table of a gated D latch, which is the smallest useful asynchronous circuit: the state is Q, the inputs are the gate G and the data D, and the excitation is Y = D when G = 1, and Y = Q otherwise. Then it applies one input change at a time and shows how the circuit settles.

Python A flow table in fundamental mode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the table, the entries in brackets are stable. Look at the column G D = 11: for Q = 0 the entry is 1 (unstable, the state must move to 1), while for Q = 1 the entry [1] is stable. In the trace, the input change G โ†’ 1 while D = 1 puts the circuit into an unstable state, and one step later it settles at Q = 1. After G โ†’ 0 the latch is closed, so the later change of D does nothing: Q stays at 0, which is exactly what "holding" means. This view also explains the forbidden state of an SR latch: it is a place where fundamental mode breaks down, because two inputs return to their safe values at the same time and the circuit cannot know which one arrived first.

Races

Real circuits have unequal delays. Suppose the flow table asks the circuit to go from state 00 to state 11 after an input change. There are two state variables to change, and each travels through its own delay. Which one changes first? Nobody knows. That situation is a race.

  • If the circuit ends in the same stable state however the race turns out, it is a non-critical race: harmless.
  • If the final stable state depends on who wins, it is a critical race: the circuit becomes unpredictable, and you must remove it.

Why would the result differ? Because after the first variable has changed, the circuit sits in an intermediate state (10 or 01) and the flow table is read for that new state. If the intermediate state happens to be stable for the current input, the circuit stops there, and never reaches 11.

The program below finds every stable state a transition can end in, by exploring the cases where one variable changes first, the other changes first, or both change together. It analyzes two versions of the same machine: the first jumps from 00 to 11 in one step, the second goes through the intermediate state 01, so only one variable changes at a time.

Python Finding critical races

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Version 1 has a critical race: the move 00 โ†’ 11 can end in 01, 10 or 11, because both intermediate states are stable for x = 1. The move from 11 back to 00 is a non-critical race, since both 10 and 01 lead on to 00. Version 2 fixes the problem by making the circuit pass through 01: that state is unstable for x = 1 and leads to 11, so there is exactly one possible path.

Removing races

There are two standard remedies:

  1. Choose a race-free state assignment. When you encode the states with binary codes, give adjacent transitions codes that differ in only one bit (adjacent codes, as in a Gray code or as in the Karnaugh map labels). If no transition needs two bits to change, there is no race. This is the same freedom you used in state assignment, but now it is mandatory.
  2. Add extra states or a transition path. If an assignment with single-bit changes does not exist, add extra rows to the flow table whose only job is to guide the circuit along a safe path, as Version 2 did. Another way is to direct the circuit through an unstable state, so that the final stable state is forced.

Other trouble comes from hazards, covered in don't cares and hazards: a glitch in the combinational logic can look like a real change to a feedback loop and send it into the wrong state, which a clocked circuit would simply ignore. Asynchronous logic therefore needs hazard-free (redundant-term) implementations in the feedback path.

The design procedure

Putting it together, the classic procedure for a fundamental-mode circuit is:

  1. Write the primitive flow table: one stable state per input combination you need.
  2. Merge compatible rows to reduce the number of states, as in state reduction.
  3. Assign binary codes so that transitions are race-free, adding rows if necessary.
  4. Derive excitation maps (K-maps for each Y) and simplify them, taking care to avoid hazards.
  5. Draw the circuit with the delays in the feedback paths (or rely on the gate delays).

A clocked design hides all this: the clock waits for everything to settle, so races and glitches between the edges do not matter. That is the reason most engineers use asynchronous circuits only in small, carefully analyzed places.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the defining difference between a synchronous and an asynchronous sequential circuit?

    A synchronous circuit uses a clock to decide when state changes. An asynchronous one reacts to input changes directly, using feedback for memory.
  2. 2. In a flow table, when is a state stable for a given input?

    Stable means Y = y: the logic is asking for the state the circuit is already in.
  3. 3. What does fundamental mode assume?

    Single-input changes with enough time to settle make the behavior a clean sequence of stable states.
  4. 4. Which situation is a critical race?

    If the outcome depends on which delay is shorter, the behavior is unpredictable. That is a critical race.
  5. 5. How can you remove a critical race?

    If only one variable changes per step the race cannot occur, either through adjacent codes or by routing through extra states.

Summary

  • An asynchronous sequential circuit has no clock; feedback in the combinational logic provides the memory, and the state changes when inputs change.
  • Fundamental mode assumes one input change at a time and enough time to settle; a flow table lists stable and unstable states under that assumption.
  • A circuit is stable when the excitation Y equals the present state y; otherwise y follows Y until it is.
  • When a transition changes two or more state variables, a race occurs; if the final state depends on the delays it is a critical race and must be eliminated.
  • Races are removed with adjacent (one-bit-change) state assignments or extra intermediate states, and hazards must also be avoided in the feedback logic.

Next: ROM, RAM and Memory Organization