Find where a toggle circuit with no clock misfires. Name its essential and static hazards, where each ends, and the fix for each.
Hardware context: An asynchronous pipeline stage that waits for its neighbours, and a toggle circuit that skips states on a board with a long input wire. Find the essential and static hazards of a toggle circuit and the fix for each.
A divide-by-two circuit with no clock goes a, b, c, d as its input x rises and falls. On the new board it sometimes skips a state. Its x signal now reaches the gates through a long wire.
This is an Implement problem with no logic to write. Analyse the netlist and write each answer as a constant. The first three constants are worked examples and are already correct.
Codes are y1y2 read as a binary number: a = 0, b = 1, c = 3, d = 2. The check compares every constant with the right value and names the first wrong one.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
question | 8 | input of each check |
Full specification
| State (code) | x = 0 | x = 1 |
|---|---|---|
| a (00) | (a) | b |
| b (01) | c | (b) |
| c (11) | (c) | d |
| d (10) | a | (d) |
// Codes y1y2: a = 00, b = 01, c = 11, d = 10. Each gate lists its output first.
not #6 n1 (xn, x); // x reaches the gates through a long wire and an inverter: 6 units
not #1 n2 (y1n, y1);
and #1 a1 (t1, xn, y2); // x'y2
and #1 a2 (t2, x, y1); // x y1
and #1 a3 (t3, x, y1n); // x y1'
or #1 o1 (Y1, t1, t2); // Y1 = x'y2 + x y1
or #1 o2 (Y2, t1, t3); // Y2 = x'y2 + x y1'
buf #1 d1 (y1, Y1); // loop delay of y1
buf #1 d2 (y2, Y2); // loop delay of y2
| Constant | What to write |
|---|---|
| END_ONCE | In the flow table, from a (x = 0): the code of the state after x rises once. |
| END_THRICE | In the flow table, from a: the code of the state after x rises, falls and rises. |
| XN_FALLS | After x rises, the time at which xn falls at the AND gates. |
| Y2_RISES | From a, after x rises, the time at which y2 rises (through a3, o2 and d2). |
| ESS_FROM | The code of the stable state, with x = 0, where x rising misfires because of the essential hazard. |
| ESS_END | The code of the state the circuit ends in after that misfire. |
| STATIC_FROM | The code of the stable state, with x = 1, where x falling misfires because of a static hazard in Y2. |
| STATIC_END | The code of the state the circuit ends in after that misfire. |
| FIX_ESS | The fix for the essential hazard. 1: delay in the y2 loop; 2: delay on the x wire; 3: a consensus term. |
| FIX_STATIC | The fix for the static hazard, with the same numbering. |
| MIN_DELAY | The fewest whole units to add to d2 so that y2 reaches a1 no earlier than xn does. |
Times are counted from the change of x. Each gate passes a change only if it lasts longer than the gate's delay. Before each input change the circuit is stable.
Examples
Example 1
Worked Example: One Change- Input
in the flow table, from a (x = 0): the code of the state after x rises once
- Output
end_once = 1
From a with x = 0, x rises: the x = 1 entry of a is b, which is stable there. One change ends in b, code 1.
Example 2
Worked Example: Three Changes- Input
in the flow table, from a: the code of the state after x rises, falls and rises
- Output
end_thrice = 2
From b, x falls to c; from c, x rises to d. Three changes end in d, code 2. The two ends differ: the table has an essential hazard at a.
Example 3
Worked Example: The Slow Inverter- Input
after x rises, the time at which xn falls at the AND gates
- Output
xn_falls = 6
n1 has a delay of 6, so xn falls 6 units after x rises. Until then, a1 still sees the old x.
Constraints and Contract
- Keep the module name answer and the names of the constants.
- Codes are 0 to 3, with y1 as the high bit.
Hints
Hint 1
An essential hazard misfires when a state variable changes through a fast path. It comes back to a gate that still sees the old x. Find the gate fed by xn and by the variable that changes first.
Hint 2
A static hazard is in the logic cover. One term turns off before the other turns on, while the output should stay 1. Look at Y2 when x falls in b.
Hint 3
For the fix, compare when y2 reaches a1 with when xn does. The new y2 must not arrive first.
What the grader checks: The check reads each constant and compares it with the right value. The values come from the flow table, the netlist delays and Icarus runs of the netlist. It cannot see how a value was found.
11 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