Build a three-input Muller C-element from gate cells. It rises when all inputs are 1, falls when all are 0, and holds otherwise.
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. Build a three-input Muller C-element from gate cells.
An asynchronous pipeline stage must wait for three neighbours before it moves on. A three-input C-element does the waiting.
This is an Implement problem in cells. Build celem3 from the cell library only, with at most 5 cells. The starter is an AND gate: it sets, but it does not hold.
The check applies input words, sometimes changing several inputs at once. After each word it records q, and whether q changed more than once (a glitch). It also counts your cells.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
words | 120 | input of each check |
Full specification
// cells.sv: the unit-delay cell library (read-only).
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter when the simulation starts.
module INV (output wire y, input wire a); not #1 (y, a); initial tb.cells++; endmodule
module AND2 (output wire y, input wire a, b); and #1 (y, a, b); initial tb.cells++; endmodule
module AND3 (output wire y, input wire a, b, c); and #1 (y, a, b, c); initial tb.cells++; endmodule
module OR2 (output wire y, input wire a, b); or #1 (y, a, b); initial tb.cells++; endmodule
module OR3 (output wire y, input wire a, b, c); or #1 (y, a, b, c); initial tb.cells++; endmodule
module OR4 (output wire y, input wire a, b, c, d); or #1 (y, a, b, c, d); initial tb.cells++; endmodule
module celem3 (
input wire a, b, c,
output wire q // 1 when a, b and c are all 1; 0 when all are 0; otherwise q holds
);
...
endmodule
| Inputs a b c | q |
|---|---|
| 111 | 1 |
| 000 | 0 |
| any other | q holds its value |
Only cell instances and wires are allowed: no assign, no always block, no operators. Each script starts with all inputs at 0, so q starts at 0.
Examples
Example 1
Inputs Rise One by One, Then Fall One by One- Input
abc per step: 100 110 111 011 001 000 000 000 000 000 000 000 000 000 000 000 ...
- Output
q_step0 = 'b0, glitch_step0 = 'b0, q_step1 = 'b0, glitch_step1 = 'b0, q_step2 = 'b1, glitch_step2 = 'b0, q_step3 = 'b1, glitch_step3 = 'b0, q_step4 = 'b1, glitch_step4 = 'b0, q_step5 = 'b0, glitch_step5 = 'b0, q_step6 = 'b0, glitch_step6 = 'b0, q_step7 = 'b0, glitch_step7 = 'b0, q_step8 = 'b0, glitch_step8 = 'b0, q_step9 = 'b0, glitch_step9 = 'b0, q_step10 = 'b0, glitch_step10 = 'b0, q_step11 = 'b0, glitch_step11 = 'b0, q_step12 = 'b0, glitch_step12 = 'b0, q_step13 = 'b0, glitch_step13 = 'b0, q_step14 = 'b0, glitch_step14 = 'b0, q_step15 = 'b0, glitch_step15 = 'b0, q_step16 = 'b0, glitch_step16 = 'b0, q_step17 = 'b0, glitch_step17 = 'b0, q_step18 = 'b0, glitch_step18 = 'b0, q_step19 = 'b0, glitch_step19 = 'b0, q_step20 = 'b0, glitch_step20 = 'b0, q_step21 = 'b0, glitch_step21 = 'b0, q_step22 = 'b0, glitch_step22 = 'b0, q_step23 = 'b0, glitch_step23 = 'b0, q_step24 = 'b0, glitch_step24 = 'b0, q_step25 = 'b0, glitch_step25 = 'b0, q_step26 = 'b0, glitch_step26 = 'b0, q_step27 = 'b0, glitch_step27 = 'b0, q_step28 = 'b0, glitch_step28 = 'b0, q_step29 = 'b0, glitch_step29 = 'b0, q_step30 = 'b0, glitch_step30 = 'b0, q_step31 = 'b0, glitch_step31 = 'b0, q_step32 = 'b0, glitch_step32 = 'b0, q_step33 = 'b0, glitch_step33 = 'b0, q_step34 = 'b0, glitch_step34 = 'b0, q_step35 = 'b0, glitch_step35 = 'b0, q_step36 = 'b0, glitch_step36 = 'b0, q_step37 = 'b0, glitch_step37 = 'b0, q_step38 = 'b0, glitch_step38 = 'b0, q_step39 = 'b0, glitch_step39 = 'b0
q rises only on the third rising input, and falls only on the third falling one.
Example 2
Two Inputs High Are Not Enough- Input
abc per step: 110 011 101 110 100 000 000 000 000 000 000 000 000 000 000 000 ...
- Output
q_step0 = 'b0, glitch_step0 = 'b0, q_step1 = 'b0, glitch_step1 = 'b0, q_step2 = 'b0, glitch_step2 = 'b0, q_step3 = 'b0, glitch_step3 = 'b0, q_step4 = 'b0, glitch_step4 = 'b0, q_step5 = 'b0, glitch_step5 = 'b0, q_step6 = 'b0, glitch_step6 = 'b0, q_step7 = 'b0, glitch_step7 = 'b0, q_step8 = 'b0, glitch_step8 = 'b0, q_step9 = 'b0, glitch_step9 = 'b0, q_step10 = 'b0, glitch_step10 = 'b0, q_step11 = 'b0, glitch_step11 = 'b0, q_step12 = 'b0, glitch_step12 = 'b0, q_step13 = 'b0, glitch_step13 = 'b0, q_step14 = 'b0, glitch_step14 = 'b0, q_step15 = 'b0, glitch_step15 = 'b0, q_step16 = 'b0, glitch_step16 = 'b0, q_step17 = 'b0, glitch_step17 = 'b0, q_step18 = 'b0, glitch_step18 = 'b0, q_step19 = 'b0, glitch_step19 = 'b0, q_step20 = 'b0, glitch_step20 = 'b0, q_step21 = 'b0, glitch_step21 = 'b0, q_step22 = 'b0, glitch_step22 = 'b0, q_step23 = 'b0, glitch_step23 = 'b0, q_step24 = 'b0, glitch_step24 = 'b0, q_step25 = 'b0, glitch_step25 = 'b0, q_step26 = 'b0, glitch_step26 = 'b0, q_step27 = 'b0, glitch_step27 = 'b0, q_step28 = 'b0, glitch_step28 = 'b0, q_step29 = 'b0, glitch_step29 = 'b0, q_step30 = 'b0, glitch_step30 = 'b0, q_step31 = 'b0, glitch_step31 = 'b0, q_step32 = 'b0, glitch_step32 = 'b0, q_step33 = 'b0, glitch_step33 = 'b0, q_step34 = 'b0, glitch_step34 = 'b0, q_step35 = 'b0, glitch_step35 = 'b0, q_step36 = 'b0, glitch_step36 = 'b0, q_step37 = 'b0, glitch_step37 = 'b0, q_step38 = 'b0, glitch_step38 = 'b0, q_step39 = 'b0, glitch_step39 = 'b0
Any two inputs at 1 leave q at 0. A majority gate would rise here.
Example 3
All Three Rise and Fall Together- Input
abc per step: 111 000 111 000 000 000 000 000 000 000 000 000 000 000 000 000 ...
- Output
q_step0 = 'b1, glitch_step0 = 'b0, q_step1 = 'b0, glitch_step1 = 'b0, q_step2 = 'b1, glitch_step2 = 'b0, q_step3 = 'b0, glitch_step3 = 'b0, q_step4 = 'b0, glitch_step4 = 'b0, q_step5 = 'b0, glitch_step5 = 'b0, q_step6 = 'b0, glitch_step6 = 'b0, q_step7 = 'b0, glitch_step7 = 'b0, q_step8 = 'b0, glitch_step8 = 'b0, q_step9 = 'b0, glitch_step9 = 'b0, q_step10 = 'b0, glitch_step10 = 'b0, q_step11 = 'b0, glitch_step11 = 'b0, q_step12 = 'b0, glitch_step12 = 'b0, q_step13 = 'b0, glitch_step13 = 'b0, q_step14 = 'b0, glitch_step14 = 'b0, q_step15 = 'b0, glitch_step15 = 'b0, q_step16 = 'b0, glitch_step16 = 'b0, q_step17 = 'b0, glitch_step17 = 'b0, q_step18 = 'b0, glitch_step18 = 'b0, q_step19 = 'b0, glitch_step19 = 'b0, q_step20 = 'b0, glitch_step20 = 'b0, q_step21 = 'b0, glitch_step21 = 'b0, q_step22 = 'b0, glitch_step22 = 'b0, q_step23 = 'b0, glitch_step23 = 'b0, q_step24 = 'b0, glitch_step24 = 'b0, q_step25 = 'b0, glitch_step25 = 'b0, q_step26 = 'b0, glitch_step26 = 'b0, q_step27 = 'b0, glitch_step27 = 'b0, q_step28 = 'b0, glitch_step28 = 'b0, q_step29 = 'b0, glitch_step29 = 'b0, q_step30 = 'b0, glitch_step30 = 'b0, q_step31 = 'b0, glitch_step31 = 'b0, q_step32 = 'b0, glitch_step32 = 'b0, q_step33 = 'b0, glitch_step33 = 'b0, q_step34 = 'b0, glitch_step34 = 'b0, q_step35 = 'b0, glitch_step35 = 'b0, q_step36 = 'b0, glitch_step36 = 'b0, q_step37 = 'b0, glitch_step37 = 'b0, q_step38 = 'b0, glitch_step38 = 'b0, q_step39 = 'b0, glitch_step39 = 'b0
Several inputs may change in one step. q must change once, with no glitch.
Constraints and Contract
- Inputs are known 0/1 values and change only between steps.
- Use only cells from the library, at most 5 of them.
Hints
Hint 1
Write q as a set term and a hold term: the set term is 1 when all inputs are 1.
Hint 2
The hold term keeps q at 1 while at least one input is still 1. It must read q itself.
Hint 3
Count cells: one gate for the set term, two for the hold term, one to combine them.
What the grader checks: Five directed and eight seeded scripts of 40 input words, single and multiple changes. q is compared with a model after every word, and any step where q changes more than once fails. The cells are counted; only library cells may be used.
14 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