Asynchronous Design: Flow Tables and Race-Free Assignment

Design a circuit with no clock: write a primitive flow table, merge its rows, and choose state codes with no critical race.

You Will Be Able To

  • Write a primitive flow table from a word specification.
  • Find compatible rows and merge them into a smaller flow table.
  • Choose codes so every move changes one variable, using a spare code as an extra state.
  • Check an assignment by simulation with many sets of loop delays.
Lesson
G7.10
Time
40 min
Runs on
Your browser
Check
5 questions

Two engineers built the same flow table with different state codes. One circuit worked for every delay. The other failed only on some chips. The lab builds each one nine times, with every pair of loop delays from 1 to 3.

AssignmentCodes A, B, CWrong states, 10 changes x 9 delay pairs
Race-free, with a spare code00, 01, 11 (D = 10)0
Careless assignment00, 11, 016

Measured: the lab below, on Icarus Verilog 12.

From Words to a Primitive Flow Table

The specification: inputs a and b; z rises when b rises while a = 1, and z falls when a falls. Only one input changes at a time.

A primitive flow table has one row per stable total state: each row is stable in exactly one column. Start from both inputs low and ask, for each row, where each single input change leads.

Rowab = 00011110zMeaning
1(1)4–20both low
21–3(2)0a rose first
3–4(3)61b rose while a = 1
41(4)5–0b rose while a = 0
5–4(5)20a rose while b = 1
61–3(6)1b fell, a still 1

Stable entries are in brackets. A dash marks a change that cannot happen: it would need both inputs to change.

Row 3 and row 5 both sit at ab = 11, but they remember different histories. That is why the table needs more rows than input columns.

Merging Compatible Rows

Two rows are compatible when their outputs agree and no column has two different specified entries. A dash agrees with anything. Compatible rows can share one state.

Which Rows Can Share a StateA line joins two compatible rows. Rows 2 and 4 conflict under ab = 11 (3 against 5); so do rows 2 and 5.
  • Neutral
  • Structure
Which rows can share a stateA line joins two compatible rows. Rows 2 and 4 conflict under ab = 11 (3 against 5); so do rows 2 and 5. neutral Row 1 z = 0 neutral Row 2 z = 0 neutral Row 4 z = 0 neutral Row 5 z = 0 neutral Row 3 z = 1 neutral Row 6 z = 1
  1. neutral Row 1z = 0
    • Row 2
    • Row 4
    • Row 5
  2. neutral Row 2z = 0
  3. neutral Row 3z = 1
    • Row 6
  4. neutral Row 4z = 0
    • Row 5
  5. neutral Row 5z = 0
  6. neutral Row 6z = 1
  1. Compatible pairs

    Five pairs are compatible: 1-2, 1-4, 1-5, 4-5 and 3-6.

  2. A group of three

    Rows 1, 4 and 5 are compatible in every pair, so they can all merge into one state, A.

  3. The cover

    Row 2 is left on its own as B. Rows 3 and 6 merge into C. Six rows become three.

Read the diagram as text
  • Row 1: z = 0
  • Row 2: z = 0
  • Row 4: z = 0
  • Row 5: z = 0
  • Row 3: z = 1
  • Row 6: z = 1
  • Row 1 → Row 2
  • Row 1 → Row 4
  • Row 1 → Row 5
  • Row 4 → Row 5
  • Row 3 → Row 6

The merger diagram of the primitive table. Each row must land in exactly one merged state.

StateRowsab = 00011110z
A1, 4, 5(A)(A)(A)B0
B2A–C(B)0
C3, 6AA(C)(C)1

The merged flow table. Every move goes to another state: A to B, B to A and C, C to A.

A Race-Free Assignment

Each move between two states should change exactly one state variable. A move that changes two is a race, and it is critical if some order ends in the wrong state. So states that move to each other need adjacent codes, one bit apart.

The Two-Variable Codes, with Adjacent Codes JoinedThe four codes of y1 y2 on a square. Each side joins two codes that differ in one bit; the diagonals differ in two.
  • Control / FSM
  • Structure
The two-variable codes, with adjacent codes joinedThe four codes of y1 y2 on a square. Each side joins two codes that differ in one bit; the diagonals differ in two. control 00 A control 01 B control 11 C control 10 D, spare A to B, B to AB to CC to DD to A
  1. control 00A
    • A to B, B to A → 01
  2. control 01B
    • B to C → 11
  3. control 11C
    • C to D → 10
  4. control 10D, spare
    • D to A → 00
  1. Place A and B

    A and B move to each other, so they take adjacent codes: 00 and 01.

  2. Place C

    B moves to C, so C goes next to B: 11. Now C and A are on a diagonal.

  3. Use the spare code

    C moves to A in two columns. Route it through D = 10: C to D, then D to A, one bit per step.

Read the diagram as text
  • 00: A
  • 01: B
  • 11: C
  • 10: D, spare
  • 00 → 01: A to B, B to A
  • 01 → 11: B to C
  • 11 → 10: C to D
  • 10 → 00: D to A

Three states that all move to each other cannot be pairwise adjacent on a square. The fourth code carries the diagonal move.

The Race-Free Assignment, Step by Step
Flow table. A circled entry is stable. The ringed cell is the present state and input.
State (code)ab = 00ab = 01ab = 11ab = 10z
A 00AAAB0
B 01A–CB0
C 11DDCC1
D 10AA––0

A is already stable under 00.

StepInputPathOutput
000A0
110A → B0
211B → C1
301C → D → A0
411A0
510A → B0
611B → C1
710C1
800C → D → A0
901A0
1000A0
Every step in words
  1. Start in A, stable under 00.
  2. A → B: stable in B.
  3. B → C: stable in C.
  4. C → D → A: stable in A.
  5. A is already stable under 11.
  6. A → B: stable in B.
  7. B → C: stable in C.
  8. C is already stable under 10.
  9. C → D → A: stable in A.
  10. A is already stable under 01.
  11. A is already stable under 00.

  1. Step 1. a rises: A to B, 00 to 01. One variable changes.
  2. Step 2. b rises while a = 1: B to C, 01 to 11. One variable again, and z = 1.
  3. Step 3. a falls. C must go to A, but 11 to 00 is two variables. C's entry is D (10) instead, and D goes on to A: a cycle, one variable per step.
  4. Step 8. The same cycle under ab = 00. No move of this table changes two variables at once.

The lab's good circuit as a flow table, on the lab's input stream. D is the spare code, used only in passing.

K-maps of the encoded table give the excitation equations, with the dashes as don't-cares. Y1 = y2 b + y1 y2 and Y2 = a b' + y2 a.

A Careless Assignment Has a Critical Race
Flow table. A circled entry is stable. The ringed cell is the present state and input.
State (code)ab = 00ab = 01ab = 11ab = 10z
A 00AAAB0
B 11A–CB0
C 01AACC1
X 10AAAB0

A → B: stable in B. Race: the state variables can change in different orders; critical — it can end in B or C.

Orders of the state-variable changes from A:

  • A → X → B
  • A → C
  • A → B
StepInputPathOutput
000A0
110A → B · race (critical)0
Every step in words
  1. Start in A, stable under 00.
  2. A → B: stable in B. Race: the state variables can change in different orders; critical — it can end in B or C.

  1. Step 1. a rises: A to B is 00 to 11. If y2 changes first the circuit lands in C (01), which is stable under ab = 10. Critical.

A = 00, B = 11, C = 01. X is the unused code 10, with the entries the lab's bad equations give it.

Asked in interviews
  1. How do you design an asynchronous state machine?

    Write a primitive flow table from the specification, one stable state per row. Merge compatible rows. Choose codes so every move changes one variable, adding cycles through spare codes where needed. Then derive the excitation equations and check for hazards.

  2. What makes a state assignment race-free?

    Every move between states changes exactly one state variable, or goes through a chain of one-variable steps. Then no order of the variable changes can end anywhere else.

  3. Three states all move to each other. Two state variables are enough?

    Yes, if one move goes through the spare fourth code as a cycle. Otherwise add a third variable, or give a state two codes.

Try It

Each line shows the state of all nine copies of each circuit after one input change. The good circuit is right in every copy.

The bad circuit fails when a rises. In copies 3, 6 and 7, y2 is faster, and the circuit lands in C, stable under ab = 10.

Delete the term y1 y2 from the good Y1, hoping C goes straight to A, and run it. All nine copies now fail on change 7: want C, got B.

That term was also C's hold under ab = 10, so C falls to B. The moves from C to A still end in A: both neighbours of 11 lead there, a noncritical race.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: ab=10 want B good BBBBBBBBB bad BBBCBBCCB ab=11 want C good CCCCCCCCC bad CCCCCCCCC ab=01 want A good AAAAAAAAA bad AAAAAAAAA ab=11 want A good AAAAAAAAA bad AAAAAAAAA ab=10 want B good BBBBBBBBB bad BBBCBBCCB ab=11 want C good CCCCCCCCC bad CCCCCCCCC ab=10 want C good CCCCCCCCC bad CCCCCCCCC ab=00 want A good AAAAAAAAA bad AAAAAAAAA ab=01 want A good AAAAAAAAA bad AAAAAAAAA ab=00 want A good AAAAAAAAA bad AAAAAAAAA wrong states in 90: good 0, bad 6
Read included file: tb.sv
// tb.sv: the bench (read-only). Each circuit is built nine times, with loop delays d1, d2 from 1 to 3.
// One input change every 20 time units; then every copy is compared with the flow table.
module tb;
  logic r = 1, a = 0, b = 0;
  wire [8:0] g1, g2, gz, b1, b2, bz;
  for (genvar i = 0; i < 9; i++) begin : copies
    good #(.D1(1 + i / 3), .D2(1 + i % 3)) g (.r(r), .a(a), .b(b), .y1(g1[i]), .y2(g2[i]), .z(gz[i]));
    bad  #(.D1(1 + i / 3), .D2(1 + i % 3)) w (.r(r), .a(a), .b(b), .y1(b1[i]), .y2(b2[i]), .z(bz[i]));
  end
  string ab   = "10110111101110000100";   // ten input words a b, one change each
  string want = "BCAABCCAAA";             // the flow table's state after each change
  string gs, bs;
  int good_wrong = 0, bad_wrong = 0;
  function automatic string name_good(logic y1, y2);
    case ({y1, y2}) 2'b00: return "A"; 2'b01: return "B"; 2'b11: return "C"; default: return "?"; endcase
  endfunction
  function automatic string name_bad(logic y1, y2);
    case ({y1, y2}) 2'b00: return "A"; 2'b11: return "B"; 2'b01: return "C"; default: return "?"; endcase
  endfunction
  initial begin
    #20 r = 0;
    for (int s = 0; s < 10; s++) begin
      {a, b} = {ab[2 * s] == "1", ab[2 * s + 1] == "1"};
      #20 gs = ""; bs = "";
      for (int i = 0; i < 9; i++) begin
        gs = {gs, name_good(g1[i], g2[i])}; bs = {bs, name_bad(b1[i], b2[i])};
        if (name_good(g1[i], g2[i]) != want.substr(s, s)) good_wrong++;
        if (name_bad(b1[i], b2[i]) != want.substr(s, s)) bad_wrong++;
      end
      $display("ab=%b%b want %s  good %s  bad %s", a, b, want.substr(s, s), gs, bs);
    end
    $display("wrong states in 90: good %0d, bad %0d", good_wrong, bad_wrong);
  end
endmodule

Check Yourself

ConceptWhat does each row of a primitive flow table have?
ConceptTwo rows have z = 0. Under ab = 11, one says 3 and the other says a dash. In every other column their entries match. Are they compatible?
ConceptState P moves to Q, Q to R, and R to P. With two state variables, what is the fix?
Predict the outputThe program counts the pairs among four codes that differ in exactly one bit. Predict the exact line.
module tb;
  logic [1:0] d;
  int n = 0;
  initial begin
    for (int i = 0; i < 4; i++)
      for (int j = i + 1; j < 4; j++) begin
        d = i[1:0] ^ j[1:0];
        if (d == 2'b01 || d == 2'b10) n++;
      end
    $display("%0d", n);
  end
endmodule
ConceptIn the good circuit, why is the entry of D under ab = 00 equal to A and not D?

Common Mistakes

Wrong Pick state codes before drawing which states move to which.

Codes chosen without that picture put some moves two bits apart. In the lab, A = 00 to B = 11 ended in the wrong state for 3 of 9 delay pairs.

Fix Draw which states move to which, and give every such pair adjacent codes.

Wrong Merge two rows that have different outputs.

A merged row stands for one state. If its stable entries need different z, no single output fits.

Fix Merge rows only when their specified entries agree and their outputs agree.

Wrong Give up when three states all move to each other.

Three states cannot all be adjacent on a square of two-bit codes. But the fourth code is free.

Fix Route one move through the spare code: a cycle of two one-variable steps.

Wrong Leave the spare code's entry stable in the column where it is used.

The circuit then stops in the spare code and never reaches the target state.

Fix In that column, make the spare code's entry the target state, so the cycle ends where it should.

Remember

  • A primitive flow table has one stable total state per row; one input changes at a time.
  • Merge rows whose outputs agree and whose specified entries never conflict; a dash agrees with anything.
  • Give states that move to each other adjacent codes, so each move changes one variable.
  • When states cannot all be adjacent, route a move through a spare code as a cycle.

Practice

Report a problem with this page