Asynchronous Sequential Circuits: Analysis

Analyse a circuit with feedback and no clock: find its state variables, build its flow table, and spot races, cycles and oscillation.

You Will Be Able To

  • Cut each feedback loop and name its state variable and excitation.
  • Build the excitation table and the flow table, and mark the stable states.
  • Tell a critical race from a noncritical one, and predict where each ends.
  • Recognise a cycle and an oscillation in a flow table.
Lesson
G7.9
Time
35 min
Runs on
Your browser
Check
5 questions

Three copies of one small circuit with no clock got the same input change. They ended in three different states. Only the delays in their feedback loops differed.

Loop delaysState y1 y2 after x rises
d1 = 1, d2 = 6 (loop 1 faster)10
d1 = 6, d2 = 1 (loop 2 faster)01
d1 = 2, d2 = 2 (equal)11

Measured: the lab below, on Icarus Verilog 12. Gates take 1 time unit; the loop delays are the delay elements.

Feedback Loops Are the State

An asynchronous sequential circuit has no clock. It remembers through feedback: a gate output that comes back to the circuit's own inputs. The SR latch of G5.4 is one.

To analyse one, cut each loop and put a delay element in it. The value going into the cut is the excitation Y. The value coming out is the state variable y. When Y and y differ, the loop is about to change.

Each Loop Cut at a Delay ElementThe gates compute Y1 and Y2 from x, y1 and y2. Each excitation passes a delay element and returns as a state variable.
  • I/O
  • Datapath
  • Neutral
  • Data
Each loop cut at a delay elementThe gates compute Y1 and Y2 from x, y1 and y2. Each excitation passes a delay element and returns as a state variable. io Input x one change at a time datapath Gates no memory neutral Delay d1 Y1 to y1 neutral Delay d2 Y2 to y2 Y1Y2y1y2
  1. io Input xone change at a time
    • Gates
  2. datapath Gatesno memory
    • Y1 → Delay d1
    • Y2 → Delay d2
  3. neutral Delay d1Y1 to y1
    • y1 → Gates
  4. neutral Delay d2Y2 to y2
    • y2 → Gates
  1. Excitations

    From x and the present state y1 y2, the gates settle to Y1 and Y2.

  2. State variables

    Each delay element passes its Y on as y after its own delay. The faster loop changes first.

  3. Stable

    When Y1 = y1 and Y2 = y2, nothing is waiting to change: the circuit is stable.

Read the diagram as text
  • Input x: one change at a time
  • Gates: no memory
  • Delay d1: Y1 to y1
  • Delay d2: Y2 to y2
  • Input x → Gates
  • Gates → Delay d1: Y1
  • Gates → Delay d2: Y2
  • Delay d1 → Gates: y1
  • Delay d2 → Gates: y2

The lab circuit cut this way. Its two delay elements are the buf gates d1 and d2.

Loop 1 Faster: d1 = 1, d2 = 6
Loop 1 Faster: d1 = 1, d2 = 6g1 · NOTy1n=0g2 · NOTy2n=1g3 · ORp1=1g4 · ORp2=0g5 · ANDY1=1g6 · ANDY2=0d1 · BUFy1=1d2 · BUFy2=0x=1
x=1
g1 · NOTy1=1 → y1n=0
g2 · NOTy2=0 → y2n=1
g3 · ORy1=1, y2n=1 → p1=1
g4 · ORy2=0, y1n=0 → p2=0
g5 · ANDx=1, p1=1 → Y1=1
g6 · ANDx=1, p2=0 → Y2=0
d1 · BUFY1=1 → y1=1
d2 · BUFY2=0 → y2=0
Read the connections
GateKindInputsOutput
g1NOTy1y1n
g2NOTy2y2n
g3ORy1, y2np1
g4ORy2, y1np2
g5ANDx, p1Y1
g6ANDx, p2Y2
d1BUFY1y1
d2BUFY2y2

Outputs: y1, y2. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 17. Settled after 17 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617y1xx0000000000001111y2xxxxxxx00000000000
Scroll horizontally ↔
Every computed frame
Timey1y2
0xx
1xx
20x
30x
40x
50x
60x
700
800
900
1000
1100
1200
1300
1410
1510
1610
1710

  1. Step 11 · Settled at 00. With `x` = 0 both AND gates give 0. The loops have settled at `y1` `y2` = 00.
  2. Step 13 · Both excited. `x` rose at 12. At 13 both AND gates switch: `Y1` = `Y2` = 1, but `y1` and `y2` are still 00. Both variables want to change.
  3. Step 14 · y1 wins. The short delay passes `y1` = 1 at 14. The state is now 10.
  4. Step 17 · Y2 withdrawn. `y1n` fell, so `p2` and then `Y2` fall at 17. The change of `y2` was due at 19 and is cancelled.
  5. Step 18 · Settled at 10. Row 10 is stable under x = 1. The race ended in 10.

The lab circuit with loop delays 1 and 6. Step it: the faster loop decides where the race ends.

The circuit works in fundamental mode: one input changes at a time, and only when the circuit is stable. Then every loop settles before the next input change.

Excitation Table and Flow Table

The excitation table gives Y1Y2 for every present state y1y2 and input. An entry equal to its own row is stable. Any other entry is unstable: the circuit moves on.

y1 y2x = 0x = 1
00(00)11
0100(01)
1100(11)
1000(10)

Y1 Y2 of the lab circuit. Stable entries are in brackets. The row 00 under x = 1 is excited in both variables.

A flow table gives the same table with a name for each state. Stable entries are circled. It describes the machine without the codes, until races need them.

The Lab Circuit as a Flow Table
Flow table. A circled entry is stable. The ringed cell is the present state and input.
State (code)x = 0x = 1
a 00ac
b 01ab
c 11ac
d 10ad

c → a: stable in a. Race: the state variables can change in different orders; noncritical — every order ends in a.

Orders of the state-variable changes from c:

  • c → b → a
  • c → d → a
  • c → a
StepInputPath
00a
11a → c · race (critical)
20c → a · race (noncritical)
Every step in words
  1. Start in a, stable under 0.
  2. a → c: stable in c. Race: the state variables can change in different orders; critical — it can end in b or c or d.
  3. c → a: stable in a. Race: the state variables can change in different orders; noncritical — every order ends in a.

  1. Step 0. Start in a (00), stable under x = 0: its entry in that column is a itself.
  2. Step 1. x rises. Row a says c (11): both variables must change. Depending on which changes first, the circuit ends in b, c or d. That is a critical race.
  3. Step 2. x falls. From c (11) the target is a (00), again two variables. But b and d also lead to a under x = 0: a noncritical race.

Step the input changes. The table lists every order of the variable changes, and which stable state each one reaches.

Critical and Noncritical Races

A race is a move in which two or more state variables must change. They never change at exactly the same moment. Whichever goes first, the circuit reads the row it lands in.

Loop 2 Faster: d1 = 6, d2 = 1
Loop 2 Faster: d1 = 6, d2 = 1g1 · NOTy1n=1g2 · NOTy2n=0g3 · ORp1=0g4 · ORp2=1g5 · ANDY1=0g6 · ANDY2=1d1 · BUFy1=0d2 · BUFy2=1x=1
x=1
g1 · NOTy1=0 → y1n=1
g2 · NOTy2=1 → y2n=0
g3 · ORy1=0, y2n=0 → p1=0
g4 · ORy2=1, y1n=1 → p2=1
g5 · ANDx=1, p1=0 → Y1=0
g6 · ANDx=1, p2=1 → Y2=1
d1 · BUFY1=0 → y1=0
d2 · BUFY2=1 → y2=1
Read the connections
GateKindInputsOutput
g1NOTy1y1n
g2NOTy2y2n
g3ORy1, y2np1
g4ORy2, y1np2
g5ANDx, p1Y1
g6ANDx, p2Y2
d1BUFY1y1
d2BUFY2y2

Outputs: y1, y2. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 17. Settled after 17 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617y1xxxxxxx00000000000y2xx0000000000001111
Scroll horizontally ↔
Every computed frame
Timey1y2
0xx
1xx
2x0
3x0
4x0
5x0
6x0
700
800
900
1000
1100
1200
1300
1401
1501
1601
1701

  1. Step 14 · y2 wins. This time `y2` = 1 arrives first, at 14. The state is 01.
  2. Step 17 · Y1 withdrawn. `p1` and then `Y1` fall. The change of `y1` that was due at 19 never happens.
  3. Step 18 · Settled at 01. Same gates, same input change, a different stable state.

Only the two loop delays differ from the figure above. The circuit ends in 01, not 10.

MoveOne orderOther orderBoth togetherRace
00 to 11, x = 110: stable, ends 1001: stable, ends 01ends 11critical
11 to 00, x = 001: goes to 0010: goes to 00ends 00noncritical

The x = 1 row is measured: the lab's three delay sets give the three ends. The x = 0 row is read from the excitation table.

A race is critical when different orders can end in different stable states. It is noncritical when every order ends in the same one. A critical race is a design error.

Cycles and Oscillation

A cycle is a path through several unstable states before a stable one. Each step can change a single variable, so a cycle has no race.

A Cycle Through Unstable States
Flow table. A circled entry is stable. The ringed cell is the present state and input.
State (code)x = 0x = 1
p 00pq
q 01pr
r 11qr

r → q → p: stable in p.

StepInputPath
00p
11p → q → r
20r → q → p
Every step in words
  1. Start in p, stable under 0.
  2. p → q → r: stable in r.
  3. r → q → p: stable in p.

  1. Step 1. x rises. p is unstable and goes to q (01), and q is unstable too, so it goes on to r (11). Each move changes one variable: no race.
  2. Step 2. x falls. r goes to q and q to p: another cycle, the other way round.

A cycle is a path through unstable states that ends in a stable one. Designers use cycles to avoid races.

If a column has no stable entry on the path at all, the circuit never settles: it oscillates. The ring of G5.9 is the simplest case. A flow table shows it as a loop of unstable entries.

Asked in interviews
  1. What is a race in an asynchronous circuit?

    A move where two or more state variables must change. Delays decide which changes first. It is critical when different orders end in different stable states, and noncritical when they all end in the same one.

  2. What is fundamental mode?

    An operating rule for asynchronous circuits: one input changes at a time, and only after the circuit has settled. The flow table describes the circuit only under that rule.

  3. How do you find the state variables of a circuit with no clock?

    Find every feedback loop and cut it. Put a delay element at the cut: its output is the state variable, its input the excitation. Then write the excitation equations from the gates.

Try It

The first line is before x changes: all three copies settled at 00. After x rises they end in 10, 01 and 11.

When x falls, all three return to 00. That race is noncritical.

Try D1 = 1 and D2 = 3 in copy a, and predict the end state before you run it. Then try 3 and 1.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: x=0, settled: d1<d2 00 d1>d2 00 d1=d2 00 x=1, settled: d1<d2 10 d1>d2 01 d1=d2 11 x=0 again: d1<d2 00 d1>d2 00 d1=d2 00
Read included file: tb.sv
// tb.sv: the bench (read-only). Three copies with different loop delays. x rises once, then falls.
module tb;
  logic x = 0;
  wire a1, a2, b1, b2, c1, c2;
  race #(.D1(1), .D2(6)) a (.x(x), .y1(a1), .y2(a2));   // loop 1 faster
  race #(.D1(6), .D2(1)) b (.x(x), .y1(b1), .y2(b2));   // loop 2 faster
  race #(.D1(2), .D2(2)) c (.x(x), .y1(c1), .y2(c2));   // equal delays
  initial begin
    #20 $display("x=0, settled:   d1<d2 %b%b   d1>d2 %b%b   d1=d2 %b%b", a1, a2, b1, b2, c1, c2);
    x = 1;
    #30 $display("x=1, settled:   d1<d2 %b%b   d1>d2 %b%b   d1=d2 %b%b", a1, a2, b1, b2, c1, c2);
    x = 0;
    #30 $display("x=0 again:      d1<d2 %b%b   d1>d2 %b%b   d1=d2 %b%b", a1, a2, b1, b2, c1, c2);
  end
endmodule

Check Yourself

ConceptAn entry of the excitation table equals its own row. What does that mean?
ConceptWhy does the lab end in three different states after the same input change?
Predict the outputCopy a of the lab gets D1 = 1 and D2 = 3. The program raises x and prints y1y2 when the circuit has settled. Predict the exact line.
// race: a circuit with two feedback loops and no clock. Each loop has a delay element: d1 in loop 1, d2 in loop 2.
// The gates compute the excitations Y1 = x(y1 + y2') and Y2 = x(y2 + y1'); the delay elements return them as y1, y2.
module race #(parameter int D1 = 1, D2 = 6) (input wire x, output wire y1, y2);
  wire y1n, y2n, p1, p2, Y1, Y2;
  not #1 g1 (y1n, y1);
  not #1 g2 (y2n, y2);
  or  #1 g3 (p1, y1, y2n);
  or  #1 g4 (p2, y2, y1n);
  and #1 g5 (Y1, x, p1);
  and #1 g6 (Y2, x, p2);
  buf #(D1) d1 (y1, Y1);                 // the delay in loop 1
  buf #(D2) d2 (y2, Y2);                 // the delay in loop 2
endmodule

module tb;
  logic x = 0;
  wire y1, y2;
  race #(.D1(1), .D2(3)) a (.x(x), .y1(y1), .y2(y2));
  initial begin
    #20 x = 1;
    #30 $display("%b%b", y1, y2);
  end
endmodule
ConceptWhich race can be left in a design?
ConceptWhat is a cycle in a flow table?

Common Mistakes

Wrong Assume both state variables change at the same moment.

Real loops have different delays. In the lab, the same input change ended in 10, 01 or 11, depending on which loop was faster.

Fix Follow every order: one variable first, the other first, and both together. A race is critical when the ends differ.

Wrong Change two inputs at once and expect the flow table to say what happens.

Fundamental mode assumes one input change at a time, with the circuit stable before the next. Two changes together are a race on the inputs.

Fix Keep one input change per step, and wait until the circuit is stable.

Wrong Read the next state from the excitation table and stop there.

An unstable entry means the circuit keeps moving. From the new state the same column gives the next move, until an entry equals its own row.

Fix Follow the column until you reach a stable entry, or find a loop with none.

Wrong Call every two-variable change a bug.

A noncritical race ends in the same stable state whatever the order. In the lab, 11 back to 00 under x = 0 always ended in 00.

Fix List the stable states each order reaches. Fix only races that can end in different ones.

Remember

  • Cut each feedback loop at a delay: its output is a state variable y, its input the excitation Y.
  • An entry equal to its own row is stable; otherwise the circuit keeps moving down the column.
  • A race changes two or more variables; it is critical when different orders end in different stable states.
  • A cycle passes through unstable states to a stable one; a loop with no stable state oscillates.

Practice

Report a problem with this page