Build a four-variable function from one 8:1 mux and one inverter, by Shannon expansion on the last variable.
Hardware context: A pump controller and a logic analyser, each built from multiplexer cells. Build a four-variable function from one 8:1 mux and one inverter.
A pump controller reads four float sensors a, b, c and d, with a the most significant. The pump runs when f = 1, and f = Σm(0, 2, 3, 7, 10, 13, 14, 15). The board has room for one 8:1 multiplexer chip and one inverter, and nothing else.
This is an Implement problem. Write pump as a netlist of cells from the read-only library. Use exactly one mux cell and at most one inverter. The constants 1'b0 and 1'b1 may drive data inputs.
The check applies eight input rows per case, one every 4 ns, and records f after each. It also counts your cells.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
script | 32 | input of each check |
Full specification
module pump (
input logic a, b, c, d, // the four sensors; a is the most significant
output wire f // 1: run the pump
);
// your netlist
endmodule
// muxcells.sv: the cell library (read-only). Every cell takes 1 ns. Ports: output first.
// The cells count themselves: tb.n_mux for every mux cell, tb.n_inv for every inverter.
module INV (output wire y, input wire a); not #1 (y, a); initial tb.n_inv++; endmodule
module MUX2 (output wire y, input wire d0, d1, s); assign #1 y = s ? d1 : d0; initial tb.n_mux++; endmodule
module MUX4 (output wire y, input wire d0, d1, d2, d3, s1, s0); assign #1 y = s1 ? (s0 ? d3 : d2) : (s0 ? d1 : d0); initial tb.n_mux++; endmodule
module MUX8 (output wire y, input wire d0, d1, d2, d3, d4, d5, d6, d7, s2, s1, s0);
wire [7:0] d = {d7, d6, d5, d4, d3, d2, d1, d0};
assign #1 y = d[{s2, s1, s0}];
initial tb.n_mux++;
endmodule
| Rule | Detail |
|---|---|
| Function | f = 1 exactly in the rows 0, 2, 3, 7, 10, 13, 14 and 15. The row number is abcd read as binary. |
| Cost | One mux cell of any size, and at most one inverter. |
| Data inputs | Each may be a variable, the inverter output, 1'b0 or 1'b1. |
| Nets | Declare each internal net as a wire. The output f is a wire. |
The result shows f after each of the eight rows, f_row0 to f_row7, in the order the case applies them. It also shows whether the cell count is over the budget.
Examples
Example 1
Rows 0 to 7- Input
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 (abcd)
- Output
f_row0 = yes, f_row1 = no, f_row2 = yes, f_row3 = yes, f_row4 = no, f_row5 = no, f_row6 = no, f_row7 = yes, over_budget = no
The first half of the table: a = 0. f is 1 in the rows 0, 2, 3 and 7. The cell count is within the budget.
Example 2
Rows 8 to 15- Input
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 (abcd)
- Output
f_row0 = no, f_row1 = no, f_row2 = yes, f_row3 = no, f_row4 = no, f_row5 = yes, f_row6 = yes, f_row7 = yes, over_budget = no
The second half: a = 1. f is 1 in the rows 10, 13, 14 and 15.
Example 3
Pairs That Differ in d Only- Input
0010, 0011, 1100, 1101, 0110, 0111, 0000, 0001 (abcd)
- Output
f_row0 = yes, f_row1 = yes, f_row2 = no, f_row3 = yes, f_row4 = no, f_row5 = yes, f_row6 = yes, f_row7 = no, over_budget = no
Rows 2 and 3 are both 1, so their data input is a constant 1. Rows 0 and 1 give 1 then 0, so their data input is d inverted.
Constraints and Contract
- Inputs are known 0/1 values. Each row is held for 4 ns before f is read.
- Keep the module name and the ports.
Hints
Hint 1
Put a, b and c on the three select lines. Then each data input sees two rows of the table: one with d = 0 and one with d = 1.
Hint 2
For each pair of rows, f is 0 in both, 1 in both, equal to d, or equal to d inverted. That value is the data input.
Hint 3
Data input k of the mux is chosen when abc = k. So the rows 2k and 2k + 1 set data input k. Mind which select pin is the most significant.
What the grader checks: Nine directed and six seeded cases apply eight rows each, covering all sixteen rows several times. f is compared with the truth table, computed in JavaScript, after every row. The cell count must be one mux and at most one inverter. The source may hold only cell instances: no assign, no always block and no operator.
15 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