G7.11.1 Muller C-Element from Gates

EasyImplementIcarus · browser samples / server checksReview the topic

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

SignalWidthRole
words120input of each check
Full specification
The cell library (read-only)
// 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

The module (keep the name and the ports)
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 cq
1111
0000
any otherq 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

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

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 ...
Expected 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.

Run samples executes all 3 public checks. Check all tests runs 14 checks on the server.

Icarus · browser samples / server checks