Give a three-state asynchronous machine state codes and a transition table with no critical race, for every pair of loop delays.
Hardware context: An asynchronous controller that must behave the same on every chip, whatever its loop delays. Choose state codes and a transition table for a three-state machine with no critical race.
A small asynchronous controller has three states, and each one can move to both others. It must work on every chip, whatever its loop delays.
This is an Implement problem with no logic to write. Choose the codes of Q and R, and write the next code for every present code and input column. P has the code 00. The starter is a first try: Q = 11, R = 01 and the flow table copied as it is. Two moves go wrong.
The check runs every move of the flow table nine times, with loop delays from 1 to 3 units. It counts the runs that end anywhere else.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
question | 8 | input of each check |
Full specification
| State | ab = 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| P | (P) | Q | R | (P) |
| Q | P | (Q) | (Q) | R |
| R | P | Q | (R) | (R) |
Two state variables y1 y2. The logic has no delay. Each loop has one delay element, which passes a change only if it lasts longer than its delay. A spare code may be used as an extra state. A move passes if every order of the variable changes ends in the right stable state.
Examples
Example 1
The Codes- Input
CODE_Q and CODE_R
- Output
codes_clash = 0
P is 00. Q and R must take two other codes, different from each other.
Example 2
P, Stable at Ab = 00, When b Rises- Input
ab 00 to 01, nine delay pairs
- Output
delay_pairs_wrong = 0
P must end in Q for all nine delay pairs. If Q is next to P, one variable changes and nothing can go wrong.
Example 3
P, Stable at Ab = 00, When a Rises- Input
ab 00 to 10, nine delay pairs
- Output
delay_pairs_wrong = 0
P is stable at ab = 10 too, so nothing should move. The result counts the delay pairs that left P.
Constraints and Contract
- Keep the module name answer and the names of the constants.
- Every constant is a code from 0 to 3.
Hints
Hint 1
Draw the moves: P with Q, P with R, Q with R. Place the codes on a square; one pair has to sit on a diagonal.
Hint 2
A diagonal move must go through the spare code. In that column, the first state points at the spare code, and the spare code points at the target.
Hint 3
Check the spare code in every column where a move passes through it. Keep every stable entry of the flow table stable.
What the grader checks: Twelve moves: every single input change from every stable total state. Each runs with all nine pairs of loop delays from 1 to 3. The model has no-delay logic and inertial delay elements. Any assignment that ends every move in the right stable state passes, so a noncritical race (every order ends right) is accepted. While the codes clash, every move reports 11, codes invalid.
13 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 2 steps and the final capstone