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.
| Assignment | Codes A, B, C | Wrong states, 10 changes x 9 delay pairs |
|---|---|---|
| Race-free, with a spare code | 00, 01, 11 (D = 10) | 0 |
| Careless assignment | 00, 11, 01 | 6 |
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.
| Row | ab = 00 | 01 | 11 | 10 | z | Meaning |
|---|---|---|---|---|---|---|
| 1 | (1) | 4 | – | 2 | 0 | both low |
| 2 | 1 | – | 3 | (2) | 0 | a rose first |
| 3 | – | 4 | (3) | 6 | 1 | b rose while a = 1 |
| 4 | 1 | (4) | 5 | – | 0 | b rose while a = 0 |
| 5 | – | 4 | (5) | 2 | 0 | a rose while b = 1 |
| 6 | 1 | – | 3 | (6) | 1 | b 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.
- Neutral
- Structure
- Compatible pairs
Five pairs are compatible: 1-2, 1-4, 1-5, 4-5 and 3-6.
- A group of three
Rows 1, 4 and 5 are compatible in every pair, so they can all merge into one state, A.
- 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.
| State | Rows | ab = 00 | 01 | 11 | 10 | z |
|---|---|---|---|---|---|---|
| A | 1, 4, 5 | (A) | (A) | (A) | B | 0 |
| B | 2 | A | – | C | (B) | 0 |
| C | 3, 6 | A | A | (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.
- Control / FSM
- Structure
- Place A and B
A and B move to each other, so they take adjacent codes: 00 and 01.
- Place C
B moves to C, so C goes next to B: 11. Now C and A are on a diagonal.
- 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.
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.
Asked in interviews
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.
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.
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.
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 6Read 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
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.